GGI026 - Algoritmos e programação
Lista de exercı́cios 2 - Grafos
• Escreva a matriz e listas de adjacências para descrever o grafo a seguir:
1
2
3
5
4
7
6
• Desenhe o grafo e escreva a matriz de adjacência que correspondem ao grafo
a seguir.
1: 3, 5, 7
2: 4
3: 1, 6, 8
4: 2
5: 1, 6
6: 3, 5
7: 1
8: 3
• Identifique cada vértice no grafo abaixo com o seu grau.
1
2
4
6
3
5
7
8
1
1. Um grafo simples G é um conjunto V de vértices e um conjunto E de
arestas, onde cada aresta é um conjunto de dois vértices. Um subgrafo G0
de um grafo G é um grafo cujos vértices V 0 é um subjconjunto de V e cujo
conjunto de arestas E 0 é um subconjunto de E.
2. Uma aresta pode ser pensada como uma conexão entre dois vértices; dois
vértices são adjacentes existe uma aresta conectando-os.
3. Descrições de grafos - nós vimos os 3 métodos a seguir:
• Pictoricamente: vértices são cı́culos e arestas são as linhas que os
conectam. Essa pode ser uma descrição útil para descrição informal e
visualização de casos mais simples.
1
2
3
4
5
• Listas de adjacência: Para cada vértice, listar os vértices adjacentes
a ele. Buscar pela existência de uma aresta é uma operação de complexidade O(n). Exercı́cio: Explique porque a complexidade é O(n)¿
1: 2, 4, 5
2: 1, 3, 4
3: 2, 4
4: 1, 2, 3, 5
5: 1, 4
• Matriz de adjacência: O grafo é representado por uma matriz com
n × n elementos, onde ai,j = 1 se e somente se existe uma aresta entre
o vértice i e vértice j, senão ai,j = 0. Uma matriz de adjacência para
um grafo não direcionado é sempre simétrica, uma vez que uma aresta
conectando i e j também conecta j e i.
• Exercı́cio: verificar a existência de uma aresta é O(1), porquê? Qual
método usa mais espaço, listas de adjacência ou matriz de adjacência
e porquê?


0 1 0 1 1
1 0 1 1 0 


0 1 0 1 0 


1 1 1 0 1 
1 0 0 1 0
2
4. O grau de um vértice v é o número de arestas incidindo em v. De maneira
equivalente, o grau de v é igual ao número de vértices adjacentes a v.
5. um isomorfismo entre dois grafos G1 = (V1 , E1 ) e G2 = (V2 , E2 ) é uma
bijeção f : V1 → V2 tal que cada aresta (v, w) que pertence ao conjunto E1
se e somente se a conexão (f (v), f (w)) pertence a E2 . Informalmente, um
isomorfismo entre dois grafos é uma maneira de renomear os vértices de um
grafo para corresponder a outro.
6. Propriedades de um grafo preservadas em um isomorfismo:
• Número de vértices - V1 e V2 têm o mesmo tamanho
• Número de arestas - E1 e E2 têm o mesmo tamanho
• Adjacência - v, w são adjacentes em G se e somente se f (v), f (w) são
adjacentes em G0 .
• Grau de vértices - v em V1 e f (v) em V2 tem o mesmo grau
7. Exercı́cio: escreva um algoritmo que verifique se dois grafos G1 e G2 não
são isomorfos com base no número de vértices e arestas e, também, comparando a lista ordenada dos graus de seus vértices.
8. Um caminho é uma sequência de vértices v0 , ..., vk tal que quaisquer dois
vértices consecutivos são conectados por uma aresta. O caminho inicia em
v0 e termina em vk . O tamanho do caminho é k, e vértices podem ser
inclusos no caminho mais de um vez.
1
2
3
Um exemplo de caminho de tamanho 3:
(5)-(1)-(2)-(3)
4
5
9. Um ciclo é um caminho que inicia e termina no mesmo vértice. Um ciclo
simples é um ciclo em que cada vértice aparece apenas uma vez, exceto o
vértice inicial e final. Um grafo que não contém um ciclo é denominado
acı́clico.
10. Exercı́cio: escreva um algoritmo que recebe um caminho e verifica se ele
é um ciclo
11. Exercı́cio: escreva um algoritmo que recebe um caminho e verifica se ele
é um ciclo simples
3
12. Exercı́cio: escreva um algoritmo que recebe um grafo e verifica se ele é
acı́clico. Dica: verifique se ao caminhar em um grafo, eventualmente seria
possı́vel visitar um vértice duas vezes.
1
2
3
Um exemplo de um
ciclo simples de
comprimento 4:
(1)-(2)-(4)-(5)-(1)
4
5
13. Dois vértices em um grafo são conectados se existe um caminho que inicia
em um vértice e termina no outro. Um componente conectado é um subconjunto de vértices de um grafo G que são todos conectados a um vértice
arbitrário. Um grafo é conectado se quaisquer dois vértices no grafo são
conectados por um caminho.
4
14. Grafos especiais - Alguns tipos de grafos ocorrem frequentemente e tem
nomes especı́ficos
• Kn , o grafo completo de n vértices, tem uma aresta entre cada um dos
n vértices
• Exercı́cio: escreva um algoritmo para verificar se um dado grafo G é
um grafo Kn
2
3
K4
1
4
• En , um grafo vazio de n vértices, não tem nenhuma aresta em qualquer
um dos n vértices
• Exercı́cio: escreva um algoritmo para verificar se um dado grafo é
um En
2
3
E4
1
4
• Cn , o grafo de ciclo simples de n vértices, é um grafo composto de um
ciclo único com n vértices
• Exercı́cio: escreva um algoritmo que verifique se um dado grafo g
possui um dado ciclo c
2
3
C4
1
4
5
Outros exercı́cios
1. Determine quais dos dois dos três grafos a seguir são isomórifcos e escreva
a equivalência entre vértices que os torna isomorfos
3
4
5
2
(a)
(b)
1
A
C
E
B
D
β
δ
γ
α
(c)
2. Explique porque um isomorfismo preserva as quatro propriedades anteriormente mencionadas (i.e. número de vértices, número de arestas, adjacência
e grau de vértices)
6
3. Explique porque em todo grafo a soma de graus de vértices é igual ao dobro
do número de arestas
7
1. (a) Explique porque o número de arestas em um Kn , o grafo completo
com n vértices, é n(n−1)
.
2
(b) Explique porque os dois grafos a seguir NÃO são isomorfos.
6
4
5
2
3
1
i.
F
D
E
B
C
A
ii.
(c) Escreva pelo menos dois isomorfismo entre os dois grafos a seguir:
4
5
2
3
1
i.
ii.
D
E
B
C
A
8
1. Um circuito euleriano de um grafo é um caminho que passa por toda aresta
em um grafo exatamento uma vez. Explique porque, em um grafo com um
circuito euleriano, todo vértice tem grau par.
1
2
1o
.
6o.
4o.
3o.
3
2o.
4
Um exemplo de
circuito euleriano
iniciando em (2)
5o.
5
2. Dado um grafo G com um conjunto de vértices V e arestas E, a coloração
de um grafo com n cores G é a atribuição de n cores aos vértices tais que
nenhum par de vértices adjacentes tem a mesma cor. Formalmente, uma
coloração é uma função C : V → {1, 2, ..., n} tal que ∀e = {v1 , v2 } ∈ E,
C(v1 ) 6= C(v2 ). O número cromática de um grafo G, denotado χ(G), é o
número mı́nimo de cores necessárias para colorir um grafo. Determine e
explique a minimalidade de χ(G) para os grafos a seguir:
(a) En
(b) Kn
(c) Cn
9