Introdução à Teoria dos Grafos

Prévia do material em texto

Tópicos Especiais em Algoritmos e Grafos
 (COS 842)
Professores: Márcia Cerioli Daniel Posner
 cerioli@cos.ufrj.br posner@cos.ufrj.br
 
 
 TEAG
 
Aula 01 – Introdução e Definições
Ementa:
Objetivos: EstudarEstudar propriedades estruturaispropriedades estruturais de classes 
 de grafos e utilizar tais estruturas parapara
 
 Reconhecê-las e solucionar problemas de Reconhecê-las e solucionar problemas de 
otimizaçãootimização
 Grafos com poucos Ppoucos P44's's 
(threshold, cografos, P4-esparsos, P4-tidy e (q, q-4))
 Grafos com decomposição por dupla 2decomposição por dupla 2. 
 (fracamente cordais, distância hereditário, bip. cordais)
 
 TEAG
 
Aula 01 – Introdução e Definições
Bibliografia
 
 TEAG
 
Aula 01 – Introdução e Definições
Grupo: https://groups.yahoo.com/neo/groups/TEAG2017/ 
Convite será enviado por email.
 
Avaliação: listas de exercícios;
 1 prova;
 1 trabalho / seminário.
 (participação em sala de aula)
 
 
 
 TEAG
 
Aula 01 – Introdução e Definições
Trabalho (tema indicado ou escolhido pelo aluno)
(classe + problema)
Relatório parcial:Relatório parcial: Uma ideia inicial sobre o tema escolhido.
 Relatório final:Relatório final: Um estudo de um problema restrito a
 uma das classes de grafos estudada no curso.
 ApresentaçãoApresentação: Seminário sobre o trabalho.
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
Grafo Simples G = (V, E):
 VV : conjunto de elementos (vérticesvértices);
 
 
 EE : conjunto de pares não ordenados de elementos 
 Vizinhança de um vértice: conjunto de vértices
 Adjacentes a v.
 Grau de um vértice: tamanhotamanho da sua vizinhançavizinhança. 
 N(v)N(v), g(v)g(v), δδ, ∆∆
 
 
 TEAG Aula 01 – Definições da Teoria dos Grafos
Classes SimplesClasses Simples:
 
 
 
 TEAG Aula 01 – Definições da Teoria dos Grafos
 Se H é um grafo, então: 
 H H é subgrafo subgrafo dede G G sese V(H) V(H) V(G) V(G) ee E(H) E(G). E(H) E(G).
 H H é subgrafo induzido subgrafo induzido de GG se é subgrafo de GG e 
 E(H) = {uv | uv E(G) E(H) = {uv | uv E(G) ee {u, v} V(H)} {u, v} V(H)}
Dado
 S V(G), G[S] S V(G), G[S] é sub. ind. sub. ind. por S S em G. G.
 
 
 
 
 
 
 
 
⊆ ⊆ 
⊆ ⊆ 
⊆ 
 
 TEAG Aula 01 – Definições da Teoria dos Grafos
 
 
 Conjunto independente
 
 
 
 
 TEAG Aula 01 – Definições da Teoria dos Grafos
Subgrafos induzidos especiaisSubgrafos induzidos especiais:
 
 
 
 
 
 
 
 TEAG Aula 01 – Definições da Teoria dos Grafos
Subgrafos induzidos especiaisSubgrafos induzidos especiais:
 
 
 
 
 
 
 
 TEAG Aula 01 – Definições da Teoria dos Grafos
Subgrafos induzidos especiaisSubgrafos induzidos especiais:
 
 
 
 
 
 
 
 TEAG Aula 01 – Definições da Teoria dos Grafos
