Let's G=(U,V,E) be a balanced bipartite graph which |U|=|V|=n and |E|=n*(n−1); All nodes in U are connected to all nodes in V except ui to vi for 1≤i≤n.

ubumanzi18

ubumanzi18

Answered question

2022-09-04

Let's G = ( U , V , E ) be a balanced bipartite graph which | U | = | V | = n and | E | = n ( n 1 ); All nodes in U are connected to all nodes in V except u i to v i for 1 i n.
Definition 1: Cross edges are two edges in E, one with two end points u i , v j and the other with u j , v i
Definition 2: Good-perfect matching is a perfect matching with no cross edges.
What is the complexity of counting the number of Good-perfect matching in G?

Answer & Explanation

Vaughn Greer

Vaughn Greer

Beginner2022-09-05Added 15 answers

Define P ( n ) as the number of good-perfect matchings on n points. We have to match u 1 to something, n 1 choices, and it might as well be v 2 . Now we are not allowed to connect u 2 to v 1 , so let C ( n ) be the number of ways of completing a good-perfect matching on n points with one set of mismatched indices that cannot be connected. Similarly let D ( n ) be the number of ways of completing a good-perfect matching with one set of mismatched indices that are allowed to be matched. After we connect u 2 to v 3 we are allowed to connect u 3 to v 1 , so we have a case of D.
The recurrences are
P ( n ) = ( n 1 ) C ( n 1 )
C ( n ) = ( n 1 ) D ( n 1 )
D ( n ) = P ( n 1 ) + ( n 1 ) D ( n 1 )
started with D ( 1 ) = 1 , C ( 1 ) = 0 , P ( 1 ) = 0 which leads to
n D C P 1 1 0 0 2 1 1 0 3 2 2 2 4 8 6 6 5 38 32 24 6 214 190 160 7 1444 1284 1140 8 11248 10108 8988 9 98972 89984 80864 10 971612 890748 809856

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?