Denomina-se complemento de um grafo G(V,E) ao grafo G(barra), que possue o mesmo conjunto de vértices V de G. O conjunto de arestas é constituído por todo par de vértices v, w distintos pertencente a V, que não é aresta de G.
Grafo Completo
Um grafo é completo quando existe uma aresta entre cada par de seus vértices.
kn denota o grafo completo com n vértices.
Grafo Bipartide
Um grafo G(V,E) é bipartide quando o seu conjunto de vértices puder ser particionado em dois subconjuntos V1, V2 tais que toda aresta de G une um vértice de V1 a outro vértice de V2.
V1={a,b} V1={a,b,c}
V2={c,d,e} V2={d,e,f}
Grafo Bipartide Completo
Um grafo que possui uma aresta para cada par de vértices v1v2, sendo v1 pertencente a V1 e v2 pertencente a V2. Se n1=|V1| e n2=|V2| , um grafo bipartido completo é denotado por kn1,n2 e possui n1*n2 arestas.
Subgrafo
Um subgrafo G2(V2,E2) de um grafo G1(V1,E1) é um grafo tal que V2 está contido em V1 e E2 está contido em E1.
Se o subgrafo G2 de G1 satisfaz: para quaisquer v, w pertencente a V2, se (v,w) pertence a E1, então (v,w) pertence a E2. Dessa forma, G2 é dito subgrafo induzido pelo conjunto de vértices V2.
(b) e (c) são subgrafos de (a)
(c) é subgrafo induzido de (a)
Clique
Denomina-se clique de um grafo G a um subgrafo de G que seja completo.
Conjuntos Independentes de Vértices
Subgrafo induzido de G que seja totalmente conexo.
Lembrando:
- ciclo é um caminho V1, V2, ..., Vk, Vk+1 sendo V1=Vk+1, k>3
- ciclo é simples se o caminho for simples e um caminho é simples quando todos os vértices forem distintos.
- um grafo que não possui ciclos é acíclico.
Árvores
Um grafo que é acíclico e conexo T(V,E)
Folha
Um vértice v da árvore é uma folha se possuir grau<=1.
Vértice Interior
Um vértice v é interior se grau |v|>1.
Floresta
Um conjunto de árvores.
Todo grafo acíclico é uma floresta.
"Todas as possíveis árvores (não isomórfas entre si) com 6 vértices."
Isomorfismo entre grafos
Sejam dois grafos G1(V1,E1) e G2(V2,E2), com |V1|=|V2|=n. Se existe uma função unívoca f:V1->V2, tal que (v,w) pertence a E1 sse (f(v),f(w)) pertence a E2, para todo v, w pertencente a V1, então G1 e G2 são ditos isomorfos entre si.
Toda árvore T de n vértices possui exatamente n-1 arestas.
Teorema:
Um grafo G é uma árvore se e só se existir um único caminho entre cada par de vértices G.
Prova:
Seja G uma árvore.
Então G é conexo e portanto existe pelo menos um caminho entre cada par de vértices v e w de G.
Suponha que existem 2 caminhos distintos vP1w e vP2w entre v e w.
Então vP1wP2v é um ciclo, o que contradiz G ser acíclico.
Reciprocamente, se existe exatamente um caminho entre cada par de vértices de G, então o grafo é obviamente conexo, e além disso não pode conter ciclos.
Portanto, G é uma árvore.
Conceitos Básicos de Grafos
Excentricidade de um Grafo e Árvores