Subgrafos induzidos especiaisSubgrafos induzidos especiais:
 
 
 
 
 
 
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
Operações Operações em grafos G G e H H com V(G) V(G) ∩ ∩ V(H) =V(H) = ∅∅
 
 União
 Join
 Complemento
 Adicionar gêmeo falso
 Adicionar gêmeo verdadeiro
 Adicionar folha
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
Operações Operações em grafos G G e H H com V(G) V(G) ∩ ∩ V(H) =V(H) = ∅∅
 
 União
 Join
 Complemento
 Adicionar gêmeo falso
 Adicionar gêmeo verdadeiro
 Adicionar folha
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
Operações Operações em grafos G G e H H com V(G) V(G) ∩ ∩ V(H) =V(H) = ∅∅
 
 União
 Join
 Complemento
 Adicionar gêmeo falso
 Adicionar gêmeo verdadeiro
 Adicionar folha
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
Operações Operações em grafos 
 
 União
 Join
 Complemento
 Adicionar gêmeo falso
 Adicionar gêmeo verdadeiro
 Adicionar folha
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
Operações Operações em grafos 
 
 União
 Join
 Complemento
 Adicionar gêmeo falso
 Adicionar gêmeo verdadeiro
 Adicionar folha
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
Operações Operações em grafos 
 
 União
 Join
 Complemento
 Adicionar gêmeo falso
 Adicionar gêmeo verdadeiro
 Adicionar folha
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
Operações Operações em grafos: 
 
 União
 Join
 Complemento
 Adicionar gêmeo falso
 Adicionar gêmeo verdadeiro
 Adicionar folha
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
Propriedades de grafosPropriedades de grafos:
 conexo 
 k-colorível
 clique máxima k
 hamiltoniano
 euleriano
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
Propriedades de grafosPropriedades de grafos:
 conexo 
 k-colorível
 clique máxima k
 hamiltoniano
 Euleriano G e H são conexos.
 A sua união é um grafo desconexo.
G é componente conexo de G U H
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
Propriedades de grafosPropriedades de grafos:
 conexo 
 k-colorível
 clique máxima k
 hamiltoniano
 euleriano
 
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
Propriedades de grafosPropriedades de grafos:
 conexo 
 k-colorível
 clique máxima k
 hamiltoniano
 euleriano
 Qual o menor k? Justifique.
 
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
Propriedades de grafosPropriedades de grafos:
 conexo 
 k-colorível
 clique máxima k
 hamiltoniano
 euleriano
 clique máxima: tamanho 3 
 
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
Propriedades de grafosPropriedades de grafos:
 conexo 
 k-colorível
 clique máxima k
 hamiltoniano
 euleriano
 G e H são hamiltonianos.
 
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
Propriedadesde grafosPropriedades de grafos:
 conexo 
 k-colorível
 clique máxima k
 hamiltoniano
 euleriano
 G é euleriano. H não é.
 (a, b, f, d, b, 
 e, f, c, d, a) 
 TEAG Aula 01 – Definições da Teoria dos Grafos
Distância e Diâmetro de um grafo.Distância e Diâmetro de um grafo.
 
 TEAG Aula 01 – Definições da Teoria dos Grafos
Distância e Diâmetro de um grafo.Distância e Diâmetro de um grafo.
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
ÁrvoreÁrvore: grafos conexo conexo e sem ciclosem ciclo.
 Árvore T (representação enraizada de T)
 Todo grafo conexo tem uma árvore geradora.
 
 
 
 TEAG Aula 01 – Definições da Teoria dos Grafos
BipartidoBipartido: grafo 2-colorível (sem ciclos ímpares).
 
 
 
 TEAG Aula 01 – Definições da Teoria dos Grafos
CordalCordal: grafo sem ciclo induzido maior que 3.
 Cordal Não é cordal.
 
 TEAG Aula 01 – Definições da Teoria dos Grafos
SplitSplit: Particiona os vértices em um conj. indep. e clique.
 (equiv. cordaiscordais cocordaiscocordais)
 
 
 
 
 TEAG Aula 01 – Definições da Teoria dos Grafos
SplitSplit: Particiona os vértices em um conj. indep. e clique.
Teo: As seguintes afirmações são verdadeiras:
 (i) GG é um grafo splitgrafo split
 (ii) GG e GG são grafos cordaisgrafos cordais.
 (iii) GG é sem C4, C5 e 2k2 induzidossem C4, C5 e 2k2 induzidos.
 
 
 TEAG Aula 01 – Definições da Teoria dos Grafos
Fracamente cordalFracamente cordal: sem ciclo induzido maior que 4.
 
 
 
 TEAG Aula 01 – Definições da Teoria dos Grafos
