CODEWITHSUNDEEP
algorithmgraphgraph-theorydirected-graphundirected-graph
Faizan Syed
Faizan Syed

Reputation: 11

Convert undirected graph to directed graph with specific condition

undirected graph is given which has M edges and N vertices we have to convert every edge from u-v to u->v or v->u such that indegree of every vertex is even.Which method or algorithm is suited for least time complexity.

Upvotes: 0

Views: 2508

Answers (3)

Saumya Agnihotri
Saumya Agnihotri

Reputation: 894

You can do something like this --> Only change you will have to make is, make MST before doing topological

https://www.geeksforgeeks.org/assign-directions-to-edges-so-that-the-directed-graph-remains-acyclic/

Upvotes: 2

mcdowella
mcdowella

Reputation: 19601

Here's a different approach - I don't reckon you want to do Gaussian elimination with n=100,000 so I did a web search for related problems.

If the graph has more than one connected component, you can consider them separately, so let's assume it only has one.

Build a spanning tree on your component and mark one of the vertices the root of that tree. Fix the directions of the edges not on the spanning tree however you like. Take each vertex one at a time starting from the leaves, dealing with all of the children of a vertex before you deal with that vertex. For each vertex, chose the direction of the tree edge up to its parent so that its own indegree is even, and ignoring the consequences for its parent. Each vertex except the root has an edge joining it with its parent, so for every vertex except the root you can make sure that its indegree is even.

When you come to the root you don't have any edges left with a direction you can change, so you can't change its indegree, which is clearly either even or odd. If it is even all is well - every vertex has even indegree. If it is odd, you have one vertex with odd indegree and all the others with even indegree, so the sum of all of the indegrees is odd. But the sum of all of the indegrees is just the number of edges in the graph, which you can't change. If the number of edges in the graph is odd there will always be at least one vertex with odd indegree, and the problem was impossible anyway.

Upvotes: 2

mcdowella
mcdowella

Reputation: 19601

Give each edge an arbitrary direction, and create a variable (currently unknown) which says whether that edge's direction needs to be changed.

For each vertex an edge is incoming according to either x or 1^x, where x is the unknown for that edge and 1^x is 1 XOR x = NOT x, depending on whether the original direction assigned to that edge was towards that vertex or not.

For each vertex, the number of incoming edges is even if the result of xoring together the results of these equations is 0 - which is the same thing as saying the result of adding them together mod 2 is 0.

So you have a system of linear equations mod 2, which is the same thing as binary linear equations, and you can use Gaussian elimination to see if there is a solution.

(There might be a more graph-theoretical way of doing this, but I think this is a solution).

Upvotes: 1

Related Questions