Fundamentos de matemática:
Introdução à Teoria de Grafos
∗
Prof. Renato Mello, 07 de maio de 2012
1 Noção intuitiva
Informalmente, podemos pensar em um grafo como sendo um conjunto de pontos e
de linhas ligando alguns desses pontos entre si. Não interessa, no entanto, a posição dos
pontos ou o caminho que cada linha percorre ao ligá-los, apenas a informação de quais
pontos estão ligados e quais não estão. Dessa maneira, as três guras abaixo representam
o mesmo grafo.
Fig. 1:
Representações planas distintas de um mesmo grafo.
Os pontos são chamados de vértices (ou nós) e as linhas, de arestas (ou arcos).
Assim, o grafo acima representado possui 7 pontos e 9 arestas.
Muitas vezes é útil acrescentar informações ao grafo. Podem-se estabelecer sentidos
nas arestas, permitir que haja mais de uma aresta ligando o mesmo par de vértices, ou
mesmo que uma aresta ligue um vértice a si mesmo, conforme ilustram as guras abaixo.
Fig. 2:
Representações planas de grafos não-simples. Da esquerda para a direita: grafo
dirigido, multigrafo simples, multigrafo com laços, multigrafo direcionado com
laços.
Grafos em que nada disso acontece são chamados de grafo simples e serão nosso
próximo objeto de estudo.
∗
Versão 1.00
1
2 Denições básicas
2
2 Denições básicas
Dado um conjunto A, o conjunto das partes de A, denotado por P(A), é formado
por todos os subcunjuntos de A, isto é, P(A) = {S | S ⊂ A}. Denotaremos por A(2) o
conjunto formado por todos os subconjuntos de A que têm exatamente 2 elementos, isto
é,
n
o
A(2) = S ∈ P(A) |S| = 2
ou, equivalentemente,
n
o
A(2) = {a, b} a, b ∈ A, a 6= b .
Veja que esse conjunto difere do produto cartesiano A2 = A × A = (a, b) | a, b ∈ A , pois
neste último a ordem dos elementos a, b importa e pode-se ter a = b.
Agora podemos estabelecer a seguinte denição.
Definição 2.1. Um grafo simples é um par ordenado G = (V, A), em que V
é um
conjunto nito e A é um subconjunto de V (2) . Os elementos de V são chamados de
vértices de G e os elementos de A, de arestas de G.
Dessa forma, as arestas são pares não-ordenados {a, b} de elementos distintos de V . A
noção intuitiva é que arestas conectam dois vértices distintos, sem estabelecer um sentido
de conexão. Dizemos que dois vértices v, w são adjacentes (ou vizinhos) se {v, w} ∈ A.
Se a ∈ A e a = {v, w}, dizemos que a incide sobre v . Duas arestas distintas são ditas
adjacentes se incidirem sobre um mesmo vértice.
É comum denotar por V (G) e A(G) os conjuntos de vértices e de arestas de um grafo
G. Assim, se G1 = (V1 , A1 ) e G2 = (V2 , A2 ) são grafos, podemos escrever V (G1 ) = V1 ,
V (G2 ) = V2 , A(G1 ) = A1 e A(G2 ) = A2 . Denotaremos também por n(G) e m(G),
respectivamente, o número de vértices e o número de arestas de G, ou seja, n(G) = |V (G)|
e n(G) = |A(G)|.
Observações. 1. Veja que não há nenhuma referência a objetos geométricos na denição,
portanto as guras encontradas neste texto são apenas representações planas dos grafos.
O grafo simples é um objeto puramente combinatório.
2. Enquanto não estudarmos novos tipos de grafos, a palavra grafo signicará grafo simples, exceto quando dito o contrário.
Exemplo 2.1. Sejam V = {1, 2, 3, 4}, A = {1, 2}, {1, 3} e G = (V, A). Então todas
as armações abaixo são verdadeiras:
• G é um grafo simples;
• 1, 2, 3 e 4 são os vértices de G;
• {1, 2} e {1, 3} são as arestas de G;
• {1, 4}, {2, 3}, {2, 4} e {3, 4} não são arestas de G;
• 1 e 2 são vizinhos;
• {1, 2} incide sobre 1;
• A Figura 3 é uma representação plana de G.
3 Grau, conexidade e tipos especiais de grafos
Fig. 3:
3
Representação plana do grafo do Exemplo 2.1.
É comum usar a notação vw para a aresta que incide sobre os vértices v e w. Assim,
em um exemplo como acima, podemos reescrever as arestas {1, 2} e {1, 3} como 11 e 13
(lê-se um, um e um, três ), se isso não causar confusão.
3 Grau, conexidade e tipos especiais de grafos
Veja que, no Exemplo 2.1, nem todas os elementos de V (2) são arestas do grafo, isto é,
nem todos os pares de vértices são adjacentes. Quando, em um grafo simples, quaisquer
dois vértices são adjacentes, dizemos que o grafo é um grafo completo e o denotamos por
Kn , em que n é o número de vértices. Reversamente, grafo nulo é todo aquele que não
possui nenhuma aresta e é denotado por Nn , assim . Assim, A(Kn ) = V (2) e A(Nn ) = ∅.
Fig. 4:
Grafos completos: K3 , K4 e K5 .
O complemento de um grafo G = (V, A) é aquele cujos vértices são os vértices de
G e cujas arestas são os pares de vértices que não são adjacentes em G. Denotamos G e,
por denição, temos V (G) = V e A(G) = V (2) − A. Assim, v ∈ V (G) ⇐⇒ v ∈ V (G) e
vw ∈ A(G) ⇐⇒ vw 6∈ V (G). O grau de um vértice no grafo G é o número de arestas
que sobre ele incidem e denota-se dG (v) ou simplesmente d(v). Sibolicamente,
d(v) = #{a ∈ A(G) | v ∈ a}.
Assim, no Exemplo 2.1, d(1) = 2, d(2) = d(3) = 1 e d(4) = 0. Um grafo em que todos
os vértices têm o mesmo grau é chamado de grafo regular. Evidentemente, o grau de
qualquer vértice em Kn é n − 1 e o grau de qualquer vértice em Nn é 0, portanto os grafos
completos e os grafos nulos são exemplos de grafos regulares. Outros exemplos são os
ciclos, que são os grafos cujas arestas formam uma única cadeia circular. Denotamos por
Cn um grafo circular de n vértices (n ≥ 3) e portanto, n arestas. Teremos
V (Cn ) = {v1 , v2 , . . . , vn };
A(Cn ) = {v1 v2 , v2 v3 , . . . , vn−1 vn , vn v1 }.
É claro que d(v) = 2 para todo v ∈ V (Cn ), logo todo ciclo é um grafo regular.
4 Quadro-resumo
4
4 Quadro-resumo
Conceito/notação
|A| ou #A
P(A)
A(2)
Signicado
Número de elementos do conjunto A.
Conjunto das partes de A.
Conjunto dos pares não-ordenados de elementos de A.
Grafo simples
Grafo não dirigido, sem laços e sem arestas múltiplas.
Grafo dirigido (digrafo) Grafo com arestas dirigidas.
Multigrafo
Grafo com arestas múltiplas.
Laço
Aresta ligando um vértice a si mesmo.
V (G)
Conjunto dos vértices de G.
A(G)
Conjunto das arestas de G.
n(G)
Número de vértices de G.
m(G)
Número de arestas de G.
dG (v) ou d(v)
Grau do vértice v no grafo G.
Kn
Grafo completo de n vértices.
Nn
Grafo nulo de n vértices.
Cn
Ciclo de n vértices.