Lema do aperto de mão

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Question book-4.svg
Esta página ou secção cita fontes confiáveis e independentes, mas que não cobrem todo o conteúdo, comprometendo a sua verificabilidade (desde novembro de 2015).
Por favor, adicione mais referências inserindo-as no texto. Material sem fontes poderá ser removido.—Encontre fontes: Google (notícias, livros e acadêmico)
Nesse grafo, um número par de vértices (os quatro vértices enumerados 2, 4, 5, e 6) tem grau ímpar. A soma dos graus dos vértices é 2 + 3 + 2 + 3 + 3 + 1 = 14, o dobro do número de arestas.

Na teoria do grafos, um ramo da matemática, o lema do aperto de mão é a afirmação que todo grafo não-direcionado finito tem um número par de vértices de grau ímpar (o número de arestas ligadas ao vértice). Em termos coloquiais, num grupo de pessoas das quais algumas apertam mãos, um número par de pessoas deve ter apertado um número ímpar de mãos de outras pessoas.

O lema do aperto de mãos é uma consequência da fórmula da soma dos graus (também chamado às vezes de lema do aperto de mão),

para um grafo com conjunto de vértices V e conjunto de arestas E. Ambos os resultados foram provados por Leonhard Euler (1736) no seu artigo famoso sobre o problema das Sete pontes de Königsberg que iniciou o estudo da teoria dos grafos.

Os vértices de grau ímpar em um grafo são às vezes chamados de nós ímpares ou vértices ímpares; nessa terminologia, o lema do aperto de mão pode ser reescrito como a afirmação que todo grafo possui um número par de nós ímpares.

Prova[editar | editar código-fonte]

A prova de Euler para a fórmula da soma dos graus usa a técnica de contagem dupla: ele conta o número de pares incidentes (v,e) onde e é uma aresta e vértice v é um dos seus pontos terminais, de duas maneiras diferentes. Vértice v pertence a deg(v) pares, onde deg(v) (o grau de v) é o número de arestas incidentes a ele. Então o número de pares incidentes é a soma dos graus. No entando, cada aresta no grafo petence a exatamente dois pares incidentes, um para cada um dos seus pontos terminais; então, o número de pares incidentes é 2|E|. Já que essas duas fórmulas contam o mesmo conjunto de objetos, elas devem ter valores iguais.

Numa soma de inteiros, a paridade da soma não é afetada por termos pares na soma; a soma total é par quando há um número par de termos ímpares, e ímpar quando há um número ímpar de termos ímpares. Já que um lado da fórmula da soma dos graus é o número par 2|E|, então a soma no outro lado deve ter um número par de termos ímpares; ou seja, deve haver um número par de vértices de grau ímpar.

De modo alternativo, é possível utilizar uma indução matemática para provar que o número de vértices de grau ímpar é par, removendo uma aresta por vez de um dado grafo e utilizando uma análise de caso nos graus dos seus pontos terminais para determinar o efeito da sua remoção na paridade do número de vértices de grau ímpar.

Grafos regulares[editar | editar código-fonte]

A fórmula de soma de graus implica que todo grafo r-regular com n vértices tem nr/2 arestas.[1] Em particular, se r é impar então o número de arestas é divisível por r.

Grafos infinitos[editar | editar código-fonte]

Um grafo infinito que não obedece o lema do aperto de mão

O lema do aperto de mão não se aplica a grafos infinitos, mesmo quando eles possuem apenas um número finito de vértices de grau ímpar. Por exemplo, um grafo de caminho infinito com um ponto terminal possui apenas um vértice de grau ímpar ao invés de ter um número par de tais vértices.

Grafos de troca[editar | editar código-fonte]

Várias estruturas combinatoriais listadas por Cameron & Edmonds (1999) podem ser demonstradas pares em número através de uma relação com o número de vértices ímpares em um "grafo de troca" apropriado.

Por exemplo, como  C. A. B. Smith provou, em qualquer grafo cúbico G deve haver um número par de ciclos Hamiltonianos através de qualquer aresta fixa uv; Thomason (1978) usou uma prova baseada no lema do aperto de mão para expandir esse resultado aos grafos G nos quais todos os vértices possuem grau ímpar. Thomason define um grafo de troca H onde os vértices estão em uma correspondência um-por-um com os caminhos Hamiltonianos começando em u e continuando por v. Dois tais caminhos p1 e p2 estão conectados por uma aresta em H se for possível obter p2 adicionando uma nova aresta ao fim de p1 e removendo outra aresta do meio de p1; isso é uma relação simétrica, então H é um grafo não-direcionado. Se um caminho p termina em um vértice w, então o vértice correspondente a p em H tem grau igual ao número de maneiras em que p pode ser estendido por uma aresta que não se conecta de volta a u; ou seja, o grau desse vértice em H  ou é deg(w) − 1 (um número par) se p não forma parte de um ciclo Hamiltoniano com uv, ou deg(w) − 2 (um número ímpar) se p é parte de um ciclo Hamiltoniano com uv. Já que H possui um número par de vértices ímpares, G deve ter um número parde ciclos Hamiltonianos com uv.

Complexidade computacional[editar | editar código-fonte]

Em conexão com o método de grafo de troca para provar a existência de estruturas combinatoriais, é interessante perguntar com qual eficiência essas estruturas podem ser encontradas. Por exemplo, suponha que é dado como entrada um ciclo Hamiltoniano em um grafo cúbico; pelo teorema de Smith existe um segundo ciclo. Quão rápido esse segundo ciclo pode ser encontrado? Papadimitriou (1994) investigou a complexidade computational de questões como essas, ou de modo mais geral de encontrar um segundo vértice de grau ímpar em um grande grafo definido implicitamente. Ele definiu a classe de complexidade PPA para encapsular problemas como esse; uma classe fortemente relacionada definida sobre grafos direcionados, PPAD, atraiu atenção significativa em teoria dos jogo algorítmica porque calcular um Equilíbrio de Nash é computacionalmente equivalente ao problema mais difícil dessa classe.[2]

Outras aplicações[editar | editar código-fonte]

O lema do aperto de mão também é usado em provas do lema de Sperner e do caso  of the piecewise linear case of the mountain climbing problem.

Notes[editar | editar código-fonte]

  1. Aldous, Joan M.; Wilson, Robin J. (2000), «Theorem 2.2», Graphs and Applications: an Introductory Approach, ISBN 978-1-85233-259-4, Undergraduate Mathematics Series, The Open University, Springer-Verlag, p. 44 
  2. Chen, Xi; Deng, Xiaotie (2006), «Settling the complexity of two-player Nash equilibrium», Proc. 47th Symp. Foundations of Computer Science, pp. 261–271, doi:10.1109/FOCS.2006.69, Predefinição:ECCC 

References[editar | editar código-fonte]