Notas de Aula: Teoria dos Grafos

Centro de Matemática Computação e Cognição Universidade Federal do ABC Profa Carla Negri Lintzmayer Notas de aula da disciplina Teoria dos Grafos Esse material é um compilado dos seguintes Sedgewick R Algorithms in C part 5 graph algorithms 3rd ed AddisonWesley 2002 Bondy J A Murty U S R Graph Theory Graduate Texts in Mathematics Springer New York 2008 Lintzmayer C N Mota G O Notas de aulas Análise de algoritmos e estruturas de dados Em construção 10 Aula 14 digrafos grafos direcionados Um digrafo G é uma tripla V E ψ onde V é um conjunto não vazio de elementos chamados vértices E é um conjunto de elementos chamados arestas ou arcos disjunto de V e ψ é a função de incidência que associa um arco a um par ordenado de vértices Por exemplo H V E ψ onde V v0 v1 v2 v3 v4 v5 E e1 e2 e3 e4 e5 e6 e7 e8 e9 ψe1 v5 v5 ψe2 v2 v3 ψe3 v0 v3 ψe4 v4 v5 ψe5 v5 v1 ψe6 v0 v1 ψe7 v0 v2 ψe8 v0 v3 ψe9 v0 v4 ψe10 v3 v4 é um digrafo Digrafos permitem uma representação gráfica amigável círculos bolinhas representam vértices e uma arestaarco e é representada por uma flecha que liga os círculos que representam os vértices x e y se ψe x y O digrafo H dado acima pode ser visualizado na figura a seguir note como V E e ψ podem ser inferidas pelo desenho v0 v1 v2 v3 v4 v5 e3 e8 e1 e2 e4 e5 e6 e7 e9 e10 Dado um digrafo G V E ψ usamos V G V usamos EG E e ψG ψ a ordem de G é V G arestas e e f são paralelas se ψe ψf aresta e é um laço se ψe v v para algum v V G 59 101 Digrafos simples e Um digrafo G é simples se nao contém lagos nem arestas paralelas Nesse caso uma aresta pode ser unicamente determinada pelos seus extremos e wG pode ser definida implicitamente fazendo com que EG seja um conjunto de pares ordenados de vértices Por exemplo J onde VJ Uo U1 V2 U3 U4 Us e EJ vo U1 vo v2 v0 U3 Vo U4 V1 Us V4 U5 V2 U3 V3 U4 U5 U1 um digrafo simples Sua representacao grafica é dada na figura a seguir e A partir de agora o termo digrafo serd usado exclusivamente para denotar digrafos simples Se necessario faremos a diferenciagao usando 0 termo multidigrafo Proposigao 101 Se G é um digrafo de ordem n vale que n EG 25 nn1 102 Grafos e digrafos e Seja D um digrafo qualquer e O grafo subjacente de D é o grafo GD tal que VGD VD e para cada arco zy de D existe uma aresta ry em GD e Muitas definigdes sobre grafos podem fazer sentido em digrafos se considerarmos seu grafo subjacente e Seja G um grafo qualquer e O digrafo associado a G é o digrafo DG tal que VDG VG e para cada aresta ry de G existem dois arcos ry e yx em DG 60 Essa relação mostra que todo grafo é um digrafo Uma orientação de G é um digrafo G tal que V G V G e para cada aresta xy de G existe um arco xy ou yx em G Se nos é dado um digrafo D qualquer e ele é uma orientação de algum grafo então D é chamado de grafo orientado 103 Adjacência e vizinhança Seja G um digrafo Se e EG e e u v então e sai de u e entra em v u é cauda de e e v é cabeça de e u domina v e v é dominado por u u é vizinho de entrada de v v é vizinho de saída de u denotaremos u v simplesmente por uv e note que uv vu A vizinhança de saída de u V G denotada N Gu ou apenas N u é o conjunto que contém os de vizinhos de saída de u isto é v V G uv EG A vizinhança de entrada de u V G denotada N Gu ou apenas N u é o conjunto que contém os de vizinhos de entrada de u isto é v V G vu EG 104 Grau Seja G um digrafo O grau de saída de um vértice v V G denotado d Gv ou dv é o número de arestas que saem de v O grau de entrada de um vértice v V G denotado d Gv ou dv é o número de arestas que entram em v Note que d Gv N Gv e d Gv N Gv se G é um multidigrafo podemos ter d Gv N Gv ou d Gv N Gv para algum v V G 61 Um vértice v é uma fonte se dv 0 Um vértice v é um ralosorvedouro se dv 0 O grau de saída mínimo de G denotado δG é o menor grau de saída dentre os graus de saída de todos os vértices de G isto é δG mind Gu u V G Analogamente podemos definir o grau de entrada mínimo de G que é denotado δG O grau de saída máximo de G denotado G é o maior grau de saída dentre os graus de saída de todos os vértices de G isto é G maxd Gu u V G Analogamente podemos definir o grau de entrada máximo de G que é denotado G 105 Isomorfismo O conceito de isomorfismo é igual ao definido para grafos 106 Algumas classes de digrafos Um digrafo D é arborescência se o grafo subjacente é uma árvore e se todo vértice tem grau de entrada 1 exceto por um vértice que é a raiz torneio se ele é a orientação de um grafo completo DAG se ele é acíclico DAG significa directed acyclic graph O digrafo reverso de D é o digrafo D tal que V D V D e xy E D se e somente se yx ED 107 Subdigrafos Os conceitos de subdigrafos são iguais aos de subgrafos 62 108 Aperto de maos O teorema a seguir estabelece uma relagao identidade fundamental que relaciona os graus dos vértices com o nimero de arestas em um digrafo Teorema 102 Aperto de maos Para todo digrafo G temos que yq di v Dveviay dev EG 109 Passeios trilhas caminhos e ciclos Os conceitos de passeios trilhas caminhos e ciclos sao os mesmos definidos para grafos O conceito de distancia também Nao é incomum falar passeiotrilhacaminhociclo orientadodirecionado para re forgar que a direcao das arestas importa 1010 Conexidade e Um digrafo G é dito fortemente conexo se existe um uvcaminho para todo par uv VG e Um digrafo que nao é fortemente conexo consiste de um conjunto de componentes fortemente conexas que sao subdigrafos fortemente conexos maximais e Note que nem todo arco de um digrafo esté em alguma componente fortemente conexa portanto 1011 Representacao de digrafos e Também usamos as duas implementagoes vistas para grafos Matriz de adjacéncias Listas de adjacéncias e Quais devem ser as adaptacoes 1012 Buscas em digrafos e Essencialmente sao os mesmos algoritmos exceto que devemos considerar a vizi nhanga de saida do vértice que esta sendo explorado 63 Assim vamos crescer uma arborescência durante a exploração 1 Função BFSD s 2 visitados 1 3 dists 0 4 crie uma fila vazia F 5 EnfileiraF s 6 Enquanto F faça 7 u DesenfileiraF 8 Para cada v N u faça 9 Se visitadov 0 então 10 visitadov 1 11 predv u 12 distv Du 1 13 EnfileiraF v 1 Função DFSD s 2 visitados 1 3 tempo tempo 1 4 preordems tempo 5 Para cada v N s faça 6 Se visitadov 0 então 7 predv s 8 DFSD v 9 tempo tempo 1 10 posordems tempo BFS continua encontrando distâncias mínimas Não conseguimos informações sobre caminhos que não comecem na raiz das buscas Não necessariamente é possível obter uma arborescência geradora do digrafo ou mesmo detectar componentes conexas ou fortemente conexas diretamente Mas podem ser adaptadas 1 2 3 4 5 6 7 8 64 Considerando uma arborescência de DFS correspondente a um dado digrafo D uma aresta xy ED é de retorno se y é ancestral de x na árvore note que posordemy posordemx de descida se y é descendente de x na árvore note que preordemy preordemx de cruzamento se y e x não têm relação de parentesco note que preordemy preordemx Lema 103 Um digrafo D é um DAG se e somente se não são encontradas arestas de retorno em nenhuma chamada da DFS sobre D 1013 Digrafos acíclicos DAGs Diversas aplicações em problemas de escalonamento realização de tarefas que têm dependência entre si Lema 104 Se D é um DAG então D contém uma fonte Demonstração Suponha para fins de contradição que D não contém nenhum vér tice v com dv 0 Tome um caminho maximal P v0 v1 vk em D Como dv0 0 seja x N v Claramente x V P pois caso contrário o caminho não seria maximal Então x vi para algum 1 i k Mas então v0 v1 vi v0 é um ciclo em D o que é uma contradição Lema 105 Se D é um DAG então D contém um ralosorvedouro Uma ordenação topológica de um digrafo D de ordem n é uma rotulação f V D 1 2 n dos vértices de D tal que fu fv se u v e se uv ED então fu fv Alternativamente uma ordenação topológica é uma sequência v1 vn dos n vértices de D tal que se vivj ED então i j Teorema 106 Se D é um digrafo então D admite uma ordenação topológica se e somente se D é acíclico Demonstração Vamos provar primeiro que se D admite uma ordenação topológica então ele é acíclico Seja f V D 1 n uma ordenação topológica de D 65 em que n V D e suponha para fins de contradição que D contém um ciclo C u1 uk u1 Para i 1 k 1 note que por causa do arco uiui1 vale que fui fui1 Isso implica que fu1 fuk Mas o arco uku1 existe o que contradiz f ser uma ordenação topológica Agora vamos provar que se D é acíclico então D admite uma ordenação topoló gica Vamos provar por indução em n V D Se n 1 então claramente D admite uma ordenação topológica Suponha então que n 1 e que qualquer digrafo acíclico D tal que 1 V D n admite uma ordenação topológica Pelo Lema 104 seja u V D uma fonte Seja D D u Note que D é um digrafo e é acíclico pois caso contrário D teria um ciclo Como V D n então por hipótese de indução D admite uma ordenação topológica S u1 un1 Vamos provar que S u u1 un1 é uma ordenação topológica de D De fato S contém todos os vértices de D Como S é ordenação topológica de D então i j para toda uiuj ED Como u é fonte em D então não existe arco do da forma uiu em D Então S é de fato uma ordenação topológica de D Teorema 107 Seja D um DAG de ordem n Aplique a DFS em D a partir de qualquer vértice e seja S v1 v2 vn a sequência dos vértices de D em ordem decrescente do valor de pósordem isto é posordemvi posordemvi1 para todo 1 i n Então S é uma ordenação topológica de D Demonstração Seja xy ED Precisamos mostrar que posordemx posordemy o que implica que x aparece em S à esquerda de y Quando DFSD x testou o vizinho de saída y de x apenas um dos dois seguintes casos ocorreu Se y não estava visitado então ele é visitado nesse momento Como a exploração de x só pode terminar depois que todos os seus vizinhos forem explorados claramente teremos posordemx posordemy Agora assuma que y já estava visitado Como D é um DAG então note que não existe yxcaminho Isso significa que DFSG y já terminou Logo claramente teremos posordemy posordemx 66