Bipartite Matching mit Grad Dominanz

Bei einem ungewichteten zweigliedrigen Graphen ist . Ist es wahr , dass es existiert immer ein nicht leeren Matching (nicht unbedingt maximal), so dass für jeden mit abgestimmt und unübertroffen, es hält ? Hier ist nicht geordnet, dh kann auf beiden Seiten sein.M ≤ E ( i , j ) ≤ E i j Grad ( i ) > Grad ( j ) ( i , j ) $G=(V, E)$$M\subseteq E$$(i,j)\in E$$i$$j$$\deg(i)>\deg(j)$$(i,j)$$i$

Meine Intuition darüber, warum dies wahr ist, ist, wenn jeder Scheitelpunkt in den gleichen Grad hat, gibt es immer eine perfekte Übereinstimmung, die die Übereinstimmung ist, die wir benötigen. Für einige einfache Diagrammstrukturen wie Bäume oder unicyclische Diagramme ist eine maximale Übereinstimmung erwünscht, da der Grad eines Blattes immer kleiner als sein übergeordnetes ist.$V$

Ich habe versucht, es aus Halls Theorem zu beweisen, bin aber gescheitert. Ein Teil der Komplexität dieses Problems besteht darin, dass die Lösung nicht immer eine maximale Übereinstimmung ist. Betrachten zum Beispiel einen Graphen, der aus zwei 4-Zyklen und . Dann sind und seine symmetrischen Übereinstimmungen die einzigen Lösungen, die nicht maximal sind.d e f g M = { a b , c d $abcd$$defg$$M=\{ab,cd\}$

Es gibt nicht immer eine Übereinstimmung mit Ihrer Eigenschaft in einem zweigeteilten Diagramm.

Betrachten Sie zum Beispiel den Graphen wobei$G = (V, E)$

• und$V = \{a_1, a_2, a_3, b_1, b_2, b_3, c_1, c_2, d_1, d_2, x\}$
• $E = \{a_1, a_2\} \times \{c_1, c_2, x\} \cup \{b_1, b_2\} \times \{d_1, d_2, x\} \cup \{(a_3, c_1), (a_3, d_2), (a_3, x), (b_3, d_1), (b_3, c_2), (b_3, x)\}$

Dieser Graph ist zweiteilig (mit als einem Teil und V 2 = { c 1 , c 2 , d 1 , d 2 , x } wie der andere). Jeder Scheitelpunkt in diesem Diagramm mit Ausnahme von x hat Grad 3 . Scheitelpunkt x hat Grad 6 .$V_1 = \{a_1, a_2, a_3, b_1, b_2, b_3\}$$V_2 = \{c_1, c_2, d_1, d_2, x\}$$x$$3$$x$$6$

Nehmen wir aus Gründen des Widerspruchs an, dass ein mit Ihrem Eigentum übereinstimmendes existiert. Betrachten Sie zwei benachbarte Eckpunkte v 1 und v 2 , die den gleichen Grad haben. Es stellt sich heraus, dass die Bedingungen für M implizieren, dass beide dieser Scheitelpunkte den gleichen Status haben, der übereinstimmt oder nicht (dh entweder beide oder keiner der Scheitelpunkte muss in M übereinstimmen ). Dies kann sehr einfach durch Widerspruch bewiesen werden: Angenommen, ein Scheitelpunkt (wlog v 1 ) stimmt überein und der andere nicht; dann, da es eine Kante zwischen ihnen gibt, sagt uns die gegebene Eigenschaft auf M , dass d e g ( v 1$M$$v_1$$v_2$$M$$M$$v_1$$M$ , was ein Widerspruch ist.$deg(v_1) > deg(v_2)$

Somit ist der Übereinstimmungsstatus benachbarter Scheitelpunkte gleichen Grades der gleiche. Wenn dann eine Menge von Scheitelpunkten die Eigenschaft hat, dass jeder Scheitelpunkt den gleichen Grad hat und der durch diese Scheitelpunkte induzierte Teilgraph verbunden ist, können wir diese Regel mehrmals anwenden, um zu schließen, dass alle Scheitelpunkte in der Menge dieselbe Übereinstimmung haben müssen oder nicht Status. Insbesondere muss in der Matched-or-Not-Status jedes Scheitelpunkts in V ∖ { x } gleich sein, da diese Scheitelpunkte alle Grad 3 haben und verbunden sind. Mit anderen Worten, entweder wird jeder Scheitelpunkt in V ∖ { x } in M abgeglichen , oder es wird kein solcher Scheitelpunkt in M abgeglichen$G$$V \setminus \{x\}$$3$$V \setminus\{x\}$$M$$M$. Wenn der Übereinstimmungs- oder Nichtübereinstimmungsstatus für diese Scheitelpunkte "übereinstimmt", wird jeder Scheitelpunkt im -Teil der Bipartition in M abgeglichen ; Dies ist unmöglich, da es in V 1 mehr Eckpunkte gibt als im anderen Teil V 2 . Wenn die Matched-oder-nicht - Status für diesen Scheiteln wird als „nicht zugeordnet“ , dann der einzige Knoten in G , die in angepaßt werden kann M ist x ; Da eine nicht leere Übereinstimmung (wie M sein muss) mit mindestens zwei Eckpunkten übereinstimmt , sehen wir, dass dieser Fall ebenfalls unmöglich ist.$V_1$$M$$V_1$$V_2$$G$$M$$x$$M$

Im Widerspruch dazu existiert in G kein Matching mit der fraglichen Eigenschaft .$M$$G$