Breve Introdução a Grafos e Redes Complexas Marcia Paiva Laboratório de Telecomunicações - LabTel Universidade Federal do Espı́rito Santo II Jornada de Atualização em Computação, Elétrica e Eletrônica - JACEE Vitória, 13 de novembro de 2014 Marcia Paiva (LabTel - UFES) [email protected] 1 / 61 Sumário 1 Introdução 2 Definições e resultados 3 Percursos em grafos Ciclos eulerianos Ciclos hamiltonianos Grafos eulerianos versus Grafos hamiltonianos 4 Exemplo: Redes de Telecomunicações 5 Próximo capı́tulo . . . 6 Referências Marcia Paiva (LabTel - UFES) [email protected] 2 / 61 Introdução Sumário 1 2 3 4 5 6 Introdução Definições e resultados Percursos em grafos Ciclos eulerianos Ciclos hamiltonianos Grafos eulerianos versus Grafos hamiltonianos Exemplo: Redes de Telecomunicações Próximo capı́tulo . . . Referências Marcia Paiva (LabTel - UFES) [email protected] 3 / 61 Introdução Alguns aspectos históricos Theorie der endlichen und unendlichen graphen D. König 1936 Problema das Pontes de Königsberg Kaliningrado (Rússia, entre a Polônia e a Lituânia) 1736 Leonhard Euler (1707 − 1783) Marcia Paiva (LabTel - UFES) [email protected] 4 / 61 Introdução O Problema das Pontes de Königsberg Marcia Paiva (LabTel - UFES) [email protected] 5 / 61 Introdução O Problema das Pontes de Königsberg Marcia Paiva (LabTel - UFES) [email protected] 6 / 61 Introdução O Problema das Pontes de Königsberg Marcia Paiva (LabTel - UFES) [email protected] 7 / 61 Introdução Grafos: Objetos e suas relações Grafo Estrutura matemática usada para modelar relações entre objetos de um certo conjunto. Marcia Paiva (LabTel - UFES) [email protected] 8 / 61 Introdução Grafos: Objetos e suas relações Grafo Estrutura matemática usada para modelar relações entre objetos de um certo conjunto. Marcia Paiva (LabTel - UFES) [email protected] 8 / 61 Introdução Grafos: Objetos e suas relações Marcia Paiva (LabTel - UFES) [email protected] 9 / 61 Introdução Grafos: Objetos e suas relações Marcia Paiva (LabTel - UFES) [email protected] 10 / 61 Definições e resultados Sumário 1 2 3 4 5 6 Introdução Definições e resultados Percursos em grafos Ciclos eulerianos Ciclos hamiltonianos Grafos eulerianos versus Grafos hamiltonianos Exemplo: Redes de Telecomunicações Próximo capı́tulo . . . Referências Marcia Paiva (LabTel - UFES) [email protected] 11 / 61 Definições e resultados Definições gerais Mais formalmente... Um grafo é uma estrutura G = G (V , E ), onde: V é um conjunto finito e não vazio de elementos denominados vértices (ou nós); e E é um conjunto de subconjuntos {u, v }, com u, v ∈ V , denominados arestas (ou enlaces). Marcia Paiva (LabTel - UFES) [email protected] 12 / 61 Definições e resultados Definições gerais Um grafo é uma estrutura G = G (V , E ), onde: V é um conjunto finito e não vazio de elementos denominados vértices (ou nós); e E é um conjunto de subconjuntos {u, v }, com u, v ∈ V , denominados arestas (ou enlaces). Notação: n: número de nós m: número de arestas Marcia Paiva (LabTel - UFES) [email protected] 13 / 61 Definições e resultados Definições gerais Matriz de Adjacências A(G ) de um grafo G : 0 1 1 1 A(G ) = 0 0 0 0 0 Marcia Paiva (LabTel - UFES) 1 0 1 0 0 0 0 1 0 1 1 0 1 0 0 0 0 0 1 0 1 0 0 0 0 1 0 0 0 0 0 0 1 1 1 0 [email protected] 0 0 0 0 1 0 1 1 0 0 0 0 0 1 1 0 1 0 0 1 0 1 1 1 1 0 1 0 0 0 0 0 0 0 1 0 14 / 61 Definições e resultados Definições gerais Grafo simples Um grafo é denominado simples quando ele não possui laços, arestas múltiplas e orientação. Marcia Paiva (LabTel - UFES) [email protected] 15 / 61 Definições e resultados Definições gerais Grafo simples Um grafo é denominado simples quando ele não possui laços, arestas múltiplas e orientação. Marcia Paiva (LabTel - UFES) [email protected] 15 / 61 Definições e resultados Definições gerais Densidade A densidade de um grafo simples é a relação entre o seu número de arestas e o maior número possı́vel. Em um grafo simples, a densidade é igual a m/C(n,2) = 2m/n(n − 1). Marcia Paiva (LabTel - UFES) [email protected] 16 / 61 Definições e resultados Definições gerais Grau O grau de um vértice v , denotado por grau(v ), é a quantidade de arestas que nele incidem. δ(G ) = min{grau(v )}, ∀v ∈ G ∆(G ) = max{grau(v )}, ∀v ∈ G Marcia Paiva (LabTel - UFES) [email protected] 17 / 61 Definições e resultados Definições gerais Grau O grau de um vértice v , denotado por grau(v ), é a quantidade de arestas que nele incidem. δ(G ) = min{grau(v )}, ∀v ∈ G ∆(G ) = max{grau(v )}, ∀v ∈ G Relações de adjacência Vértices ligados por arestas são ditos vértices adjacentes ou vizinhos. Arestas que incidem em um mesmo vértice são arestas adjacentes. Marcia Paiva (LabTel - UFES) [email protected] 17 / 61 Definições e resultados Definições gerais - Exemplo n, m densidade de arestas vértices adjacentes arestas adjacentes grau de um vértice grau mı́nimo δ grau máximo ∆ Marcia Paiva (LabTel - UFES) [email protected] 18 / 61 Definições e resultados Definições gerais Grafo k-regular Todos os vértices do grafo tem o mesmo grau k. Marcia Paiva (LabTel - UFES) [email protected] 19 / 61 Definições e resultados Definições gerais Grafo k-regular Todos os vértices do grafo tem o mesmo grau k. Grafo completo Todos os vértices do grafo tem o mesmo grau k, com k máximo. Ou seja, quaisquer dois vértices distintos são adjacentes. Marcia Paiva (LabTel - UFES) [email protected] 19 / 61 Definições e resultados Definições gerais Percursos Informalmente, um caminho é uma sequência de nós e arestas, sem repetição. Um ciclo é um caminho que começa e termina no mesmo nó. Um grafo que não possui ciclo é dito acı́clico. Marcia Paiva (LabTel - UFES) [email protected] 20 / 61 Definições e resultados Definições gerais Percursos Informalmente, um caminho é uma sequência de nós e arestas, sem repetição. Um ciclo é um caminho que começa e termina no mesmo nó. Um grafo que não possui ciclo é dito acı́clico. Marcia Paiva (LabTel - UFES) [email protected] 20 / 61 Definições e resultados Definições gerais Percursos Informalmente, um caminho é uma sequência de nós e arestas, sem repetição. Um ciclo é um caminho que começa e termina no mesmo nó. Um grafo que não possui ciclo é dito acı́clico. Marcia Paiva (LabTel - UFES) [email protected] 20 / 61 Definições e resultados Definições gerais Percursos Um ciclo euleriano é um que passa exatamente uma vez por cada aresta do grafo. Um ciclo hamiltoniano é um ciclo que passa exatamente uma vez por cada vértice do grafo. Marcia Paiva (LabTel - UFES) [email protected] 21 / 61 Definições e resultados Definições gerais Percursos Um ciclo euleriano é um que passa exatamente uma vez por cada aresta do grafo. Um ciclo hamiltoniano é um ciclo que passa exatamente uma vez por cada vértice do grafo. Marcia Paiva (LabTel - UFES) [email protected] 21 / 61 Definições e resultados Definições gerais Grafo conexo Um grafo conexo é um grafo no qual existe um caminho interligando qualquer par de seus vértices. Um grafo que não é conexo será denominado desconexo. Marcia Paiva (LabTel - UFES) [email protected] 22 / 61 Definições e resultados Definições gerais Grafo conexo Um grafo conexo é um grafo no qual existe um caminho interligando qualquer par de seus vértices. Um grafo que não é conexo será denominado desconexo. Figura: (a) Um grafo conexo, e (b) Um grafo desconexo. Marcia Paiva (LabTel - UFES) [email protected] 22 / 61 Definições e resultados Definições gerais Árvore Um grafo conexo e acı́clico é denominado árvore. Marcia Paiva (LabTel - UFES) [email protected] 23 / 61 Definições e resultados Árvores Teorema: Dado um grafo G , as afirmações seguintes são equivalentes: 1 G é uma árvore. 2 Quaisquer dois vértices de G são ligados por um único caminho. 3 G é conexo e m = n − 1. 4 G é acı́clico e m = n − 1. 5 G é acı́clico e se quaisquer dois vértices não adjacentes de G são ligados por uma aresta e, então G + e tem exatamente um ciclo. Marcia Paiva (LabTel - UFES) [email protected] 24 / 61 Definições e resultados Árvores Teorema: Dado um grafo G , as afirmações seguintes são equivalentes: 1 G é uma árvore. 2 Quaisquer dois vértices de G são ligados por um único caminho. 3 G é conexo e m = n − 1. 4 G é acı́clico e m = n − 1. 5 G é acı́clico e se quaisquer dois vértices não adjacentes de G são ligados por uma aresta e, então G + e tem exatamente um ciclo. Corolário: Toda árvore (n ≥ 2) tem pelo menos dois vértices de grau 1, chamados vértices terminais ou folhas. Marcia Paiva (LabTel - UFES) [email protected] 24 / 61 Definições e resultados Árvores Com estes resultados, concluı́mos que: Uma árvore é um grafo conexo minimal com relação ao número de arestas. Ou seja, dados n nós, o menor grafo conexo que se pode construir é uma árvore. Marcia Paiva (LabTel - UFES) [email protected] 25 / 61 Definições e resultados Exemplo: árvores não isomorfas com 7 nós Dados 7 nós, existem 11 configurações possı́veis de árvores não isomorfas: Marcia Paiva (LabTel - UFES) [email protected] 26 / 61 Definições e resultados Definições gerais Cortes em um grafo Uma articulação é um vértice que, ao ser retirado, torna o grafo desconexo. Uma ponte é uma aresta que, ao ser retirada, torna o grafo desconexo. Marcia Paiva (LabTel - UFES) [email protected] 27 / 61 Definições e resultados Definições gerais Conectividade de vértices k(G ) de um grafo G Menor número de vértices que, ao serem retirados, o grafo se torna desconexo (ou se reduz a um único vértice). Conectividade de arestas k ′ (G ) de um grafo G Menor número de arestas que, ao serem retiradas, o grafo se torna desconexo. Marcia Paiva (LabTel - UFES) [email protected] 28 / 61 Definições e resultados Definições gerais Conectividade de vértices k(G ) de um grafo G Menor número de vértices que, ao serem retirados, o grafo se torna desconexo (ou se reduz a um único vértice). Conectividade de arestas k ′ (G ) de um grafo G Menor número de arestas que, ao serem retiradas, o grafo se torna desconexo. Portanto: Em qualquer árvore T , k(T ) = k ′ (T ) = 1. Marcia Paiva (LabTel - UFES) [email protected] 28 / 61 Definições e resultados Conectividade em árvores T A expressão k(T ) = k ′ (T ) = 1 pode ser traduzida como: Basta uma falha (vértice/aresta) para tornar o grafo desconexo. Toda aresta é uma ponte, e todo vértice (exceto possivelmente os terminais) é uma articulação. Existe um único caminho entre qualquer par de vértices. Marcia Paiva (LabTel - UFES) [email protected] 29 / 61 Definições e resultados Definições gerais Conectividade Um grafo G tal que k(G ) ≥ 2 é denominado grafo 2-conexo. Marcia Paiva (LabTel - UFES) [email protected] 30 / 61 Definições e resultados Definições gerais Conectividade Um grafo G tal que k(G ) ≥ 2 é denominado grafo 2-conexo. Como consequência da definição: Em um grafo 2-conexo G , não há pontes e nem articulações. Marcia Paiva (LabTel - UFES) [email protected] 30 / 61 Definições e resultados Definições gerais Conectividade Um grafo G tal que k(G ) ≥ 2 é denominado grafo 2-conexo. Como consequência da definição: Em um grafo 2-conexo G , não há pontes e nem articulações. Teorema (Whitney, 1932): Um grafo G é p-conexo se, e somente se, qualquer par de vértices de G é interligado por no mı́nimo p caminhos disjuntos. Marcia Paiva (LabTel - UFES) [email protected] 30 / 61 Definições e resultados Definições gerais Distância A distância dist(s, d) entre dois nós s e d e o número de enlaces de um menor caminho entre s e d. Marcia Paiva (LabTel - UFES) [email protected] 31 / 61 Definições e resultados Definições gerais Distância A distância dist(s, d) entre dois nós s e d e o número de enlaces de um menor caminho entre s e d. Diâmetro O diâmetro do grafo, denotado diam(G ), é a maior distância entre quaisquer dois nós s, d ∈ V . Marcia Paiva (LabTel - UFES) [email protected] 31 / 61 Definições e resultados Definições gerais Matriz de distâncias Dist(G ) de um grafo G : 0 1 1 1 Dist(G ) = 3 3 3 2 3 Marcia Paiva (LabTel - UFES) 1 0 1 2 2 2 2 1 2 1 1 0 1 3 3 3 2 3 1 2 1 0 2 2 2 1 2 3 2 3 2 0 1 1 1 2 [email protected] 3 2 3 2 1 0 1 1 2 3 2 3 2 1 1 0 1 2 2 1 2 1 1 1 1 0 1 3 2 3 2 2 2 2 1 0 32 / 61 Percursos em grafos Sumário 1 2 3 4 5 6 Introdução Definições e resultados Percursos em grafos Ciclos eulerianos Ciclos hamiltonianos Grafos eulerianos versus Grafos hamiltonianos Exemplo: Redes de Telecomunicações Próximo capı́tulo . . . Referências Marcia Paiva (LabTel - UFES) [email protected] 33 / 61 Percursos em grafos Ciclos eulerianos Voltando ao problema das pontes. . . Traduzindo para a linguagem de grafos, a questão das pontes de Königsberg fica assim: Começando de um vértice qualquer, existe um percurso que passa por cada aresta do grafo exatamente uma vez e retorna ao vértice inicial? Com a nomenclatura atual podemos perguntar: O grafo G possui um ciclo euleriano? Ou, equivalentemente: Quando um grafo pode ser desenhado sem levantar o lápis do papel? Marcia Paiva (LabTel - UFES) [email protected] 34 / 61 Percursos em grafos Ciclos eulerianos Ciclos eulerianos A resposta dada por Euler: Um grafo G possui um ciclo euleriano (isto é, G é euleriano) se, e somente se: G é conexo; e cada vértice de G tem grau par. Marcia Paiva (LabTel - UFES) [email protected] 35 / 61 Percursos em grafos Ciclos eulerianos Ciclos eulerianos Teorema (Euler, 1736): Um grafo conexo é euleriano se, e somente se, todos os seus vértices tem grau par. Marcia Paiva (LabTel - UFES) [email protected] 36 / 61 Percursos em grafos Ciclos eulerianos Ciclos eulerianos Teorema (Euler, 1736): Um grafo conexo é euleriano se, e somente se, todos os seus vértices tem grau par. Conclusão: O tour pelas pontes não é possı́vel! Marcia Paiva (LabTel - UFES) [email protected] 36 / 61 Percursos em grafos Ciclos eulerianos Aplicações Problemas de entregas domiciliares ou recolhimento, como: o Problema do Carteiro Chinês (Kwan Mei-Ko, 1962); coleta de lixo; limpeza de ruas com veı́culos vassoura. Marcia Paiva (LabTel - UFES) [email protected] 37 / 61 Percursos em grafos Ciclos eulerianos Decisão versus Otimização Tipos de problemas envolvendo grafos: Dado um grafo conexo, ele possui um ciclo que passa por cada aresta exatamente uma vez? Dado um grafo conexo, qual é o menor ciclo que passa por cada aresta pelo menos uma vez? Podemos pensar em problemas de decisão ou de otimização. Os problemas de decisão envolvem a caracterização dos grafos que atendem a certos requisitos. Marcia Paiva (LabTel - UFES) [email protected] 38 / 61 Percursos em grafos Ciclos hamiltonianos O problema do ciclo hamiltoniano William Rowan Hamilton (1805 - 1865) Marcia Paiva (LabTel - UFES) [email protected] 39 / 61 Percursos em grafos Ciclos hamiltonianos Around the world Marcia Paiva (LabTel - UFES) [email protected] 40 / 61 Percursos em grafos Ciclos hamiltonianos Ciclos hamiltonianos Dodecaedro regular (12 faces, 20 vértices e 30 arestas) É possı́vel viajar pelo mundo, passando por cada cidade exatamente uma vez, e retornar à cidade de origem? O dodecaedro possui um ciclo hamiltoniano? Marcia Paiva (LabTel - UFES) [email protected] 41 / 61 Percursos em grafos Ciclos hamiltonianos Ciclos hamiltonianos Marcia Paiva (LabTel - UFES) [email protected] 42 / 61 Percursos em grafos Ciclos hamiltonianos Aplicações O Problema do Caixeiro Viajante (Karl Menger, 1932) Marcia Paiva (LabTel - UFES) [email protected] 43 / 61 Percursos em grafos Ciclos hamiltonianos Decisão versus Otimização Também aqui há dois enfoques possı́veis: Dado um grafo conexo, ele possui um ciclo que passa por cada vértice exatamente uma vez? Dado um grafo conexo, qual é o menor ciclo que passa por cada vértice exatamente uma vez? Marcia Paiva (LabTel - UFES) [email protected] 44 / 61 Percursos em grafos Ciclos hamiltonianos Alguns resultados Teorema (Dirac, 1952) : Seja G = G (V , E ) um grafo com n vértices (n ≥ 3). Se grau(v ) ≥ n/2, para todo v ∈ V então G é hamiltoniano. Teorema (Ore, 1960) : Seja G = G (V , E ) um grafo com n vértices (n ≥ 3). Se, para todo par v , w de vértices não adjacentes, grau(v ) + grau(w ) ≥ n, então G é hamiltoniano. Teorema (Nash-Williams, 1969) : Todo grafo k-regular com 2k + 1 vértices é hamiltoniano. Teorema (Haggkvist e Micoghossian, 1981) : Um grafo G com k(G ) ≥ 2 e com δ(G ) ≥ (n + k(G ))/3 é hamiltoniano. Marcia Paiva (LabTel - UFES) [email protected] 45 / 61 Percursos em grafos Grafos eulerianos versus Grafos hamiltonianos Grafos eulerianos versus Grafos hamiltonianos Será que: Se um grafo G possui um ciclo euleriano, então G possui um ciclo hamiltoniano? Se um grafo G possui um ciclo hamiltoniano, então G possui um ciclo euleriano? Marcia Paiva (LabTel - UFES) [email protected] 46 / 61 Percursos em grafos Grafos eulerianos versus Grafos hamiltonianos Exemplo: Grafos eulerianos versus Grafos hamiltonianos, para n = 6 Marcia Paiva (LabTel - UFES) [email protected] 47 / 61 Percursos em grafos Grafos eulerianos versus Grafos hamiltonianos Resumindo: Ciclos eulerianos Leonhard Euler (1707 − 1783) Ciclo que passa por cada aresta do grafo exatamente uma vez Problema do Carteiro Chinês (Kwan Mei-Ko, 1962) Marcia Paiva (LabTel - UFES) [email protected] 48 / 61 Percursos em grafos Grafos eulerianos versus Grafos hamiltonianos Resumindo: Ciclos eulerianos Leonhard Euler (1707 − 1783) Ciclo que passa por cada aresta do grafo exatamente uma vez Problema do Carteiro Chinês (Kwan Mei-Ko, 1962) Teorema (Euler, 1736): Um grafo conexo é euleriano se, e somente se, todos os seus vértices tem grau par. Marcia Paiva (LabTel - UFES) [email protected] 48 / 61 Percursos em grafos Grafos eulerianos versus Grafos hamiltonianos Resumindo: Ciclos hamiltonianos William Rowan Hamilton (1805 − 1865) Ciclo que passa exatamente uma vez por cada vértice do grafo Problema do Caixeiro Viajante (Karl Menger, 1932) Ainda não existe condição necessária e suficiente para solucionar o problema Marcia Paiva (LabTel - UFES) [email protected] 49 / 61 Percursos em grafos Grafos eulerianos versus Grafos hamiltonianos Aplicações, do ponto de vista de redes Monitoramento de uma rede em malha com um nó central. Pode-se desejar enviar um sinal a partir deste nó, que deverá passar por todos os cabos/nós da rede exatamente uma vez e retornar ao ponto inicial. Sincronização, estimação de tempo de atraso, informação sobre estado, alarmes, etc. Marcia Paiva (LabTel - UFES) [email protected] 50 / 61 Percursos em grafos Grafos eulerianos versus Grafos hamiltonianos Observações adicionais Modelagem dos pontos de interesse em nós ou arestas Os pontos de atendimento de um serviço podem ser modelados por vértices ou arestas, dependendo do custo do serviço. Marcia Paiva (LabTel - UFES) [email protected] 51 / 61 Percursos em grafos Grafos eulerianos versus Grafos hamiltonianos Observações adicionais Modelagem dos pontos de interesse em nós ou arestas Os pontos de atendimento de um serviço podem ser modelados por vértices ou arestas, dependendo do custo do serviço. Problemas de percursos abrangentes Há diversas variações destes problemas para percursos abrangentes, que são percursos abertos ou fechados, com ou sem repetição de elementos, que utilizam todas as arestas ou todos os vértices de um grafo. Marcia Paiva (LabTel - UFES) [email protected] 51 / 61 Percursos em grafos Grafos eulerianos versus Grafos hamiltonianos Observações adicionais Modelagem dos pontos de interesse em nós ou arestas Os pontos de atendimento de um serviço podem ser modelados por vértices ou arestas, dependendo do custo do serviço. Problemas de percursos abrangentes Há diversas variações destes problemas para percursos abrangentes, que são percursos abertos ou fechados, com ou sem repetição de elementos, que utilizam todas as arestas ou todos os vértices de um grafo. Problemas de roteamento Na literatura de grafos e otimização combinatória, todos estes problemas são classificados como problemas de roteamento. Marcia Paiva (LabTel - UFES) [email protected] 51 / 61 Exemplo: Redes de Telecomunicações Sumário 1 2 3 4 5 6 Introdução Definições e resultados Percursos em grafos Ciclos eulerianos Ciclos hamiltonianos Grafos eulerianos versus Grafos hamiltonianos Exemplo: Redes de Telecomunicações Próximo capı́tulo . . . Referências Marcia Paiva (LabTel - UFES) [email protected] 52 / 61 Exemplo: Redes de Telecomunicações Grafos como Redes de Telecomunicações Marcia Paiva (LabTel - UFES) [email protected] 53 / 61 Exemplo: Redes de Telecomunicações Backbone da RNP (Rede Nacional de Ensino e Pesquisa) Marcia Paiva (LabTel - UFES) [email protected] 54 / 61 Exemplo: Redes de Telecomunicações Backbone da RNP G : RNP n = 17 nós m = 21 enlaces δ(G ) = 1 ∆(G ) = 4 diam(G ) = 7 G é conexo? G é 2-conexo? G é euleriano? G é hamiltoniano? Marcia Paiva (LabTel - UFES) [email protected] 55 / 61 Próximo capı́tulo . . . Sumário 1 2 3 4 5 6 Introdução Definições e resultados Percursos em grafos Ciclos eulerianos Ciclos hamiltonianos Grafos eulerianos versus Grafos hamiltonianos Exemplo: Redes de Telecomunicações Próximo capı́tulo . . . Referências Marcia Paiva (LabTel - UFES) [email protected] 56 / 61 Próximo capı́tulo . . . Backbone da RNP Marcia Paiva (LabTel - UFES) [email protected] 57 / 61 Próximo capı́tulo . . . Olhando mais de perto . . . Marcia Paiva (LabTel - UFES) [email protected] 58 / 61 Próximo capı́tulo . . . Backbones versus Redes Complexas Marcia Paiva (LabTel - UFES) [email protected] 59 / 61 Referências Sumário 1 2 3 4 5 6 Introdução Definições e resultados Percursos em grafos Ciclos eulerianos Ciclos hamiltonianos Grafos eulerianos versus Grafos hamiltonianos Exemplo: Redes de Telecomunicações Próximo capı́tulo . . . Referências Marcia Paiva (LabTel - UFES) [email protected] 60 / 61 Referências Principais referências: Graph theory Frank Harary Addison-Wesley, 1969. Introductory Graph Theory Gary Chartrand Dover Publications, 1984. The Theory of Graphs Claude Berge Dover Publications, 2001. Grafos: teoria, modelos, algoritmos Paulo Oswaldo Boaventura Netto Edgard Blücher, 2006. Algoritmos S. Dasgupta, C. H. Papadimitriou, U. Vaziranic 2009. Marcia Paiva (LabTel - UFES) [email protected] 61 / 61
Download
