Universidade Tecnológica Federal do Paraná
Professor Murilo V. G. da Silva
Notas de aula – Matemática Discreta (Aula 12)
Teoria dos Grafos
Definição: Um grafo é um par de conjuntos G = (V, E), onde V é um conjunto de vértices e E é um conjunto
de arestas, tal que:
• O conjunto de vértices V não é vazio1
• Cada aresta (ou seja, cada elemento de E) é um conjunto de 2 vértices.
Exemplo 1: G1 = (V1 , E1 ) é um grafo, onde
• V1 = {a, b, c, d, e}
• E1 = {{a, b}, {b, c}, {c, d}, {a, d}, {c, e}, {d, e}}
Exemplo 2: G2 = (V2 , E2 ) é um grafo, onde
• V1 = {1, 2, 3, 4}
• E1 = {e1 , e2 , e3 }, sendo que e1 = {1, 2}, e2 = {1, 3} e e3 = {1, 4}
Exemplo 3: H = (V, E) é um grafo, onde
• V = {v1 , v2 , v3 , v4 , v5 , v6 }
• E = {{v1 , v6 }, {v1 , v5 }, {v1 , v6 }, {v4 , v5 }, {v4 , v6 }, {v2 , v3 }}
Exemplo 3: G = (V, E) é um grafo, onde
• V = {v1 , v2 , v3 , v4 }
• E=∅
Desenho de grafos: Visto em sala de aula.
Notação: Dado G = (V, E), se e = {a, b} é uma aresta de E, então também podemos escrever de maneira
simplificada e = ab, ou seja, podemos escrever ab ∈ E(G). Por exemplo, poderı́amos escrever o conjunto de
arestas do grafo H do Exemplo 3 acima como E = {v1 v6 , v1 v5 , v3 v6 , v4 v5 , v4 v6 , v2 v3 }.
Notação: Dado um grafo G = (V, E), usaremos a notação V (G) como sinônimo para o conjunto V . De maneira
semelhante denotamos E = E(G). Isso simplifica a notação quando dizemos simplesmente “dado um grafo H”
(sem especificar o par de conjuntos) nós usamos a notação V (H) e E(H) para denotar seus vértices e arestas.
1 Podemos
também considerar o caso em que |V | = 0, mas para facilitar não vamos lidar com esse caso aqui.
1
Dado um grafo G = (V, E), definimos abaixo:
Isomorfismo: Dois grafos G1 = (V1 , E1 ) e G2 = (V2 , E2 ) são isomorfos se existe uma bijeção f : V1 → V2
respeitando: uv ∈ E1 ⇔ f (u)f (v) ∈ E2 . Se G1 e G2 são isomorfos, escrevemos G1 ∼
= G2 .
Adjacência: Dois vértices u, v ∈ V são adjacentes se uv ∈ E.
Incidência: Uma aresta e ∈ E é incidente a v ∈ V se v ∈ e.
Grau: O grau de v ∈ V é o número de arestas incidentes a v. Denotamos o grau de v por d(v).
Teorema: Seja G = (V, E) um grafo com n vértices e m arestas. Seja V = {v1 , v2 , ..., vn }. Então
n
X
d(vi ) = 2m.
i=1
Prova: Vista em sala de aula.
Teorema: Todo grafo tem um número par de vértices de grau ı́mpar.
Prova: Vista em sala de aula.
Passeio: Um passeio em um grafo G é uma sequência v1 , v2 , ..., vk (possivelmente com repetições) de vértices
de V (G) tal que se dois vértices vi , vk são consecutivos, então vi vk ∈ E(G).
Caminho: Um caminho em um grafo G é uma sequência v1 , v2 , ..., vk de vértices distintos de V (G) tal que
se dois vértices vi , vk são consecutivos, então vi vk ∈ E(G). Dado um caminho P = p1 , ..., pk , dizemos que P
conecta o vértice p1 ao vértice pk .
Ciclo: Um ciclo em um grafo G é um passeio v1 , v2 , ..., vk , com k ≥ 3 onde v1 = vk e todos os demais vértices
do passeio v2 , ..., vk−1 são distintos.
Circuito: Um circuito em um grafo G é um passeio v1 , ..., vk que contém todos os vértices de G e além disso
v1 = vk .
Arestas de um passeio: Dado um passeio P = v1 , ..., vk , dizemos que v1 v2 , v2 v3 , ..., vk−1 vk são as arestas de
P . Dizemos também que P passa por estas arestas. Definimos de maneira semelhante estes conceitos
para caminhos, ciclos e um circuitos.
Tamanho de um passeio: O tamanho de um passeio P é o número de arestas de P . O tamanho de um
caminho, de um ciclo e de um circuito é definido de maneira semelhante.
Conectividade: Um grafo G é conexo se para cada par de vértices x, y ∈ V (G), existe um caminho conectando x a y. Caso contrário, G é desconexo.
Grafos acı́clicos: Um grafo G é acı́clico se G não contém nenhum ciclo.
Árvores: Um grafo G é uma árvore se G é conexo e acı́clico.
Folhas e vértices internos: Em uma árvore T , chamamos os vértices de grau 1 de folhas e os demais vértices
de vértices internos.
Grafo Completo: Um grafo G é um grafo completo se G contém uma aresta entre cada par de vértices de
V (G). Notação: Um grafo completo com n vértices é denotado Kn .
Exercı́cio: Quantas arestas contém o K4 ? Quantas aresta contém o Kn ?
2