Black metal

Teoria dos Grafos
Edson Prestes

Teoria dos Grafos
Complemento de Grafos
Mostre que para qualquer Grafo G com 6 pontos, G ou possui um triângulo Considere um vértice v de V(G). Sem perda de generalidade, podemos assumir v é adjacente a outros três vértices u1, u2 e u3 em G. ! Se dois destes vértices forem adjacentes, então existirá um triangulo formado por estes dois e por v. ! Caso contrário, estes três vértices não serão adjacentes entre si em G, mas serão em

Teoria dos Grafos
Decomposição
Uma decomposição de um grafo é uma lista de subgrafos tal que cada aresta aparece exatamente uma única vez em um único subgrafo.

Teoria dos Grafos
Matching
Um matching em um grafo G é um conjunto de arestas que não formam loops e que não compartilham vértices entre si. ! Um vértice incidente às arestas de um matching M é dito saturado por M. ! Um matching perfeito de G satura todos os vértices de G. Determine um matching para o grafo abaixo

É um matching perfeito ?

Sim!

Teoria dos Grafos
Matching
O tamanho de um matching M é igual a quantidade de arestas de M. ! Um matching M de um grafo G é maximal se toda aresta que não participa de M é incidente a alguma aresta em M. ! Se M for o matching de maior cardinalidade de G então ele é chamado matching máximo.

Teoria dos Grafos
Matching
Um caminho de alternante em um matching M é um caminho cujas arestas alternam entre aquelas que estão em M e aquelas que não estão em M. !
!

Um caminho alternante, cujos vértices extremos não são saturados por M, é um caminho de aumento de M. !
!

Quando M possuir um caminho de aumento P podemos trocar as arestas deste caminho, substituindo aquelas que não estão M pelas que estão. Isto irá aumentar em uma (1) unidade o tamanho do matching. !
!

Uma observação importante é que o matching máximo é caracterizado pela ausência de caminhos de aumento.

Teoria dos Grafos
Matching
O matching do grafo abaixo, representado pelas arestas sólidas, é um matching