Estruturas Discretas - Grafos

2024/2025
Grafos não dirigidos

Um grafo não dirigido G é um par ordenado (V , E ), onde V é um

conjunto e E é um conjunto de subconjuntos de dois elementos de
V . Ou seja,
E ⊆ { {x, y } | x, y ∈ V , x ∕= y }.

Os elementos de V são chamados vértices do grafo (também

chamados nós) e os elementos de E são as arestas.

Se {x, y } ∈ E dizemos que x e y são vértices adjacentes do grafo

G.
Exemplos comuns grafos - Cliques

Definição: Um grafo com n vértices, em que cada par de vértices

está ligado, é chamado clique (ou n-clique) e é denotado por Kn .

Formalmente Kn = (V , E ), onde V = {1, . . . , n} e

E = { {i, j} | 1 ≤ i ∕= j ≤ n }.
󰀃n 󰀄
O número de arestas de Kn é 2 .

Exemplo: G = (V , E ), com V = {1, 2, 3, 4} e

E = {{1, 2}, {1, 3}, {1, 4}, {2, 3}, {2, 4}, {3, 4}}.
Exemplos comuns grafos - Caminhos

Definição: Um caminho Pn com n vértices, é o grafo

Pn = (V , E ), onde V = {1, 2, . . . , n} e
E = { {i, i + 1} | 1 ≤ i ≤ n − 1 }.

O número de arestas em Pn é n − 1. Os vértices 1 e n são

respectivamente o ı́nicio e fim de Pn .

Exemplo: G = (V , E ), com V = {1, 2, 3, 4, 5} e

E = {{1, 2}, {2, 3}, {3, 4}, {4, 5}}.
Exemplos comuns grafos - Ciclo

Definição: Um ciclo Cn com n ≥ 3 vértices é o grafo

Cn = (V , E ), onde V = {1, 2, . . . , n} e
E = { {i, i + 1} | 1 ≤ i ≤ n − 1 } ∪ {{1, n}}.

O número de arestas em Cn é n.

Exemplo: G = (V , E ), com V = {1, 2, 3, 4, 5} e

E = {{1, 2}, {2, 3}, {3, 4}, {4, 5}, {5, 1}}.

Nota: G = (V , E ), com V = {A, B, C } e

E = {{A, B}, {B, C }, {C , A}}, também é um ciclo apesar de não
seguir a definição, pois é isomorfo ao ciclo G = (V , E ), com
V = {1, 2, 3} e E = {{1, 2}, {2, 3}, {3, 1}}.
Isomorfismo entre grafos

Definição: Dois grafos G = (V , E ) e G ′ = (V ′ , E ′ ) são isomorfos

se existe uma bijecção f : V → V ′ tal que

{x, y } ∈ E se e só se {f (x), f (y )} ∈ E .

Nesse caso escrevemos G ≃ G ′ e a função f é chamada um

isomorfismo entre G e G ′ .

Identificamos grafos que sejam isomorfos como representando o

mesmo grafo.

Grafos isomorfos a cliques, caminhos e ciclos são também cliques,

caminhos e ciclos, respectivamente.
Tamanho e Grau

Definição: O número de arestas de um grafo é chamado de

tamanho do grafo. 󰀃 󰀄
Ex: O tamanho de um grafo de n vértices é no máximo n2 e
corresponde ao clique de n vértices.

Definição: O grau dG (v ) de um vértice v num grafo

G = (V , E ), é o número de vizinhos de v em G . Ou seja

dG (v ) = |{ u ∈ V | {v , u} ∈ E }|.

Um grafo diz-se regular, se para algum número k, todos os vértices

têm grau k.
Lema dos “apertos de mão”

Proposição: O número de vértices com grau ı́mpar de um grafo

é par.

Prova: Para um grafo G = (V , E ) consideremos a soma dos graus

dos seus vértices 󰁛
s= dG (v )
v ∈V

Note-se que esta soma conta cada aresta e duas vezes, uma para
cada um dos vértices adjacentes a e. Logo s = 2|E |, e portanto, s
é par.
Subtraindo a s os graus dos vértices de G com grau par, o
resultado é a soma dos graus dos vértices de grau ı́mpar, e
continua a ser par.
Subgrafos

Definição: Dado um grafo G = (V , E ):

• Um grafo G ′ = (V ′ , E ′ ) é um subgrafo de G se e só se
V ′ ⊆ V e E′ ⊆ E.

• Um grafo G ′ = (V ′ , E ′ ) é chamado de subgrafo induzido de G

se e só se V ′ ⊆ V e E ′ = { {u, v } ∈ E | u, v ∈ V ′ }.

Dado um grafo G , um caminho, ciclo, ou clique em G é um

subgrafo de G que é respectivamente um caminho, ciclo ou clique.
Conectividade

