Dado um gráfico bipartido não ponderado . É verdade que sempre existe uma correspondência não vazia M ⊆ E (não necessariamente máxima), de modo que para todo ( i , j ) ∈ E com i correspondido e j sem correspondência, ele detém deg ( i ) > deg ( j ) ? Aqui ( i , j ) não está ordenado, ou seja, eu posso estar em ambos os lados.
Minha intuição sobre por que isso é verdade é que, quando todo vértice em tem o mesmo grau, sempre há uma correspondência perfeita, que é a correspondência que exigimos. Para algumas estruturas gráficas simples, como árvores ou gráficos monociclicos, é desejada uma correspondência máxima, uma vez que o grau de uma folha é sempre menor que seu pai.
Tentei provar isso pelo teorema de Hall, mas falhei. Parte da complexidade desse problema é que a solução nem sempre é uma correspondência máxima. Por exemplo, considerando um gráfico que consiste em dois 4 ciclos e d e f g . Então M = { a b , c d } e suas combinações simétricas são as únicas soluções, que não são máximas.
fonte
Respostas:
Nem sempre existe uma correspondência com sua propriedade em um gráfico bipartido.
Considere, por exemplo, o gráfico ondeG = ( V, E)
Este gráfico é bipartido (com como uma parte e V 2 = { c 1 , c 2 , d 1 , d 2 , x } como o outro). Todo vértice neste gráfico, exceto x, possui o grau 3 . O vértice x tem grau 6 .V1= {a1,um2,um3,b1,b2,b3} V2= { c1,c2,d1,d2, x } x 3 x 6
Suponha, por uma questão de contradição, que exista um correspondente à sua propriedade. Considere quaisquer dois vértices adjacentes v 1 e v 2 que têm o mesmo grau. Acontece que as condições em M implicam que esses dois vértices tenham o mesmo status de correspondência ou não (ou seja, ambos ou nenhum dos vértices devem corresponder em M ). Isso pode ser provado de maneira muito simples por contradição: suponha que um vértice (wlog v 1 ) seja correspondido e o outro não; então, como existe uma aresta entre eles, a propriedade fornecida em M nos diz que d e g ( v 1 )M v1 v2 M M v1 M , que é uma contradição.de g( v1)>deg(v2)
Assim, o status correspondente ou não de vértices adjacentes do mesmo grau é o mesmo. Então, se um conjunto de vértices tem a propriedade de que todo vértice tem o mesmo grau e o subgráfico induzido por esses vértices está conectado, podemos aplicar essa regra várias vezes para concluir que todos os vértices no conjunto devem ter o mesmo pareamento ou não status. Em particular, em o status de correspondência ou não de todos os vértices em V ∖ { x } deve ser o mesmo, pois todos esses vértices possuem grau 3 e estão conectados. Em outras palavras, cada vértice em V ∖ { x } é correspondido em M ou nenhum vértice é correspondido em MG V∖{x} 3 V∖{x} M M . Se o status de correspondência ou não desses vértices for "correspondido", todos os vértices na parte da bipartição serão correspondidos em M ; isso é impossível, pois há mais vértices em V 1 do que na outra parte V 2 . Se o status correspondente ou não desses vértices for "não correspondente", o único vértice em G que pode ser correspondido em M é x ; como uma correspondência não vazia (como M deve ser) corresponde a pelo menos dois vértices, vemos que esse caso também é impossível.V1 M V1 V2 G M x M
Por contradição, uma correspondência com a propriedade em questão não existe no G .M G
fonte