Correspondência bipartida com dominação de graus

8

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.G=(V,E)ME(Eu,j)EEujdeg(Eu)>deg(j)(Eu,j)Eu

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.V

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.umabcddefgM={umab,cd}

Willard Zhan
fonte
@Gamow os dois vértices que você deu não formam uma borda em . E
Willard Zhan
@AndrewMorgan No meu exemplo final, uma vez que aparece nos dois ciclos. E as restrições são apenas para as arestas com exatamente um ponto final correspondente. Portanto, não consideramos ( u , v ) se nem u nem v são correspondidos. deg(d)=4(você,v)vocêv
Willard Zhan
Você pode mostrar um exemplo em que sua propriedade não se aplica a um gráfico não bipartido?
JimN
3
@JimNastos um triângulo deve resolver o problema #
Yonatan N
Você diz na pergunta que é "... não necessariamente máximo ..." ... para que ele possa conter apenas uma borda, não é? Que tal um ciclo de duração uniforme? M
Marzio De Biasi

Respostas:

4

Nem sempre existe uma correspondência com sua propriedade em um gráfico bipartido.

Considere, por exemplo, o gráfico ondeG=(V,E)

  • eV={uma1,uma2,uma3,b1,b2,b3,c1,c2,d1,d2,x}
  • E={uma1,uma2}×{c1,c2,x}{b1,b2}×{d1,d2,x}{(uma3,c1),(uma3,d2),(uma3,x),(b3,d1),(b3,c2),(b3,x)}

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={uma1,uma2,uma3,b1,b2,b3}V2={c1,c2,d1,d2,x}x3x6

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 )Mv1v2MMv1M , que é uma contradição.deg(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 MGV{x}3V{x}MM. 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.V1MV1V2GMxM

Por contradição, uma correspondência com a propriedade em questão não existe no G .MG

Mikhail Rudoy
fonte
Sim, eu queria usar essencialmente o mesmo argumento para provar que praticamente qualquer expansor bipartido 3-regular pode ser transformado em um contra-exemplo se excluirmos um vértice e conectarmos seus 3 vizinhos a outros vértices suficientemente distantes.
Domotorp #