CODEWITHSUNDEEP
algorithmgraph
Cereal_Killer
Cereal_Killer

Reputation: 324

count unique pair in graph (vertices repetition not allowed)

Is there any Algorithm exists for counting unique pair (pair of vertices) in undirected graph (vertices repetition not allowed). I think it could be a variation of bipartite graph but if there is any better way to find out .. please comment.
[I think Problem Belongs to Perfect Matching Algorithm]
Problem Statement: I have an undirected graph which consists of n vertexes and m edges. I can delete edges from the graph. Now I'm interested in one question : is it possible to delete edges in the graph so that the degree of each vertex in the graph will be equal 1.. There can be multiple edges in the graph, but can not be any loops
Example: n = #vertices, m = #edges
n = 4, m = 6
1 2
1 3
1 4
2 3
2 4
3 4
Unique sequence could be (1 2, 3 4) (1 4, 2 3) (1 3, 2 4)

Upvotes: 0

Views: 996

Answers (2)

kiruwka
kiruwka

Reputation: 9450

Here is pseudo code, it should run in O(|E|) time, i.e. linear of number of edges :

Suppose G = (V, E) is your initial graph, with E - initial set of all edges

count = 0;
while(E is not empty) {
    //1. pick up any edge e = (n1, n2) from E

    //2. remove e from G
    E = E - e;

    //3. calculate number of edges in G remaining if nodes n1 and n2 were removed
    // -> these are edges making pair with e
    edges_not_connected_to_e = |E| - |n1| - |n2|;
    // where |n1| - degree of n1 in updated G (already without edge e)

    //4. update the count
    count += edges_not_connected_to_e;
}
return count;

Let me know if you need more clarifications. And probably someone could fix my Graph math notations, in case they are incorrect.

Upvotes: 1

Vincent van der Weele
Vincent van der Weele

Reputation: 13177

The set of edges that covers the entire graph without using the same vertex multiple times is called a matching or independent edge set, see wikipedia.

In that article is also mentioned that the number of distinct matchings in a graph (which is the number you are after) is called the Hosoya index, see this wikipedia article.

Algorithms to compute this number are not trivial and Stack Overflow wouldn't be the right place to try to explain them, but I at least I hope you have enough pointers to investigate further.

Upvotes: 1

Related Questions