Fracamente cordalFracamente cordal: sem ciclo induzido maior que 4.
 Quais desses grafos são fracamente cordais?
 
 TEAG Aula 01 – Definições da Teoria dos Grafos
CografoCografo: 
não tem caminho induzido de tamanho 4.
K1; União de dois cografos; Join de dois cografos 
 
K1 com operações de adição de gêmeos v. e f.
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
 Propriedades de classes de grafos: Propriedades de classes de grafos: 
 Hereditária:
 
 todo subgrafo induzido de um grafo
 na classe está na classe.
bipartidosbipartidos, cografoscografos, fracamente cordaisfracamente cordais, 
conexosconexos, árvoresárvores, clique Hellyclique Helly.
Autocomplementar: todo complemento de um grafo
 na classe está na classe.
cografoscografos, PP44-tidy-tidy, permutação, perfeitospermutação, perfeitos, , splitsplit, , 
árvoresárvores, bipartidosbipartidos, cordaiscordais
 
 TEAG Aula 01 – Definições da Teoria dos Grafos
 Diagrama de Classes: Diagrama de Classes: 
 
 TEAG Aula 01 – Definições da Teoria dos Grafos
 Diagrama de Classes: Diagrama de Classes: 
 
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
 
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
 Algoritmo:Algoritmo: método sistemático para solucionar problema. 
 Este recebe uma entrada (de tam. x) e fornece um saída.
Ex: Busca em largura em um grafo.Busca em largura em um grafo.
 Entrada: Grafo G e vértice raiz.
 Saída: Lista de arestas por tipo.
 Tamanho da entrada: n + m.
 #Operações: O(n + m) [linearlinear]
 Algoritmo é: linearlinear, polinomialpolinomial ou exponencialexponencial se o seu
 # operações é O(xx), O(xxcc) ou O(22xx).
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
 Problema de decisãoProblema de decisão: palavra pertence a linguagem? 
 (resposta: SIM ou NÃO)
 Ex: Ciclo hamiltoniano = <G | G é hamiltoniano>.
pi∈P se resolvemosresolvemos em tempo polinomialpolinomial na entrada.
pi∈NP se verificamosverificamos em tempo polinomialpolinomial na entrada.
Ex: pi1= Distância (G, u, v), pi2= Caminho Hamiltoniano 
 pi ∈1 P e pi ∈2 NP 
 
 TEAG Aula 01 – Definições da Teoria dos Grafos
 Prob. NP-difíceisProb. NP-difíceis: tão difíceis quanto os + difíceis de NP.
 
 Transformação polinomialTransformação polinomial pi em pi2
 pi2∈NP-difícil se ∀pi∈NP é transf. pol. em pi2.
 pi2∈NP-difícil se ∃ transf. pol. pi1∈NP-difícil em pi2.
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
 Problemas NP-completosProblemas NP-completos: NP-difíceis em NP.
 Um algoritmo pol. para um problema NP-completo 
resolve todos os problemas em NP em tempo pol. (P = NP)
 9 dos 21 problemas NP-completos de Karp
SAT, 3SAT, 3DM, KNAPSACK
CLIQUE, PARTITION, VERTEX COVER, 
CHROMATIC NUMBER, MAX CUT.
 Outros: VERTEXCOVER, STABLESET, BANDWIDTH. 
 
 TEAG
 
Aula 01 – Definições da Teoria dos Grafos
 Classifique os problemas em: NP-difícil ou NP-completo.
 (está em NP ou não?)
(a) (b)
Caminho Hamiltoniano Número cromático
Instância: Grafo G Instância: Grafo G
Pergunta: Exist. cam. Ham. Pergunta: Qual menor k 
 em G? G é k-colorível?
 (c) (d)
Conj. Ind. Máximo MAX-CUT 
Instância: Grafo G Instância: Grafo G, peso 
Pergunta: Qual # maior nas arestas de E(G), int. k
 conj. ind. de G? Pergunta: Existe bip. V(G)
 onde soma dos peso das 
 arestas do corte é k? 
 TEAG Aula 01 – Definições da Teoria dos Grafos