Teoria dos Grafos

Resumo pós Greve

Prof. Oberlan C. Romão

Departamento de Computação e Eletrônica – DCE

Centro Universitário Norte do Espírito Santo – CEUNES
Universidade Federal do Espírito Santo
Conceitos Básicos
Definições básicas

Grafos
Um grafo G = (V, E) é definido por um conjunto finito e não vazio V de
vértices e um conjunto E de arestas, em que cada aresta e ∈ E é
definida por um par não-ordenado de vértices (u, v), sendo ambos u e
v∈V

1
Definições básicas

• A ordem de um grafo G = (V, E) é a cardinalidade de V ;

• O tamanho do grafo representa a cardinalidade do conjunto E;
• Um grafo trivial é aquele com um único vértice (n = 1) e nenhuma
aresta (m = 0);
• Um grafo nulo é um grafo que não possui arestas, ou seja, E(G) = ∅
(isto é, m = 0)

2
Definições básicas

• Seja e = uv uma aresta de um grafo G. Dizemos que os vértices u e v

são vizinhos e que são vértices adjacentes;
• Arestas com um extremo em comum, i.e., arestas com interseção em
um vértice, são ditas adjacentes;
• A vizinhança de um vértice v ∈ V , denotada por N (v), é o conjunto
de todos os vértices adjacentes a v em G;
• Arestas que possuem os mesmos extremos são chamadas de arestas
múltiplas;
• Arestas cujos dois extremos são o mesmo vértice, são chamadas de
laço (ou loop);

3
Definições básicas

• Grafos simples são grafos que não possuem laços nem arestas
múltiplas.
• Grafos com arestas paralelas e/ou loops são comumente chamados de
multigrafos.

4
Definições básicas

• O grau de um vértice v, denotado por dG (v), é o número de arestas

que incidem em v, onde os laços são contados duas vezes;
• Em um grafo simples, o grau de um vértice é igual ao número de
vizinhos que ele possui, isto é, d(v) = |N (v)|;
• Um vértice de grau zero é chamado isolado (não possui vizinhos, ou
seja, N (v) = ∅);
• Um vértice v é universal quando está conectado por arestas a todos
os demais vértices, isto é, N (v) = V (G) \ v.

5
Definições básicas

• O grau mínimo de um grafo G, denotado por δ(G), é o menor grau

dentre todos os vértices de G, i.e.,

δ(G) = min{d(v) : v ∈ V (G)}.

• O grau máximo de G, denotado por ∆(G), é o maior grau dentre

todos os vértices de G, i.e.,

∆(G) = max{d(v) : v ∈ V (G)}.

6
Definições básicas

Teorema
Em qualquer grafo simples G temos que v∈V (G) d(v) = 2m. Ou seja, a
P

soma dos graus dos vértices de um grafo é igual ao dobro do número de

suas arestas.

7
Definições básicas

Teorema
Em qualquer grafo simples G temos que v∈V (G) d(v) = 2m. Ou seja, a
P

soma dos graus dos vértices de um grafo é igual ao dobro do número de

suas arestas.

Corolário
Todo grafo tem uma quantidade par de vértices de grau ímpar.

7
Subgrafo
Subgrafo

Subgrafo
Um grafo H é subgrafo de um grafo G se H contém alguns vértices e
arestas G, ou seja, V (H) ⊆ V (G) e E(H) ⊆ E(G).

• Dizemos também que G contém H ou que H está contido em G ou

que G é um supergrafo de H, e escrevemos H ⊆ G para denotar essa
relação.
• Um subgrafo próprio H de G é um subgrafo de G tal que
V (H) ̸= V (G) ou E(H) ̸= E(G) e escrevemos H ⊂ G.

8
Subgrafo

• H é um subgrafo gerador de G se H ⊆ G e V (H) = V (G), ou seja,

H contém todos os vértices, mas não necessariamente todas as arestas
de G;
• Dado um conjunto de vértices X ⊆ V (G) de um grafo G, o subgrafo
de G induzido por X, denotado G[X], é o subgrafo H de G tal que
V (H) = X e E(H) é o conjunto de arestas de G com os dois
extremos em X;
• Similarmente, se F é um subconjunto de arestas de G, então o
subgrafo de G induzido por F , denotado por G[F ], é o subgrafo H
de G tal que E(H) = F e V (H) é o conjunto de vértices de G que
são extremos de alguma aresta de F .

9
Passeios, trilhas, caminhos e ciclos
Passeios, trilhas, caminhos e ciclos

Passeio
Um passeio é uma sequência de vértices tal que existe uma aresta entre
vértices consecutivos, onde pode haver repetição de vértices e arestas.

• Um passeio fechado começa e termina no mesmo vértice;

• Caso contrário, o passeio é aberto;
• O comprimento de um passeio P é a quantidade de arestas de P .

Trilha
Uma trilha é um passeio sem arestas repetidas (pode haver repetição de
vértices).