Definição: Dois vértices v e u de G dizem-se ligados se e só se

existe um caminho em G que liga u e v .

Definição: Um grafo G diz-se conexo se e só se qualquer par de

vértices em G está ligado.

Um subgrafo G ′ de G é chamado de componente conexa de G se

G ′ é conexo e não existe um grafo G ′′ , tal que G ′ ⊂ G ′′ ⊆ G que
seja conexo. Um grafo é conexo se e só se tem uma única
componente conexa.
Grafos dirigidos - digrafos

Definição: Um grafo dirigido G é um par ordenado (V , E ), onde

V é um conjunto e E é um conjunto de pares ordenados de V . Ou
seja
E ⊆ { (x, y ) | x, y ∈ V }.

Nota: Representamos uma relação binária R definida num

conjunto A pelo grafo dirigido GR = (A, R).

Para grafos dirigidos, definimos a noção de grau de entrada e grau

de saı́da de um vértice v definidos respectivamente como
|{ u ∈ V | (u, v ) ∈ E }| e |{ u ∈ V | (v , u) ∈ E }|.
Outras Noções de Grafos

Um grafo (dirigido ou não dirigido) pode ter múltiplas arestas

entre o mesmo par de vértices.

A presença de múltiplas arestas significa que as arestas passam a

ser representadas por um multiconjunto.

Um grafo com pesos é um grafo onde podemos associar pesos

(númericos) às arestas.

Quando não indicado nada em contrário usamos a designação

grafo para grafos não dirigidos (sem pesos).
Grafo Complementar e União de Grafos

Definição: Dado um grafo G = (V , E ), definimos o grafo

complementar de G , como o par (V , E ′ ), tal que uma aresta
e ′ ∈ E ′ se e só se e ′ ∈
/ E . Denotamos o grafo complementar por G .

Definição: A união de dois grafos G1 = (V1 , E1 ), G2 = (V2 , E2 ) é

o grafo com conjunto de vértices V1 ∪ V2 e conjunto de arestas
E1 ∪ E2 . A união de G1 e G2 é denotada por G1 ∪ G2 .
Percursos, Pistas e Circuitos

Definição: Dado um grafo G = (V , E ), um percurso W em G é

uma sequência W = (v1 , e1 , v2 , e2 , . . . , vn−1 , en−1 , vn ) de vértices e
arestas em G que não são necessariamente distintas e tais que
{v1 , v2 , . . . , vn } ⊆ V , {e1 , e2 , . . . , en−1 } ⊆ E , e ei = {vi , vi+1 },
para todo 1 ≤ i ≤ n − 1.

Definição: Dado um grafo G = (V , E ), uma pista é um percurso

W = (v1 , e1 , v2 , e2 , . . . , vn−1 , en−1 , vn ) em que cada aresta aparece
no máximo uma vez.

Definição: Dado um grafo G = (V , E ), um circuito é um

percurso fechado W = (v1 , e1 , v2 , e2 , . . . , vn−1 , en−1 , vn ) em que v1
e vn coincidem.
Percursos e circuitos Eulerianos

Definição: Um percurso de Euler num grafo é uma pista que

inclui todos os ramos desse grafo.

Um percurso Euleriano fechado (ou seja um circuito), é chamado

de circuito Euleriano.

Um grafo diz-se Euleriano se contém um circuito Euleriano.

Teorema: Um grafo é Euleriano se e só se é conexo e cada um

dos seus vértices tem um grau par.
Sete pontes de Königsberg

O problema é baseado na cidade de Königsberg (Prússia até 1945,

actual Kaliningrado, Rússia) que é cortada pelo Rio Pregolia e
onde há duas grandes ilhas que, juntas, formam um complexo que
na época continha sete (7) pontes.

Discutia-se nas ruas da cidade a possibilidade de atravessar todas

as pontes, sem repetir nenhuma, voltando ao ponto de partida.

Havia-se tornado uma lenda popular a possibilidade da façanha

quando Leonhard Euler, em 1736, provou que não existia caminho
que possibilitasse tais restrições.
Percursos e circuitos Hamiltoneanos

Definição: Um percurso de Hamilton (1859) num grafo é um

percurso que passa por cada vértice do grafo uma e uma só vez.

Definição: Um circuito de Hamilton é um circuito com origem e

fim no mesmo vértice e que passa por cada um dos restantes
vértices do grafo uma e uma só vez.

Serve de modelo ao “Problema do caixeiro viajante”, que tendo

que visitar várias localidades, pretende saber qual o melhor
caminho a percorrer sem passar (se possı́vel) duas vezes na mesma
localidade.

Nota: É um problema NP-completo.

Alguns grafos especiais

Recordemos:
Grafo completo de n vértices: O grafo Kn com n vértices em
que cada par de vértices está ligado.

