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

condition for eulerian and hamiltonian circuit
Автор Vital1ty, 10 лет назад, По-английски

Is there any condition for a graph to have a circuit that is both eulerian and hamiltonian ??

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

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

Consider the graph with n vertices. Hamiltonian circuit contains n edges. So the graph must contain only n edges. And the only way to build hamiltonial graph with n edges is take some permutation of vertices p1, p2, ..., pn and add edges p1 - p2, p2 - p3, ..., pn - 1 - pn, pn - p1. So you should just check the graph to be one big circuit.

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

    If I haven't misunderstood the question and the answer, I think that also K5 (a clique having 5 vertices) is both Hamiltonian and Eulerian. However, it is obviously not a circuit.

    // This is "true" also for K2n + 1,  n ≥ 2 and many other graphs.

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

      I think you misunderstood it, the question was whether the graph contains a cycle that is both hamiltonian and eulerian, not whether the graph contains both hamiltonian and eulerian cycles.

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

        OK, thanks ;)

        If it's really the case, the presented solution is of course OK :)

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

    Thnx :)

    → Ответить