Teoria dos Grafos - Conceitos Básicos 

---

Definição de Grafo

Um grafo G = (VG,AG) consiste de um conjunto finito e não vazio VG ( |VG|  1 ), e uma família finita, AG, de pares não ordenados de elementos de VG. Os elementos de VG são chamados de vértices e os de AG arestas.

Touro	Sem nome especial
VG = {a,b,c,d,e}	VG = {1,2,3,4}
AG ={ (a,b),(b,c),(b,d),(d,e),(c,d) }	AG = {(1,2),(1,2),(2,1),(1,3),(3,4),(4,4)}

 

Definições Auxiliares

Família: Diferente de conjunto, uma família permite elementos duplicados.
Par não ordenado: (a,b) = (b,a)
Grafo Trivial é aquele em que VG é um conjunto unitário e AG = 
Grafo Identidade de G é um grafo H tal que VG=VH e AG=AH
Seja G um grafo e  = (a,b)  AG.
Definimos:

a e b são os extremos da aresta 
a e b são vértices adjacentes
é incidente a a e b

Arestas Adjacentes são duas arestas com um extremo em comum .
Arestas Múltiplas são arestas que possuem os mesmos extremos. ( os dois )
Laço é uma aresta cujos extremos são iguais ( Ex.: (4,4) )
Tamanho de um grafo G = |VG|+|AG|   (uma das possíveis definições)
Obs: Usaremos, neste texto, n para indicar |VG|, e m para indicar |AG|

Grafo Orientado

Quando a família de arestas é formada por pares ordenados dizemos que o grafo é orientado ou direcionado.
Nesse caso, ao desenhar o grafo, devemos usar uma seta partindo do primeiro elemento do par até o segundo:
 

VG1 = { a,b,c }.	VG2 = { a,b,c }.
AG1 = { (a,b) , (b,c) }	AG2 = { (a,b) , (c,b) }

Os grafos G₁ e G₂ são diferentes , /* Se não fossem orientados seriam iguais */

Grafo Simples

Um grafo simples é um grafo que não contém nem laços nem arestas múltiplas.

Ex: Grafo Touro.
  Os grafos abaixo Não são exemplos de grafos simples:
 

Laço (a')	Arestas Múltiplas (b' b'')

 

Representação dos Grafos

Lista de Adjacências

O grafo é representado por uma lista de listas .

Exemplo:
 

Vértices	Vértices aos quais estão ligados
1	2 4 5
2	1 3
3	1 2
4
5	3 4

Obs. Se o grafo fosse orientado a  primeira coluna da tabela acima seria a origem, e a segunda o destino das arestas.
 
 

1245      213      312      4      534

Grafo G,

VG ={1,2,3,4,5}
AG ={ (1,2), (1,4), (1,5),(2,1),(2,3),(3,1),(3,2),(5,3),(5,4)}

Matriz de Adjacência

O grafo orientado é representado por uma matriz quadrada, nXn, em que n é o número de vértices do Grafo.
Indicamos a existência de uma aresta saindo de vértice i e chegando em um vértice j , colocando o número 1 na linha i, coluna j, da matriz. (Na matriz abaixo, por exemplo, existe a aresta (1,2), mas não existe a aresta (2,1))

Exemplo:

Grafo G,

VG ={1,2,3,4}
AG ={ (1,2), (1,4), (2,2), (2,3), (2,4), (3,1), (4,2), (4,3)}

Se o grafo é  simples e não orientado, não aparecem "uns" na diagonal principal e
a matriz é simétrica em relação à diagonal principal.

Exemplo:

Grafo G,

VG ={1,2,3,4}
AG ={ (3,1), (3,2), (4,2), (4,3)}

Matriz de Incidência

O Grafo é representado por uma matriz em que as colunas são as arestas do grafo e as linhas seus vértices.
Se o grafo for orientado as arestas são representadas por +1 indicando sua origem e -1 seu destino.
Exemplo:


Grafo G,

VG ={1,2,3,4}
AG ={ (1,2), (1,3), (1,3),(2,4),(4,3)}

Grafo Complementar

O Complemento de um grafo simples G, denotado por G', é o grafo simples que possui o mesmo conjunto de vértices de G, e tal que dois vértices distintos são adjacentes em G' sse não são em G.

Touro	Touro Complementar
VG = {a,b,c,d,e}	VG = {a,b,c,d,e}
AG={(a,b),(b,c),(b,d),(d,e),(c,d)}	AG={(a,e),(a,c),(c,e),(a,d),(b,e)}

 

Grafos Completos - Kn

São grafos simples em que existem arestas ligando cada par de vértices.
Existe um único grafo completo (a menos de isomorfismos) com n vértices. Denota-se esse grafo por K_n

K1	K2	K3	K4
K5	K6	K7	K8

 

É o número de arestas incidentes a v, com laços contados duas vezes.
Dado um vértice v, denotaremos o grau de v por gr(v).

Teorema da "Soma dos graus "

A soma dos graus de todos os vértices de um grafo G é duas vezes o número de arestas
  Prova: Cada aresta contribui com duas unidades para a soma do graus.

Corolário do "Número de Vértices de grau impar"

O número de vértices de grau impar é par.

Prova:

 
Sejam P e I os subconjuntos de VG com graus par e impar, respectivamente.

