Блог пользователя pabloskimg

Proof that if a biconnected component has an odd simple cycle, then ALL edges in such component belong to some odd simple cycle?
Автор pabloskimg, история, 7 лет назад, По-английски

Is it true that if a biconnected component has an odd simple cycle, then ALL edges in that component belong to some (not necessarily the same) odd simple cycle? If that's the case, what would be a formal proof for that? I believe this property would be crucial to solve this problem: http://codeforces.net/problemset/problem/97/E

  • Проголосовать: нравится
  • +3
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +13 Проголосовать: не нравится

Yes, it's true.

Imagine you have a cycle of odd length which covers vertices (a1, a2, ..., a2k + 1). Then imagine a edge. If the edge is (u, v) we can simply pick any path from u to any vertex in the cycle a. Then go through the cycle and get back to this vertex. Finally go from this vertex in the cycle to u by the same path, you chose earlier. What will be the parity of the length of this cycle?

Well the length is 2k + 1 (odd) plus 2 * (the length of the path from u to the cycle). This number obviously will be always odd as it is sum of an odd number and even (because we have 2*).

→ Ответить
  • »
    »
    7 лет назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I didn't quite understand your proof. You said you go from u to some arbitrary node a in the odd cycle, but what if this path (u -> a) partially overlaps with the cycle? And then you say you go back from a to u using the same path backwards. But that would not be a simple cycle, because you would be repeating nodes. Moreover, you didn't mention the node v, but remember you want to prove that the edge (u,v) belongs to an odd length cycle.

    → Ответить
»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).

→ Ответить
»
7 лет назад, # |
← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

I go over the proof in this video for a different problem: https://www.youtube.com/watch?v=tRTezLvPZ3k

→ Ответить
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Thanks for the video. Do I need to watch it all or can I skip to the proof part?

    → Ответить
    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      You can skip right to the proof part at the end

      → Ответить
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Ok, I just reviewed the proof and it makes sense except for the fact that you are assuming that your paths I1 and I2 from the external node to the odd cycle are disjoint. Why can we make such assumption?

        → Ответить