Help in a Graph question
An undirected graph with N vertices (numbered 1 through N) and M edges. He wants to divide it into K parts (subgraphs) for some integer K.
An edge is said to be a part of a subgraph if its both the vertices is present in the subgraph.
The condition is that every subgraph should contain even number of edges belonging to it(zero edges is also considered even).We need to minimise the value of K.
Example: N=5,M=5
the edges: 1-2,1-3,2-3,2-4,3-4
output: K=2
the subgraph corresponding to which each vertices numbered from 1 to N belongs:
1 belongs to subgraph 1,2 belongs to subgraph 2,3 belongs to subgraph 1,4 belongs to subgraph 1,5 belongs to subgraph 2
An edge is said to be a part of a subgraph if its both the vertices is present in the subgraph.
The condition is that every subgraph should contain even number of edges belonging to it(zero edges is also considered even).We need to minimise the value of K.
Example: N=5,M=5
the edges: 1-2,1-3,2-3,2-4,3-4
output: K=2
the subgraph corresponding to which each vertices numbered from 1 to N belongs:
1 belongs to subgraph 1,2 belongs to subgraph 2,3 belongs to subgraph 1,4 belongs to subgraph 1,5 belongs to subgraph 2
>Duthomhas
I was basically thinking of taking the whole graph as one when the edges are even and when odd doing DFS and dividing accordingly but the case of disconnected graph was causing the problem.
I was basically thinking of taking the whole graph as one when the edges are even and when odd doing DFS and dividing accordingly but the case of disconnected graph was causing the problem.
Er, ok, so I drew a picture of your graph.
1,5 cannot be a subgraph, that leaves 2,3,4 with three edges. Vertices 2 or 3 must be paired with 5. For example:
{2,5|0 edges}, {1,3,4|2 edges}
Do you see a pattern you can exploit here?
[edit]
The graph described by 5V, 5E = 1-2, 1-3, 2-3, 2-4, 3-4:
1,5 cannot be a subgraph, that leaves 2,3,4 with three edges. Vertices 2 or 3 must be paired with 5. For example:
{2,5|0 edges}, {1,3,4|2 edges}
Do you see a pattern you can exploit here?
[edit]
The graph described by 5V, 5E = 1-2, 1-3, 2-3, 2-4, 3-4:
(1)--(2) | / | (5) | / | (3)--(4) |
Last edited on
Topic archived. No new replies allowed.