Ciclo de n vértices: O grafo Cn = (V , E ), com n ≥ 3 vértices,

onde V = {1, 2, . . . , n} e
E = {{i, i + 1} : 1 ≤ i ≤ n − 1} ∪ {{1, n}}.

Roda de n vértices: O grafo Wn , pode ser obtido de Cn ,

adicionando um vértice adicional e ligando o novo vértice aos n
vértices de Cn .
Grafos bipartidos

Um grafo bipartido é um grafo que pode ser particionado em duas

partes tal que as arestas do grafo ligam uma parte à outra, mas
não vértices numa mesma parte.

Definição: Um grafo G = (V , E ) diz-se bipartido se e só se

existe uma partição {V1 , V2 } de V , tal que

E ⊆ { {v1 , v2 } | v1 ∈ V1 , v2 ∈ V2 }.

Os conjuntos V1 and V2 são chamados de classes de G .

O grafo C6 é um grafo bipartido e K3 não é bipartido.

Proposição: Um grafo é bipartido se e só se não tem ciclos de

tamanho ı́mpar.
Grafos bipartidos completos

Um grafo bipartido completo Km,n é um grafo que contém todas

as arestas possı́veis entre as duas classes.

Ou seja, Km,n = (V , E ), onde V = {1, 2, . . . , m + n} e

E = { {i, j} | 1 ≤ i ≤ m, m + 1 ≤ j ≤ m + n }.

O número de arestas em Km,n é mn.

Uma rede com uma topologia em estrela, pode ser representada

por um grafo bipartido completo K1,n .
Grafos planares

Definição: Um grafo é planar se e só se for possı́vel representá-lo

no plano sem que haja cruzamento de arestas.

Essa representação é chamada de representação planar do grafo.

Caminhos e ciclos são exemplos de grafos planares (assim como

árvores).

O grafo K4 é planar

O grafo K3,3 é não-planar.

A representação planar de um grafo divide o plano em regiões,

incluindo uma região não limitada.
Árvores

Definição: Uma árvore T é um grafo conexo sem ciclos.

Os grafos com apenas um vértice representam árvores

degeneradas, constituı́dos por apenas uma folha.
Numa árvore não degenerada chamamos folhas aos vértices de
grau um.

Uma árvore, juntamente com um nó especial, ao qual designamos

de raı́z, define um grafo dirigido.

Se T é uma árvore com uma raiz e v é um nó da árvore, então v é

pai dos nós u tais que (v , u) é uma aresta da árvore e filho do nó
w tal que (w , v ) é uma aresta.

Chamamos nós internos aos nós com descendentes.

Árvores
Teorema: Um grafo é uma árvore se e só se existe um único
caminho entre quaisquer dois dos seus vértices.

Prova: Vamos assumir que T é uma árvore. Então T é um grafo

conexo, sem ciclos. Sejam x e y dois vértices de T . Como T é conexo,
existe um caminho entre x e y . Se existir mais do que um caminho entre
x e y , é possı́vel combinar (partes dos) os dois caminhos de forma a
obter um ciclo em T , o que contradiz a definição de árvore. Para isso,
note que nesse caso teriamos um caminho 〈v0 = x, v1 , . . . , vk , vk+1 = y 〉
(k ≥ 1) e outro caminho 〈w0 = x, w1 , . . . , wℓ , wℓ+1 = y 〉 (ℓ ≥ 0) entre x
e y . Tomando j = min { i | vi ∕= wi (1 ≤ i ≤ k, ℓ) }, e
r = min { i | vi ∈ {wj+1 , . . . , wℓ+1 } (j ≤ i ≤ k + 1) }, e ainda
s ∈ {j + 1, . . . , ℓ + 1} tal que vr = ws , obtemos o ciclo
〈vj−1 = wj−1 , vj , . . . , vr = ws , ws−1 , . . . , wj , wj−1 = vj−1 〉.
Por outro lado, se entre quaisquer dois vértices de um grafo T existir um
(único) caminho, então T é conexo. Supondo que existe um ciclo em T
contendo dois vértices x e y , então existiriam dois caminhos entre x e y .
Logo não existem ciclos em T . Concluimos que T é uma árvore.
Árvores

Teorema: Uma árvore com n ≥ 1 vértices tem n − 1 arestas.

Prova: Por indução sobre n:

• Caso base: para n = 1, temos uma árvore com 0 arestas.
• Caso indutivo: Supomos que qualquer árvore com k vértices
tem k − 1 arestas. Seja T uma árvore com k + 1 vértices e
seja v uma folha em T .

Removendo v e a única aresta {w , v } resulta numa árvore T ′

com k vértices. Por hipótese de indução T ′ tem k − 1 arestas.
Logo T tem k arestas, pois tem uma aresta mais que T , que
é a aresta {w , v }.