• Uma trilha fechada ou circuito começa e termina no mesmo vértice;

• Caso contrário, é uma trilha aberta.

10
Passeios, trilhas, caminhos e ciclos

Caminho
Um caminho é um passeio sem vértices repetidos.

• Como não há repetição de vértices, não há repetição de arestas;

• Portanto, todo caminho é uma trilha (mas nem toda trilha é um
caminho).

Ciclo
Um ciclo é um caminho fechado, isto é, um caminho que começa e
termina no mesmo vértice. Assim, os ciclos não podem repetir arestas ou
vértices (exceto pelos vértices inicial e final).

• Um ciclo com n vértices é denotado Cn ;

• Um ciclo é par (resp. ímpar) se possui uma quantidade par (resp.
ímpar) de vértices.
11
Distância, diâmetro, cintura e circunferência

• A distância entre um par de vértices u, v de um grafo G, denotada

por distG (u, v), é o o comprimento do caminho mais curto de u a v;
• O diâmetro de G, denotado por diam(G), é a maior das distâncias
entre todos os pares de vértices de G, i.e.,
diam(G) = max{distG (u, v) : u, v ∈ V (G)}
• A cintura de um grafo G, denotado por cint(G), que é a quantidade
de arestas do menor ciclo de G;
• A circunferência de um grafo é o comprimento de um maior ciclo do
grafo.
• Se G não tem ciclos, então definimos cint(G) = ∞ e a circunferência
como sendo zero.

12
Isomorfismo
Isomorfismo

Isomorfismo
Sejam G e H dois grafos simples. Dizemos que G é isomorfo a H, e
escrevemos G ∼
= H, se existe uma função bijetora f : V (G) → V (H) que
satisfaça:

uv ∈ E(G) ⇔ f (u)f (v) ∈ E(H) para todo u, v ∈ V (G).

• Em outras palavras, dois grafos G e H são isomorfos se H puder ser

obtido renomeando-se os vértices de G;

13
Isomorfismo

• Decidir se dois grafos são ou não isomorfos é uma tarefa

computacionalmente cara;
• Como saber se dois grafos são isomorfos?

14
Isomorfismo

• Decidir se dois grafos são ou não isomorfos é uma tarefa

computacionalmente cara;
• Como saber se dois grafos são isomorfos?
• Algumas condições necessárias:
• Mesma quantidade de vértices;
• Mesma quantidade de arestas;
• Mesma quantidade de vértices com um mesmo grau;
• Ambos possuem ou não um ciclo de comprimento k.
Essas condições são suficientes?

14
Complemento
Complemento

Complemento
Se G é um grafo simples, o complemento de G, denotado por Ḡ é um
grafos simples com V (Ḡ) = V (G), sendo que dois vértices são adjacentes
em Ḡ se e somente se eles não são adjacentes em G, i.e.,
(u, v) ∈ E(Ḡ) ↔ (u, v) ∈
/ E(Ḡ).

• Um grafo simples é auto-complementar se é isomorfo ao seu

complemento.

15
Tipos Especiais de Grafos
Tipos Especiais de Grafos

Grafos Simples
Um grafo é simples se não tem laços e nem arestas múltiplas.

• Um grafo simples com apenas um vértice é chamado trivial.

• Um grafo com n vértices é nulo, denotado por Nn , quando todos os
seus vértices são isolados, ou seja, não possui arestas.

Grafos Regulares
Um grafo simples é k-regular se todos os seus vértices têm grau k. O
grafo G é regular se é k-regular para algum k.

16
Tipos Especiais de Grafos

Grafos Completos
Um grafo completo é um grafo simples em que quaisquer dois de seus
vértices distintos são adjacentes, ou seja, todos os seus vértices são
universais.

• Um grafo completo com n vértices é denotado por Kn ;

• Um grafo completo com 3 vértices (K3 ) é chamado de triângulo;
• Note que o grafo completo Kn é (n − 1)-regular e possui n2 arestas.

17
Tipos Especiais de Grafos

Clique
Um subconjunto de vértices X onde todos os pares de vértices em X são
adjacentes é chamado de clique.

• O conjunto de vértices de um grafo completo é uma clique;

• Um único vértice já é uma clique, então sempre é interessante
encontrar cliques máximas;
• Denotamos por ω(G) a cardinalidade de uma clique máxima em G.

18
Conjunto Independente
Conjunto Independente

Conjunto Independente
Um conjunto independente ou conjunto estável de um grafo G é um
conjunto de vértices X tal que o subgrafo de G induzido por X não
contém nenhuma aresta (será um grafo nulo).

• Um conjunto independente é máximo se tem a maior quantidade de

vértices dentre todos os conjuntos independentes de um grafo G;
• Denotamos por α(G) a quantidade de vértices em um conjunto
independente máximo de um grafo G.

19
Maximalidade e Minimalidade
Maximalidade e Minimalidade

• Um subgrafo H de G é dito maximal (resp. minimal) com respeito a

