Libraion's blog

[Help] Minimum Path Cover Every Edges ?!
By Libraion, history, 3 years ago, In English

Given a undirected graph with $$$N (N \leq 100)$$$ vertices, $$$M (M \leq N * (N + 1) / 2)$$$ edges (there can be edge connect a vertex with itself but all edges are distinct).

Find the number of minimum paths that every edge is in exactly 1 path.

Thanks.

UPD: I just realized it is sum of (odd vertices / 2) for every connected component (and some special case like m = 0, odd vertices = 0).

  • Vote: I like it
  • +38
  • Vote: I do not like it

»
3 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

just find Eilerev way ? or am i wrong ?

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +24 Vote: I do not like it

    Sorry I don't understand what you mean. Could you elaborate it a bit?

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it -24 Vote: I do not like it

      As I understand it, a non-weighted graph is given and we want to visit all the edges exactly once, but exactly this is done by the algorithm of the eleree path, there is a theorem when it is possible to traverse all the edges once.

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +24 Vote: I do not like it

        So what happen when there is > 2 odd degree vertex that you cannot fit every vertices into 1 path. Then how many paths? And what if after finishing 1 path you make the graph unconnected ... etc.

        → Reply
        • »
          »
          »
          »
          »
          3 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Ahhh, I just realized your question, sorry

          → Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply