View
2
Download
0
Category
Preview:
Citation preview
BCC204 - Teoria dos Grafos
Marco Antonio M. Carvalho
(baseado nas notas de aula do prof. Haroldo Gambini Santos)Departamento de Computação
Instituto de Ciências Exatas e BiológicasUniversidade Federal de Ouro Preto
9 de março de 2020
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 1 / 26
Avisos
Site da disciplina:I http://www.decom.ufop.br/marco/
Lista de e-mails:I bcc204@googlegroups.com
Para solicitar acesso:I http://groups.google.com/group/bcc204
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 2 / 26
Avisos
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 3 / 26
Conteúdo
1 Isomorfismo
2 Subgrafos
3 Conectividade e Caminhos
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 4 / 26
Exercício
1 Com relação ao grafo abaixo, responda:
v3
v4
v5v7
v6
v2v1
a O grafo é simples?b Completo?c Regular?d Conexo?e Encontre dois caminhos diferentes entre v3 e v6.f Indique uma aresta cuja remoção tornará o grafo desconexo.g Indique a representação deste grafo por listas de adjacências.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 5 / 26
Isomorfismo
DefiniçãoDois grafos G e H são ditos isomorfos se existir uma correspondênciaum-para-um entre seus vértices e entre suas arestas, de maneira que asrelações de incidência são preservadas.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 6 / 26
Isomorfismo
Condições necessárias mas não suficientes para isomorfismoI Mesmo número de vértices;I Mesmo número de arestas;I Mesmo número de componentes;I Mesmo número de vértices com o mesmo grau.
Exemplo:
a b c
d
e f
5
61 2 3 4
Observação: Não existem algoritmos comprovadamente eficientes paradeterminar se dois grafos são isomorfos.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 7 / 26
Isomorfismo
ComplexidadeO algoritmo intuitivo para testes de isomorfismo consiste em analisar aspermutações de linhas e colunas de matrizes de equivalência, em busca de umarelação um-para-um, ou seja, O(n!).
Em outubro de 2015, Lászó Babai, da Universidade de Chicago, anunciou umalgoritmo quasipolinomiala para o teste de isomorfismo!b
Em 4 de janeiro de 2017, foi descoberto um erro na prova, reclassificando oalgoritmo como subexponencialc.
Em 9 de janeiro de 2017, o erro na prova foi anunciado como contornadod.
aMais lento que polinomial, mas significativamente mais rápido queexponencial.
bhttps://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/
cMais lento que quasipolinomial, mas mais rápido que exponencial.dhttp://people.cs.uchicago.edu/~laci/update.html
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 8 / 26
Exercícios
1 Encontre um grafo com 4 vértices que seja isomorfo a seucomplemento (ou seja, auto-complementar).
2 Qual o número de arestas de um grafo que é isomorfo a seucomplemento?
3 Qual grafo é diferente dos demais?
(a)(b)
(c) (d) (e)
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 9 / 26
Isomorfismo
Algoritmo BásicoI Verificar todas as seguintes propriedades:
I mesmo número de vértices;I mesmo número de arestas;I mesmo número de componentes;I mesmo número de vértices com o mesmo grau.
I Em seguida efetuar a combinação das matrizes de adjacência dosgrafos, verificando se são semelhantes.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 10 / 26
Isomorfismo e Matrizes de Adjacência
a b
de c
a b c d ea 0 1 0 1 1b 1 0 1 1 1c 0 1 0 1 0d 1 1 1 0 1e 1 1 0 1 0
1 2
4
5 3
1 2 3 4 51 0 0 1 1 12 0 0 1 0 13 1 1 0 1 14 1 0 1 0 15 1 1 1 1 0
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 11 / 26
Isomorfismo e Matrizes de Adjacência
a b
de c
a b c d ea 0 1 0 1 1b 1 0 1 1 1c 0 1 0 1 0d 1 1 1 0 1e 1 1 0 1 0
1 2
4
5 3
1 5 2 3 41 0 1 0 1 15 1 0 1 1 12 0 1 0 1 03 1 1 1 0 14 1 1 0 1 0
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 11 / 26
Subgrafo
DefiniçãoUm grafo Gs = (Vs , As) é dito ser um subgrafo de um grafo G = (V, A)se todos os vértices e todas as arestas de Gs estão em G , ou seja, seVs ⊆ V e As ⊆ A.
Observações:I Todo grafo é subgrafo de si próprio;I O subgrafo Gs2 de um subgrafo Gs de G também é subgrafo de G ;I Um vértice simples de G é um subgrafo de G ;I Uma aresta simples de G (juntamente com suas extremidades) é um
subgrafo de G .
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 12 / 26
Subgrafo
Encontre todos os subgrafos.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 13 / 26
Definições
1 2
3
5
4
a
b c
d
e
PasseioUm passeio é uma sequência finita de vértices earestas.
Cada vértice da sequência é incidente a arestaque o precede e a aresta seguinte.
Essa sequência deve acabar e iniciar em umvértice (não necessariamente os mesmos).
Ex.: 1 - a - 2 - c - 3 - d - 4 - d - 3 - e - 5ou: 1 - 2 - 3 - 4 - 3 - 5
O passeio pode ser:
Aberto : quando inicia e acaba emvértices diferentes (o caso acima).
Fechado : quando inicia e acaba no mesmovértice. Ex.: 1-2-3-4-3-5-3-1.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 14 / 26
Definições
1 2
3
5
4
a
b c
d
e
PasseioUm passeio é uma sequência finita de vértices earestas.
Cada vértice da sequência é incidente a arestaque o precede e a aresta seguinte.
Essa sequência deve acabar e iniciar em umvértice (não necessariamente os mesmos).
Ex.: 1 - a - 2 - c - 3 - d - 4 - d - 3 - e - 5ou: 1 - 2 - 3 - 4 - 3 - 5
O passeio pode ser:
Aberto : quando inicia e acaba emvértices diferentes (o caso acima).
Fechado : quando inicia e acaba no mesmovértice. Ex.: 1-2-3-4-3-5-3-1.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 14 / 26
Definições
1 2
3
5
4
a
b c
d
e
PasseioUm passeio é uma sequência finita de vértices earestas.
Cada vértice da sequência é incidente a arestaque o precede e a aresta seguinte.
Essa sequência deve acabar e iniciar em umvértice (não necessariamente os mesmos).
Ex.: 1 - a - 2 - c - 3 - d - 4 - d - 3 - e - 5ou: 1 - 2 - 3 - 4 - 3 - 5
O passeio pode ser:
Aberto : quando inicia e acaba emvértices diferentes (o caso acima).
Fechado : quando inicia e acaba no mesmovértice. Ex.: 1-2-3-4-3-5-3-1.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 14 / 26
Definições
1 2
3
5
4
a
b c
d
e
PasseioUm passeio é uma sequência finita de vértices earestas.
Cada vértice da sequência é incidente a arestaque o precede e a aresta seguinte.
Essa sequência deve acabar e iniciar em umvértice (não necessariamente os mesmos).
Ex.: 1 - a - 2 - c - 3 - d - 4 - d - 3 - e - 5ou: 1 - 2 - 3 - 4 - 3 - 5
O passeio pode ser:
Aberto : quando inicia e acaba emvértices diferentes (o caso acima).
Fechado : quando inicia e acaba no mesmovértice. Ex.: 1-2-3-4-3-5-3-1.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 14 / 26
Definições
1 2
3
5
4
a
b c
d
e
PasseioUm passeio é uma sequência finita de vértices earestas.
Cada vértice da sequência é incidente a arestaque o precede e a aresta seguinte.
Essa sequência deve acabar e iniciar em umvértice (não necessariamente os mesmos).
Ex.: 1 - a - 2 - c - 3 - d - 4 - d - 3 - e - 5ou: 1 - 2 - 3 - 4 - 3 - 5
O passeio pode ser:
Aberto : quando inicia e acaba emvértices diferentes (o caso acima).
Fechado : quando inicia e acaba no mesmovértice. Ex.: 1-2-3-4-3-5-3-1.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 14 / 26
Definições
1 2
3
5
4
a
b c
d
e
PasseioUm passeio é uma sequência finita de vértices earestas.
Cada vértice da sequência é incidente a arestaque o precede e a aresta seguinte.
Essa sequência deve acabar e iniciar em umvértice (não necessariamente os mesmos).
Ex.: 1 - a - 2 - c - 3 - d - 4 - d - 3 - e - 5ou: 1 - 2 - 3 - 4 - 3 - 5
O passeio pode ser:
Aberto : quando inicia e acaba emvértices diferentes (o caso acima).
Fechado : quando inicia e acaba no mesmovértice. Ex.: 1-2-3-4-3-5-3-1.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 14 / 26
Definições
1 2
3
5
4
a
b c
d
e
PasseioUm passeio é uma sequência finita de vértices earestas.
Cada vértice da sequência é incidente a arestaque o precede e a aresta seguinte.
Essa sequência deve acabar e iniciar em umvértice (não necessariamente os mesmos).
Ex.: 1 - a - 2 - c - 3 - d - 4 - d - 3 - e - 5ou: 1 - 2 - 3 - 4 - 3 - 5
O passeio pode ser:
Aberto : quando inicia e acaba emvértices diferentes (o caso acima).
Fechado : quando inicia e acaba no mesmovértice. Ex.: 1-2-3-4-3-5-3-1.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 14 / 26
Definições
1 2
3
5
4
a
b c
d
e
PasseioUm passeio é uma sequência finita de vértices earestas.
Cada vértice da sequência é incidente a arestaque o precede e a aresta seguinte.
Essa sequência deve acabar e iniciar em umvértice (não necessariamente os mesmos).
Ex.: 1 - a - 2 - c - 3 - d - 4 - d - 3 - e - 5ou: 1 - 2 - 3 - 4 - 3 - 5
O passeio pode ser:
Aberto : quando inicia e acaba emvértices diferentes (o caso acima).
Fechado : quando inicia e acaba no mesmovértice. Ex.: 1-2-3-4-3-5-3-1.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 14 / 26
Definições
1 2
3
5
4
a
b c
d
e
CadeiaUm passeio que não repete arestas.
Ex.: 4 - 3 - 2 - 1 - 3 - 5
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 15 / 26
Definições
1 2
3
5
4
a
b c
d
e
CadeiaUm passeio que não repete arestas.
Ex.: 4 - 3 - 2 - 1 - 3 - 5
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 15 / 26
Definições
1 2
3
5
4
a
b c
d
e
CadeiaUm passeio que não repete arestas.
Ex.: 4 - 3 - 2 - 1 - 3 - 5
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 15 / 26
Definições
1 2
3
5
4
a
b c
d
e
CadeiaUm passeio que não repete arestas.
Ex.: 4 - 3 - 2 - 1 - 3 - 5
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 15 / 26
Definições
1 2
3
5
4
a
b c
d
e
CadeiaUm passeio que não repete arestas.
Ex.: 4 - 3 - 2 - 1 - 3 - 5
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 15 / 26
Definições
1 2
3
5
4
a
b c
d
e
CadeiaUm passeio que não repete arestas.
Ex.: 4 - 3 - 2 - 1 - 3 - 5
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 15 / 26
Definições
1 2
3
5
4
a
b c
d
e
CaminhoUma cadeia sem repetição de vértices.
Ex.: 1 - 2 - 3 - 5Aberto : quando inicia e acaba em
vértices diferentes (o casoacima).
Fechado : quando inicia e acaba nomesmo vértice. Ex.: 1-2-3-1.
Comprimento : o comprimento de umcaminho é o número de arestasque o mesmo inclui.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 16 / 26
Definições
1 2
3
5
4
a
b c
d
e
CaminhoUma cadeia sem repetição de vértices.
Ex.: 1 - 2 - 3 - 5Aberto : quando inicia e acaba em
vértices diferentes (o casoacima).
Fechado : quando inicia e acaba nomesmo vértice. Ex.: 1-2-3-1.
Comprimento : o comprimento de umcaminho é o número de arestasque o mesmo inclui.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 16 / 26
Definições
1 2
3
5
4
a
b c
d
e
CaminhoUma cadeia sem repetição de vértices.
Ex.: 1 - 2 - 3 - 5Aberto : quando inicia e acaba em
vértices diferentes (o casoacima).
Fechado : quando inicia e acaba nomesmo vértice. Ex.: 1-2-3-1.
Comprimento : o comprimento de umcaminho é o número de arestasque o mesmo inclui.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 16 / 26
Definições
CaminhoUma cadeia sem repetição de vértices.
Ex.: 1 - 2 - 3 - 5Aberto : quando inicia e acaba em
vértices diferentes (o casoacima).
Fechado : quando inicia e acaba nomesmo vértice. Ex.: 1-2-3-1.
Comprimento : o comprimento de umcaminho é o número de arestasque o mesmo inclui.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 16 / 26
Definições
CaminhoUma cadeia sem repetição de vértices.
Ex.: 1 - 2 - 3 - 5Aberto : quando inicia e acaba em
vértices diferentes (o casoacima).
Fechado : quando inicia e acaba nomesmo vértice. Ex.: 1-2-3-1.
Comprimento : o comprimento de umcaminho é o número de arestasque o mesmo inclui.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 16 / 26
Definições
CaminhoUma cadeia sem repetição de vértices.
Ex.: 1 - 2 - 3 - 5Aberto : quando inicia e acaba em
vértices diferentes (o casoacima).
Fechado : quando inicia e acaba nomesmo vértice. Ex.: 1-2-3-1.
Comprimento : o comprimento de umcaminho é o número de arestasque o mesmo inclui.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 16 / 26
Sumarizando...
PasseioSequência finita de vértices e arestas.
CadeiaUm passeio que não repete arestas.
CaminhoUma cadeia sem repetição de vértices.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 17 / 26
Relembrando...
Grafo ConexoUm grafo é dito conexo se para todo par de vértices i e j existe pelo menosum caminho entre i e j .
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 18 / 26
Exercícios
1 Quantos caminhos existem entre os vértices b e f ?b e
c d
a
f
g
2 Dê um exemplo de um grafo conexo G cuja remoção de qualqueraresta torna G desconexo.
3 Quantas arestas possui um grafo com estas características?
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 19 / 26
Caminhos e Circuitos
Teorema 1Se um grafo possui exatamente 2 vértices de grau ímpar, existe umcaminho entre esses dois vértices.
Teorema 2O número mínimo de arestas de um grafo simples com n vértices e kcomponentes é n − k .
Teorema 3Um grafo simples com n vértices e k componentes possui no máximo(n − k)(n − k + 1)/2 arestas (caso trivial).
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 20 / 26
Caminhos e Circuitos
Teorema 1Se um grafo possui exatamente 2 vértices de grau ímpar, existe umcaminho entre esses dois vértices.
Teorema 2O número mínimo de arestas de um grafo simples com n vértices e kcomponentes é n − k .
Teorema 3Um grafo simples com n vértices e k componentes possui no máximo(n − k)(n − k + 1)/2 arestas (caso trivial).
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 20 / 26
Caminhos e Circuitos
Teorema 1Se um grafo possui exatamente 2 vértices de grau ímpar, existe umcaminho entre esses dois vértices.
Teorema 2O número mínimo de arestas de um grafo simples com n vértices e kcomponentes é n − k .
Teorema 3Um grafo simples com n vértices e k componentes possui no máximo(n − k)(n − k + 1)/2 arestas (caso trivial).
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 20 / 26
Ciclos
DefiniçãoUm ciclo é um caminho fechado.
Alguns autores, utilizam o termo circuito para o caso de grafos orientados.
Grafo Ciclo: Um grafo ciclo Cn é um grafo com n vértices formado porapenas um ciclo passando por todos os vértices.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 21 / 26
ExercícioQuantos grafos ciclos (não isomorfos) são subgrafos do grafo abaixo?
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 22 / 26
Ciclos
DefiniçõesA cintura de um grafo é o comprimento do menor ciclo existente no mesmo.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 23 / 26
Ciclos
DefiniçõesA circunferência de um grafo é o comprimento do maior ciclo existente nomesmo.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 24 / 26
Exercícios
1 Qual a cintura e a circunferência do grafo abaixo ?
2 Mostre que não é possível haver um grupo de 7 pessoas no qual cadaum conhece exatamente outras 3 pessoas.
3 Prove que quaisquer dois grafos conexos com n vértices, todos de grau2, são isomorfos.
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 25 / 26
Dúvidas?
Marco Antonio M. Carvalho (UFOP) BCC204 9 de março de 2020 26 / 26
Recommended