uma propriedade P se H possui a propriedade P e não existe H ′
satisfazendo P tal que H ⊂ H ′ (resp. H ′ ⊂ H);
• Um subgrafo H = (V (H), E(H)) de G é máximo (resp. mínimo)
com relação a uma propriedade P se, dentre todos os subgrafos H ′ de
G maximais (resp. minimais) com relação a propriedade P,
|V (H)| ≥ |V (H ′ )| (resp. |V (H)| ≤ |V (H ′ )|).

Todo conjunto máximo é também maximal, mas nem todo conjunto

maximal é máximo.

20
Maximalidade e Minimalidade

Os conjuntos de vértices S1 = {u, w, y} e S2 = {a, u, y, w} são ambos

conjuntos independentes maximais de G abaixo, mas apenas S2 é um
conjunto independente máximo de G.

21
Maximalidade e Minimalidade

Nos grafos abaixo temos um exemplo de conjunto independente maximal e

máximo

22
Grafos Bipartidos
Grafos Bipartidos

Grafo Bipartido
Um grafo G é bipartido se V (G) pode ser particionado em dois
conjuntos X e Y (X ∪ Y = V (G) e X ∩ Y = ∅) tais que X e Y são
conjuntos independentes, ou seja, toda aresta de G tem um extremo em
X e outro em Y .

• Note que a definição de grafo bipartido implica em nunca haver arestas

entre vértices dos conjuntos X e Y .

23
Grafos Bipartidos

Grafo Bipartido Completo

Um grafo bipartido completo é um grafo simples com bipartição (X, Y ),
no qual cada vértice de X é adjacente a cada vértice de Y .

• Se |X| = p e |Y | = q então um tal grafo é denotado por Kp,q .

24
Grafos Conexos
Grafos Conexos

Grafo Conexo
Um grafo é conexo se para todo par de vértices distintos u, v existe um
caminho de u a v.

• Um grafo que não é conexo é dito desconexo.

• Uma componente conexa de um grafo G é um subgrafo conexo

maximal de G.
• Denotamos por w(G) o número de componentes conexas de G.
• Naturalmente, G é conexo se e somente se w(G) = 1.

Proposição
Seja G um grafo simples com n vértices e δ(G) ≥ n2 . Então, G é conexo.

25
Grafos Conexos

• Uma aresta e de um grafo G é uma aresta de corte (ou ponte) se

sua remoção de G gera um grafo G′ com mais componentes conexas
que G.
• Um vértice v de G é um vértice de corte se sua remoção de G
(juntamente com as arestas a ele conectadas) gera um grafo G′ com
mais componentes conexas que G.

26
Grafos Direcionados
Grafos Direcionados

Grafo Direcionado
Um grafo direcionado (ou digrafo) é um grafo onde cada uma das
arestas (neste caso, comumente, chamadas de arcos) são direcionadas.

• Cada aresta direcionada (v, w) possui uma única direção: de v para w.

27
Grafos Direcionados

• O grau de saída, d+ (v), de um vértice num digrafo é o número de

arcos que saem do vértice;
• O grau de entrada, d− (v), é o número de arcos que entram no
vértice;
• Uma fonte é um vértice que tem grau de entrada nulo;
• Um sumidouro é um vértice que tem grau de saída nulo;
• Um digrafo D é dito balanceado se d+ (vi ) = d− (vi ) para todo
vi ∈ V (D).
• Um digrafo é regular se existe um inteiro k tal que
d+ (vi ) = d− (vi ) = k para todo vi ∈ V (D). Dizemos que o digrafo é
k-regular.

28
Grafos Direcionados

• Em um digrafo, duas arestas sao paralelas se elas incidem nos mesmos

vértices e possuem a mesma orientação;
• O grafo associado a um digrafo D é o grafo obtido desconsiderando
a orientação de D;
• Dois digrafos são isomorfos quando os grafos assoados são isomorfos e,
além disso, a orientação das arestas coincidem.

29
Grafos Direcionados

Tipos de Digrafos
• Simples: se não possui loops e arestas paralelas;
• Balanceado: se d+ (v) = d− (v) para todo v ∈ V (D);
• Regular: se existe um inteiro k tal que d+ (v) = d− (v) = k para todo
v ∈ V (D).

30
Grafos Direcionados

• Um vértice de um digrafo é fortemente ligado a outro se um está ao

alcance de outro e vice-versa;
• Um digrafo D é fortemente conexo se cada um de seus vértices está
fortemente ligado a todos os outros;
• Um digrafo D é fracamente conexo se o grafo associado é conexo,
mas D não é fortemente conexo.

31
Grafos Ponderados
Grafos Ponderados (Valorado)

Grafo Ponderado
Um grafo ponderado (ou valorado) é um grafo (dirigido ou não
dirigido) no qual cada uma de suas arestas está associada a um valor
numérico chamado peso ou custo da aresta.

O custo de uma aresta pode representar:

• Distância;
• Custo monetário;
• Tempo;
• etc.

32