Seja  A= _v P gr(v) e B=_v I gr(v)

 
Pelo teorema da soma dos graus, temos que A + B = 2|AG| , e portanto A + B é par.
Mas, a soma de números pares é par, portanto A é par.
Se A + B é par e A é par, então B é par.
Para que a soma de n números ímpares seja par, n deve ser par.
Logo, o número de vértices de grau impar é par.

Obs: Note que a prova acima utiliza diversos teoremas da arimética  (Eg.: A soma de dois numeros pares é um número par, a soma de um número ímpar e um número par é ímpar, ...)

Outra Prova para o Corolário
Suponha, por absurdo, que o número de vértices de grau ímpar seja ímpar.
Sejam, g₁, g₂, ..... g_n os grafos dos vértices de grau ímpar de um grafo qualquer

Seja A=  gr(v) , somatório de i =1 até n
Como a soma de uma quantidade ímpar de números ímpares é ímpar, temos que A é ímpar

Seja B a soma dos graus dos vértices de grau par.
Como a soma de números pares é par, temos então que B é par
Como a soma de um par com um número ímpar é ímpar, temos que A + B é ímpar.

Ou seja, a soma dos graus dos vértices de G é ímpar.

Absurdo,  visto que  pelo teorema da soma dos graus, a soma dos graus de um grafo é par.

Definições Auxiliares

• denota o grau do vértice com o menor grau dentre os vértices de um grafo.
• denota o grau do vértice com o maior grau dentre os vértices de um grafo.
• Nos grafos simples |VG|, e além disto,  2m/n  ( 2m/n é o grau médio )

Grafo k-regular

É um grafo em que todos os vértices tem o mesmo grau k.
Nos grafos k-regulares, =  = k.

Teoremas:

Todo Grafo Ciclo C_n é 2-regular,
Todo Grafo com AG = é 0-regular,
Todo Grafo Completo K_n é (n-1) k-regular.
 

Grafo de Petersen (3-regular)	Grafo Cúbico (3-regular)

Teorema: Um grafo k-regular com n vértices possui n.k/2 arestas.

Prova:

 Seja G um grafo k-regular.
Pelo teorema da "soma dos graus" sabemos que a soma dos graus dos vértices de G e' 2.m /* Lembre-se que m denota o total de arestas do grafo */
Agora, como G e' k-regular, temos que todos os n vértices de G tem grau k.
Portanto, a soma dos graus dos vértices de G e' n.k
Logo,
n.k = 2.m
e
m=n.k/2
 
Corolário: K_n possui n(n-1)/2 arestas.

Prova:

No K_n todos os vértices tem grau (n-1), uma vez que cada vértice está ligado a todos os n vértice de G, com exceção dele mesmo.
Pelo teorema anterior temos que n.k = 2m.
Substituindo k por (n-1) temos que n.(n-1) = 2m
Logo, m = n(n-1)/2

SubGrafos

Um SubGrafo H = (VH,AH) de um grafo G = (VG,AG), é um grafo tal que VH  VG  e AH  AG

SubGrafo Gerado ou Induzido

Um subgrafo H de G é dito induzido de G, ou gerado por G, quando todas as arestas de AG que possuem ambos os extremos em VH estão em AH.

Denotamos esse grafos por G[VH].

Exemplo:

Dado G = ({a, b, c, d, e}, {(a, b), (b, c), (b, d), (d, e), (c, d)}).
H₁ = ({a, b, c}, {(a,b), (b, c)}) = G [a, b, c] é um subgrafo induzido de G.

 
Tomando o Touro como exemplo, podemos criar os seguintes grafos induzidos:
 

Grafo Touro	SubGrafo Gerado ou Induzido de Touro	SubGrafo Gerado ou Induzido de Touro

Teorema: Todo Grafo é  um grafo induzido dele mesmo.

SubGrafo Gerador

Um grafo gerador de G é um subgrafo H, em que VG = VH.
Todo grafo é gerador dele mesmo.
 
Exemplo de uma demonstração (prova) que utiliza o conceito de subgrafos induzidos
 
Teorema: Não existe um grafo simples com a sequência s = 1,1,3,3,3,3,5,6,8,9 de graus.

Prova:

Vamos supor por absurdo que exista tal grafo G.
Seja v₁₀ o vértice de G que possui grau 9.  (A sequência s mostra que este vértice existe).
Como o número de vértices de G é 10, v₁₀ deve ser adjacente a todos os outros vértices de G.

Seja G' = G\v₁₀ /* G menos o vértices v₁₀ */ um subgrafo induzido de G.

A sequência de Graus de G' só pode ser 0,0,2,2,2,2,4,5,7.
(Como v₁₀ estava ligado a todos os vértices, com a sua retirada, todo os vértices perdem 1 unidade em seus graus).
G' possui um vértice v com grau 7.
Portanto, 8 vértices de G' devem ter grau  1.  (Lembre-se que v é simples).

Absurdo, visto que a sequência de G' só possui 7 vértices com grau 1.

Propriedades Hereditárias

Uma propriedade é dita hereditária quando é satisfeita por um grafo G e por todos os subgrafos induzidos de G.

Exemplos: Ser um grafo Simples, Ser cordal, Completude (Ser Completo).
Não exemplos: k-regularide (ser k-regular).