[[cap4]] == Introdução a Grafos e Árvores :cap: cap4 :online: {gitrepo}/blob/master/livro/capitulos/code/{cap} :local: {code_dir}/{cap} :img: {img_dir}/{cap} .Objetivos do capítulo ____ Ao final deste capítulo você deverá ser capaz de (entre outras coisas): * Modelar problemas do seu mundo real por meio de grafos, digrafos, ou árvores, para mais facilmente resolver os problemas mais simples; * Dominar e saber usar os principais conceitos e terminologia de grafos, de digrafos e de árvores; * Reconhecer se um grafo é k-partido, k-clique, conexo ou desconexo, digrafo, ou subgrafo de outro grafo; * Dominar e saber usar os principais conceitos e terminologia de passeios, trilhas, ciclos, caminhos, grafos eulerianos e hamiltonianos; * Conhecer os problemas do caminho mais curto, do carteiro chinês, do caixeiro viajante, das árvores geradoras de grafos. Não precisará saber os algoritmos, que são difíceis, mas deverá saber encontrar soluções _ad hoc_ de problemas em grafos muito pequenos. ____ *Nosso objetivo, neste capítulo*, é que você seja introduzido aos conceito básicos sobre grafos e árvores, começando a desenvolver a capacidade de modelar problemas reais por meio deles, e capacitando-o a acompanhar disciplinas posteriores que o habilitarão a modelar mais complexos problemas reais usando tais ferramentas, depois resolvê-los usando os algoritmos mais apropriados. Por falta de tempo, de espaço no livro, e de sua maior experiência com linguagens de programação, deixaremos a maioria dos tais algoritmos mais interessantes (e difíceis) para quando você fizer as disciplinas _Estruturas de Dados_, _Redes de Computadores_, e, talvez como ouvinte, alguma disciplina na linha de _Análise_ (da complexidade) e _Projeto de Algoritmos_, do Bacharelado em Ciência da Computação, da UFPB. .Sempre vamos repetir [TIP] ==== Estamos torcendo por você. O fórum de alunos, os tutores, e eu (o professor) queremos e vamos ajudá-lo (nessa ordem), mas você tem que ser determinado e disciplinado, *cada semana dedicando 4 a 8 horas para estudar este livro*. ==== [NOTE] ==== Agradecemos a permissão do _Prof. Dr. Lucídio dos Anjos Formiga Cabral_ (DCC/ CI/ UFPB) para usarmos grande parte das 2 primeiras aulas de seu curso ``_Introdução à Teoria dos Grafos_'', que brevemente voltará a ser disponibilizado na Internet. Mas acrescentamos alguns problemas a resolver e alguns exemplos, e ocasionalmente mudamos algumas figuras (ou copiamos de fontes tais como Professora Sílvia Fernanda Martins Brandão da Uber http://www.uber.com.br/silvia/MATD/, e outras.), omitimos, ou acrescentamos algumas coisas. Se você quiser ver o assunto mais explicada e profundamente, não precisará de mais que os livros textos da ementa da disciplina. Agradecemos a permissão do _Prof. Dr. Lucídio dos Anjos Formiga Cabral_ (DCC/ CI/ UFPB) para usarmos grande parte das 2 primeiras aulas de seu curso ``Introdução à Teoria dos Grafos'', que brevemente voltará a ser disponibilizado na Internet. Mas acrescentamos alguns problemas a resolver e alguns exemplos, e ocasionalmente mudamos algumas figuras (ou copiamos de fontes tais como Professora Sílvia Fernanda Martins Brandão da Uber http://www.uber.com.br/silvia/MATD/, e outras.), omitimos, ou acrescentamos algumas coisas. Se você quiser ver o assunto mais explicada e profundamente, não precisará de mais que os livros textos da ementa da disciplina. Mas há muitos e bons livros somente sobre grafos, alguns deles na Internet. link:http://www.ime.usp.br/\~pf/teoriadosgrafos/texto/TeoriaDosGrafos.pdf[] (_Uma Introdução Sucinta à Teoria dos Grafos_, Wakabayashi- Kohayakawa- Feofiloff), link:http://www.slideshare.net/biancamcdantas/introduo-teoria-dos-grafos[], link:http://www.ime.usp.br/\~pf/grafos-exercicios[], link:http://www.utm.edu/departments/math/graph/glossary.html[], link:http://www.iro.umontreal.ca/~hahn/IFT3545/GTWA.pdf[] (_Graph Theory with Applications_ - Bondy- Murty). Creditamos alguns dos exemplos e exercícios ao _Prof. Christopher Strobel_ e ao _Prof. Antônio Alfredo Ferreira Loureiro_. ==== === Motivação e Introdução Por que estudar grafos? Porque são: * Importante ferramenta matemática com aplicação em diversas áreas do conhecimento; * Utilizados na definição e/ou resolução de problemas; * Existem centenas de problemas computacionais que empregam grafos com sucesso. Primeiras motivações na área: * 1735, o Problema das 7 Pontes de Königsberg (atual Kaliningrad): (((Problema, 7 pontes de Königsberg))) Duas ilhas A e D, existentes no rio Pregel em Königsberg (Rússia), foram ligadas às margens do rio (B e C) através de 7 pontes. Pergunta: é possível iniciar uma caminhada a partir de um dos blocos de terra (A, B, C ou D), passar por cada uma das pontes exatamente uma vez, e voltar ao ponto de partida sem nadar pelo rio? [width="100%",cols="^,^",frame="none",grid="none"] |==== 2+|Você tem que passar por cada de *a,b,c,d,e,f,g* exatamente uma vez. |image:images/cap4/img01.eps[width="130"] Situação real -- o problema |image:images/cap4/img02.eps[width="100"] Modelo do problema |==== Resolvido pelo estudo da paridade dos nós: O problema não tem solução porque tem vértices com paridade ímpar (os termos serão definidos mais adiante, mas adiantamos que isto significa que há vértices com número ímpar de arcos incidentes). * 1847: G.R.Kirchnoff desenvolveu a teoria de árvores para trabalhar com aplicações em circuitos elétricos. * 1852: F. Guthrie apresentou informalmente o problema das 4 cores: São apenas 4 cores suficientes para colorir qualquer mapa em superfície plana (fronteiras entre regiões têm que ser linhas contínuas com comprimento maior que 0: não podem ser apenas um ponto), de maneira que regiões fronteiriças recebam cores distintas? (Isto só conseguiu ser (aos poucos) provado em a partir de 1976). * 1859: Sir W.R. Hamilton inventou um jogo que consistia em um dodecaedro com 12 faces e 20 vértices, com cada face sendo um pentágono regular e três arestas se encontrando em cada vértice e os vértices foram rotulados com nomes de 20 cidades importantes. O objetivo do jogo é achar uma rota pelas arestas do dodecaedro passando por cada vértice apenas uma vez. (A solução para este problema específico é fácil de se obter. No entanto, ainda não se tem uma condição necessária e suficiente para se verificar a existência de um ciclo hamiltoniano (definição mais adiante) em um grafo arbitrário.) * Depois desta época pouca coisa foi investigada em Teoria dos Grafos por quase um século. * O interesse ressurgiu na década de 1920 com os estudos de D. König que se transformaram em um livro, publicado em 1936. .Problema das (três) Utilidades [NOTE] ==== [width="100%", cols="^.^a,<.^", frame="none",grid="none"] |==== | G E W A B C |Considere 3 casas (A,B,C), cada uma com três utilidades: água (W), gás (G) e eletricidade (E). As utilidades estão conectadas às casas por meio de fios e canos. Considerando que todos os fios e canos estão no mesmo plano, é possível fazer as instalações sem cruzá-los? A resposta é *não* (a prova disso é difícil demais para esta disciplina). |==== ==== === Conceitos Básicos de Grafos e Digrafos Um *((grafo))* latexmath:[$G$] é um objeto matemático constituído por um par latexmath:[$(V,E)$], onde latexmath:[$V$] é um conjunto de elementos chamados de *((vértices))* (ou *nodos*) (que modelam locais ou estados ou tempos ou entidades, de problemas reais) e latexmath:[$E$] é um conjunto de elementos chamados de *((arestas))* (ou *arcos*), cada aresta latexmath:[$e_k$] modelando a relação de um vértice latexmath:[$v_i$] para um vértice latexmath:[$v_j$], ditos *extremos* de latexmath:[$e_k$]. Os vértices extremos de uma aresta são ditos incidentes nela, e as arestas que se ligam a um vértice são ditas *incidentes* nele. Dois vértices que são incidentes a uma (i.é, estão ligados a uma) mesma aresta são ditos *((vértices adjacentes))*. Duas arestas que são incidentes a um mesmo vértice são ditas *((arestas adjacentes))*. .{zwsp} ==== [width="100%", cols="^.^,<.^", frame="none",grid="none"] |==== |image:images/cap4/img03.eps[width="100"] |latexmath:[$G = (V,E)$] (grafo) latexmath:[$V = {1, 2, 3, 4, 5, 7}$] (vértices) latexmath:[$E = {a, b, c, d, e, f}$] (arcos) 5,7 são os extremos da aresta latexmath:[$a$]. 5,7 são incidentes na aresta latexmath:[$a$]; latexmath:[$a,d$] são incidentes no vértice 5. latexmath:[$a,d$] são arestas adjacentes; 5,7 são vértices adjacentes. |==== ==== .{zwsp} [NOTE] ==== [[fig_multigrafo]] .Grafo multigrafo image::images/cap4/img04.eps[scaledwidth="30%"] * Um grafo latexmath:[$G = (V, E)$] (<>) é um *((multigrafo))* se existem mais de uma aresta ligando o mesmo par de vértices. * Uma aresta do tipo latexmath:[${v_i,v_i}$] é denominada auto-laço. * Arestas que possuem os mesmos vértices extremos latexmath:[$v_i \not= v_j$] são ditas paralelas ou múltiplas. * Um grafo (como o anterior) sem auto-laços nem arestas paralelas é denominado *grafo simples*. ==== * O número de vértices de um grafo G é denotado por latexmath:[$n = |V|$]. O valor latexmath:[$n$] também é conhecido como ordem do grafo. (No multigrafo acima, é 4.) * O número de arestas de um grafo é denotado por latexmath:[$m = |E|$]. (No multigrafo acima, é 6.) * Se latexmath:[$|V|$] e latexmath:[$|E|$] são finitos, o grafo latexmath:[$G = (V,E)$] é finito. Caso contrário, é dito infinito. Estudaremos apenas grafos finitos. * O número de arestas incidentes a um vértice latexmath:[$v$] é denominado *grau* (latexmath:[$v$]) (ou *valência*) e representado por latexmath:[$d(v)$]. (No multigrafo acima, latexmath:[$d(4) = 5$].) O grau de um vértice isolado é 0. * latexmath:[$\delta(G)$] é o *grau mínimo* de latexmath:[$G$], o grau do vértice de menor grau. (No multigrafo acima, é 2, correspondente aos vértices 2 e 3.) * latexmath:[$\Delta(G)$] é o *grau máximo* de latexmath:[$G$], o grau do vértice de maior grau. (No multigrafo acima, é 5, correspondente ao vértices 4.) * *((Vértice isolado))* é o vértice que não possui arestas incidentes (tem grau 0). * *((Vértice folha))* (nomenclatura melhor que ((vértice terminal))) é o vértice que possui grau 1 (Em um digrafo será grau de entrada 1 e grau de saída 0). * *((Vizinhos))* de um vértice são os vértices adjacentes a ele. (No grafo acima, 3 e 4 são vizinhos.) * Pares de vértices (ou de arestas) não adjacentes são denominadas *independentes*. (No grafo acima, qualquer uma das arestas de 3 para 4, e a aresta de 1 para 2, são independentes entre si.) * Um conjunto de vértices (ou arestas) é *independente* se nenhum par de seus elementos é adjacente. Teorema:: Seja G = (V,E) um grafo simples com n vértices e m arestas. Então latexmath:[$\sum_{v \in V}{d(V)} = 2m$]. + -- [NOTE] ==== Esta fórmula equivale a dizer que a soma dos graus de todos os vértices é o dobro do número de arestas. ==== -- Prova:: Cada aresta latexmath:[$a$] é incidente em dois vértices latexmath:[$u$] e latexmath:[$v$], sendo contabilizada no cômputo do grau de latexmath:[$u$] e também de latexmath:[$v$]. * *((Auto-laço))* é uma aresta com extremos idênticos latexmath:[$(u,u)$]. *Link* é uma aresta com extremos diferentes latexmath:[$v_i \not= v_j$]. Portanto, arestas múltiplas são links com mesmos extremos: * Um grafo é *simples* se não possuir auto-laço nem arestas múltiplas. * (((Grafo, completo))) *Grafo completo* de latexmath:[$n$] vértices (também chamado de *n-clique*) é um grafo simples em que cada um dos seus latexmath:[$n$] vértices se liga por 1 aresta a todos os outros latexmath:[$n-1$] vértices, cada vértice tendo grau latexmath:[$n-1$], o grafo abaixo é um 5-clique. Há n nodos, cada um deles incidente em latexmath:[$n-1$] arcos, mas assim cada arco é contado 2 vezes, portanto o número total de arcos é latexmath:[$n(n-1)/2$]. .Grafo 5-clique. Pois cada um dos 5 vértices se liga a todos os outros. image::images/cap4/img05.eps[scaledwidth="30%"] * (((Grafo,vazio))) *Grafo vazio* é um grafo sem arestas. === Classes especiais de grafos ==== Grafo trivial (((Grafo, trivial))) *Grafo trivial* é um grafo com apenas um vértice. ==== Grafo bipartido (((Grafo, bipartido))) *Grafo bipartido* é aquele em que o conjunto de vértices pode ser particionado em dois subconjuntos latexmath:[$X$] e latexmath:[$Y$], tal que cada aresta do grafo tem um extremo em latexmath:[$X$] e o outro em latexmath:[$Y$]. Isso implica que não há ciclos de comprimento ímpar. Na <>, latexmath:[$X$] é o conjunto dos vértices na parte superior do grafo e latexmath:[$Y$] é o conjunto na parte inferior. ===== Grafo bipartido completo (((Grafo, bipartido completo))) *Grafo bipartido completo* é um grafo bipartido com bipartição latexmath:[$(X, Y)$] em que cada vértice de latexmath:[$X$] é adjacente a cada um de todos os vértices de latexmath:[$Y$]. (<>). Se chamarmos latexmath:[$|X|$] de latexmath:[$m$] e latexmath:[$|Y|$] de latexmath:[$n$], então denotamos tal grafo por latexmath:[$K_{m,n}$]. [[fig_grafo_bipartido]] .Grafo bipartido completo latexmath:[$K_{4,5}$]. image::images/cap4/img06.eps[scaledwidth="25%"] ==== Grafo k-partido (((Grafo, k-partido))) *Grafo k-partido* latexmath:[$G(V,E)$] é um grafo cujos vértices podem ser particionados em k conjuntos (como temos uma partição, esses conjuntos são disjuntos e união deles é V) de modo que nunca ocorra que dois vértices do mesmo conjunto sejam ligados por alguma aresta. ==== Grafo regular (((Grafo, regular))) *Grafo regular* é aquele em que todos os vértices têm mesmo grau. Se o grau for latexmath:[$k$], chamamos o grafo de k-regular. (Exemplo: o grafo bipartido completo, acima, é 4-regular) ==== Grafo rotulado (((Grafo, rotulado))) *Grafo rotulado* em vértices (ou arestas) é aquele em que cada vértice (ou aresta) é atribuído um rótulo tal como Brasília (ou Ponte da Amizade) que será seu nome. (Exemplo: o primeiro grafo desta seção é rotulado nos vértices (1, 2, etc.), e também é rotulado nas arestas (latexmath:[$a, b,$] etc.)) ==== Grafo valorado (((Grafo, valorado))) (((Grafo, ponderado))) *Grafo valorado* (ou ponderado) é aquele em que cada aresta (ou vértice) tem um número real associado a ele, representando um custo ou ganho em se passar por ele. Exemplos nas definições de problema do caminho mais curto (<>) e da árvore geradora mínima (<>). ==== Grafo altamente irregular (((Grafo, altamente irregular))) *Grafo altamente irregular* é aquele em que cada um de seus vértices é adjacente a vértices de graus diferentes entre si. ==== Grafo complementar (((Grafo, complementar))) Dado um grafo latexmath:[$G$], seu grafo *complementar* latexmath:[$\bar{G} $] é o grafo que contém as arestas que teria se fosse completo, mas que não estão em latexmath:[$G$]. .Grafos complementares. Os grafos cinza e preto são complementares entre si. image::images/cap4/img07.eps[scaledwidth="60%"] .Note que: [NOTE] ==== * O complementar de um grafo sem arestas é um grafo completo e vice versa. * Um conjunto de vértices independentes em um grafo corresponde a um clique no grafo complementar e vice versa. ==== ==== Grafo conexo (((Grafo, conexo))) Um grafo é dito *conexo* se houver um caminho entre quaisquer dois de seus vértices. .Grafo conexo image::images/cap4/img08.eps[scaledwidth="30%"] ==== Grafo desconexo (((Grafo, desconexo))) Um grafo é dito *desconexo* se não houver um caminho entre quaisquer dois de seus vértices. .Grafo desconexo. Note que não há caminho entre X~2~ e X~5~. image::images/cap4/img09.eps[scaledwidth="30%"] Um grafo desconexo é formado por pelo menos dois subgrafos conexos, disjuntos em relação aos vértices. Cada um destes subgrafos conexos é dito ser uma *componente conexa* do grafo. image::images/cap4/img10.eps[scaledwidth="30%"] Um vértice é chamado de um *((vértice de corte))* se sua remoção (juntamente com as arestas a ele conectadas) aumenta o número de componentes conexas (ver definição acima) do grafo. Isto é, a remoção de um vértice de corte faz com que um [sub] grafo que era conexo fique dividido em dois ou mais (sub-) subgrafos, cada um conexo em relação a si mesmo, mas sem ligação de um para os outros. Exemplo: o vértice 4 na definição de multigrafo, acima. Uma aresta é chamada de *((aresta ponte))* (também conhecida por *((aresta de corte))* ou *istmo*) se sua remoção aumenta o número de componentes conexas (ver definição acima) do grafo. Exemplo: a aresta latexmath:[$x_1 x_2$] na definição de grafo desconexo, acima. Dois grafos latexmath:[$G$] e latexmath:[$H$] são *idênticos* se: * latexmath:[$V(G) = V(H)$]; * latexmath:[$E(G) = E(H)$]; + -- [NOTE] ==== - A cada arco de latexmath:[$G$] ligando os vértices latexmath:[$u,v$] corresponde um arco de mesmo nome ligando os vértices latexmath:[$u,v$] em latexmath:[$H$]; e vice-versa) - latexmath:[$(u,v) \in E(G) \leftrightarrow (u,v) \in E(H)$] ==== -- Grafos idênticos podem estar _((graficamente distorcidos))_ e não ser muito fácil de você olhar para eles e logo perceber que são idênticos. Mas ambos podem ser representados por um mesmo diagrama. (Exemplo: os dois grafos abaixo, se já tivéssemos mudado os rótulos dos vértices do segundo grafo de 1,2,3,4,5,6,7,8 para a,h,d,i,g,b,j,c, respectivamente.) Um *isomorfismo* (denotado latexmath:[$G \approx H$]) entre dois grafos latexmath:[$(G,H)$] é uma bijeção latexmath:[$f$] de latexmath:[$V(G)$] em latexmath:[$V(H)$] tal que [latexmath] ++++ \[(u,v) \in E(G) \leftrightarrow (f(u),f(v)) \in E(H) \] ++++ isto é, para quaisquer dois vértices latexmath:[$u$] e latexmath:[$v$] de latexmath:[$G$], eles são adjacentes em latexmath:[$G$] se e somente se latexmath:[$f(u)$] e latexmath:[$f(v)$] são adjacentes em latexmath:[$H$]. Dois digrafos são *isomórficos* (definição adiante) se existe um isomorfismo entre os grafos a eles equivalentes e se é preservada a ordem dos vértices de cada arco. [width="100%",cols="^.^1,^.^2,^.^2",frame="none",grid="none",options="header"] |==== |Grafo latexmath:[$G$] |Grafo latexmath:[$H$] |Um isomorfismo entre latexmath:[$G$] e latexmath:[$H$] |image:images/cap4/img11.eps[width="60"] |image:images/cap4/img12.eps[width="130"] |latexmath:[$f(a) = 1$] latexmath:[$f(b) = 6$] latexmath:[$f(c) = 8$] latexmath:[$f(d) = 3$] latexmath:[$f(g) = 5$] latexmath:[$f(h) = 2$] latexmath:[$f(i) = 4$] latexmath:[$f(j) = 7$] |==== Compare esta definição com a de grafos idênticos. Obviamente, grafos idênticos são isomórficos. No entanto, o reverso não é verdade. (No exemplo acima, é possível alterar o nome dos vértices do grafo H de forma que este fique idêntico a latexmath:[$G$], mas isso nem sempre é possível. Exemplo: grafo latexmath:[$G = \{(1,2),(1,3),(1,4),(2,3)\}$] e grafo latexmath:[$H = \{(1,2),(1,3),(2,3),(3,4)\}$]. Desenhe os diagramas dos dois grafos, depois explique porque são isomórficos, e porque não são idênticos.) O isomorfismo de grafos preserva as propriedades: * Simetria: latexmath:[$G \approx H \leftrightarrow H \approx G$] * Reflexividade: latexmath:[$G \approx G$] * Transitividade: latexmath:[$(G \approx H) \wedge (H \approx I) \leftrightarrow (G \approx I)$] Se latexmath:[$G \approx H$], valem as seguintes proposições: * G e H têm o mesmo número de vértices * G e H têm o mesmo número de arestas * G e H têm a mesma sequência de graus (a sequência de graus de um grafo é a ordenação não crescente dos graus de seus vértices) ==== Digrafo ou grafo direcionado (((Digrafo))) (((Grafo, direcionado))) *Grafo direcionado* ou *digrafo* é aquele que tem todas as suas arestas direcionadas. Prefere-se chamar de arcos as arestas direcionadas, e de A o conjunto desses arcos. Cada arco é representado por um par ordenado, onde o primeiro elemento é a origem do arco e segundo é seu final. No exemplo abaixo, latexmath:[$G = (V,A)$] + latexmath:[$V = \{2,3,5,7,8,9,10,11\}$] + latexmath:[$A = \{(3,8), (3,10), (5,11), (7,8), (7,11), (8,9), (11,2), (11,9), (11,10)\}$]. NOTE: Pronuncia-se di-**GRA**-fo, pois não há acento. Alguns descuidados escrevem e pronunciam como ``dígrafo'', com acento, o que é erro pois corresponde ao conceito ``duas letras com apenas um só fonema, como ss entre duas vogais'', enquanto ``digrafo'' é aportuguesamento do inglês ``digraph'' (``directed graph'', ``grafo direcionado''). ===== Digrafo simples (((Digrafo, simples))) * *Digrafo simples* é um digrafo que não tem auto-laços e os arcos são todos distintos. (Exemplo acima.) (((Digrafo, acíclico))) * Digrafo simples *acíclico* é um digrafo simples que não tem ciclos. (Exemplo acima.) * O grafo latexmath:[$G$] obtido removendo-se as orientações dos arcos de um digrafo latexmath:[$D$] é chamado de grafo equivalente a latexmath:[$D$]. Se latexmath:[$D$] for simples, latexmath:[$G$] pode não o ser. (Você mesmo ache um exemplo disso.) Cada vértice latexmath:[$v$] de um digrafo latexmath:[$(V,A)$] tem um grau de entrada latexmath:[$grauent(v)$] ou latexmath:[$grau^{+}(v)$](que é o número de arcos que chegam nele) e um grau de saída latexmath:[$grausai(v)$] ou latexmath:[$grau^{-}(v)$] (que é o número de arcos que saem dele), onde: [latexmath] ++++ \[\sum{grauent(v_i)} = \sum{grausai(v_i)} = |A|\] ++++ Prova:: Cada arco latexmath:[$a$] sai de um nodo latexmath:[$u$] entra num nodo latexmath:[$v$], sendo contabilizada no cômputo do grau de saída de latexmath:[$u$] e também no grau de entrada de latexmath:[$v$]. ===== Digrafo fracamente e fortemente conectado (((Digrafo, fracamente conectado))) (((Digrafo, fortemente conectado))) Um digrafo latexmath:[$D$] é chamado de *fracamente conectado* (ou apenas *conectado*) se o grafo equivalente é um grafo conexo. Um digrafo é *fortemente conectado* ou *forte* se ele tem um caminho orientado de latexmath:[$u$] a latexmath:[$v$] e um caminho orientado de latexmath:[$v$] a latexmath:[$u$] para cada par de vértices latexmath:[$u,v$]. ==== Subgrafo (((Subgrafo))) * Um grafo latexmath:[$H$] é um *subgrafo* de latexmath:[$G$] (latexmath:[$H \subseteq G$]) se latexmath:[$V(H) \subseteq V(G)$] e latexmath:[$E(H)\subset E(G)$]. * Quando latexmath:[$H \subseteq G$] e latexmath:[$H \not= G$], denotamos latexmath:[$H \subseteq G$] e dizemos que latexmath:[$H$] é *subgrafo próprio* de latexmath:[$G$].Se latexmath:[$H$] é um subgrafo de latexmath:[$G$] então latexmath:[$G$] é um *supergrafo* de latexmath:[$H$] * Um *subgrafo gerador* de latexmath:[$G$] é um subgrafo latexmath:[$H$] com latexmath:[$V(H) = V(G)$] * Seja latexmath:[${V}'$] um subconjunto não vazio de latexmath:[$V$]. O subgrafo de latexmath:[$G$] cujo conjunto de vértices é latexmath:[${V}'$] e o conjunto de arestas é o conjunto de todas as arestas de latexmath:[$G$] com ambos extremos em latexmath:[${V}'$], é chamado de *subgrafo de latexmath:[$G$] induzido pelo conjunto de vértices latexmath:[${V}'$] *. Denotamos por latexmath:[$G[{V}'\]$] o subgrafo induzido de latexmath:[$G$] por latexmath:[${V}'$]. * Seja latexmath:[${E}'$] um subconjunto não vazio de arestas de latexmath:[$E$]. O subgrafo de latexmath:[$G$] cujo conjunto de vértices é o conjunto dos extremos das arestas em latexmath:[${E}'$] é chamado de *subgrafo de latexmath:[$G$] induzido pelo conjunto de arestas latexmath:[${E}'$]*. * latexmath:[$G[V \setminus {V}'\]$], também denotado por latexmath:[$G-{V}'$] , é o subgrafo obtido a partir de latexmath:[$G$] pela remoção dos seus vértices latexmath:[$v$] que também estão em latexmath:[${V}'$], e remoção de toda aresta incidente em algum desses latexmath:[$v$]. * latexmath:[$G-{E}'$] é o subgrafo gerador de latexmath:[$G$] com conjunto de arestas latexmath:[$E \setminus {E}'$]. * latexmath:[$G+{E}'$] é o grafo obtido a partir de latexmath:[$G$] adicionando um conjunto de arestas latexmath:[${E}'$]. * Sejam os subgrafos latexmath:[$G_1, G_2 \subseteq G$]. latexmath:[$G_1$] e latexmath:[$G_2$] são *disjuntos (em vértices)* se latexmath:[$V(G_1) \cap V(G_2) = \emptyset$]. E são *disjuntos (em arestas)* se latexmath:[$E(G_1) \cap E(G_2) = \emptyset$]. ==== Exercício de fixação Reestude com rigor todas as definições e teoremas acima, entendendo e memorizando, depois feche o livro e responda as seguintes perguntas, anotando as respostas para as conferir somente ao final de todo o exercício: .. Utilizando a <> responda: 1) Quais são os vértices? 2) E as arestas? 3) Quais os extremos da aresta de maior peso? 4) Que vértices incidem nessa aresta? 5) Que vértices são adjacentes via essa aresta? 6) Que arestas incidem no vértice latexmath:[$A$]? 7) Que arestas são adjacentes via esse vértice? 8) Este é um multigrafo? 9) Tem algum auto-laço? 10) Tem arestas paralelas? 11) É um grafo simples? 12) É finito? 13) Qual é a ordem do grafo? 14) Qual o grau do vértice latexmath:[$A$]? 15) Qual o grau mínimo de latexmath:[$G$]? 16) Qual o grau máximo de latexmath:[$G$]? 17) Há algum vértice isolado? 18) Há algum vértice folha? 19) Quais são os vizinhos do vértice latexmath:[$A$]? 20) Os vértices latexmath:[$A$] e latexmath:[$D$] são independentes ou vizinhos? 21) As arestas de maior e de menor peso são independentes ou adjacentes? 22) Sendo este um grafo simples, vale o teorema que diz que a soma dos graus dos vértices é o dobro do número das arestas? + -- Respostas:: 01) Quais são os vértices? A,B,...,G. 02) E as arestas? AB, AD, BC, BE, BD, CE, DE, DF, EF, EG. 03) Qual a aresta de maior peso? DE, com peso 15. 04) Que vértices incidem nessa aresta? D e E. 05) Que vértices são adjacentes via essa aresta? D e E. 06) Que arestas incidem no vértice A? AB e AD. 07) Que arestas são adjacentes via esse vértice? AB e AD. 08) Este é um multigrafo? Não. 09) Tem algum auto-laço? Não. 10) Tem arestas paralelas? Não. 11) É um grafo simples? Sim, pois não possui auto-laço. 12) É finito? Sim. 13) Qual é a ordem do grafo? Sim. 14) Qual o grau do vértice A? 7, pois tem 7 vértices. 15) Qual o grau mínimo de G? 2, pois A,C,G têm grau 2, e nenhum outro vértice tem grau menor. 16) Qual o grau máximo de G? 5, pois E tem grau 5 e nenhum outro vértice tem grau maior. 17) Há algum vértice isolado? Não, todos os vértices incide em alguma aresta. 18) Há algum vértice folha? Não, pois nenhum os vértices tem grau 1 19) Quais são os vizinhos do vértice A? B e D. 20) Os vértices A e D são independentes ou vizinhos? Vizinhos. 21) As arestas de maior e de menor peso são independentes ou adjacentes? A aresta (DE) de maior peso (15) e a aresta (AD) (também poderia ser CE) de menor peso são adjacentes através do vértice D (também poderia ser o vértice E). 22) Sendo este um grafo simples, vale o teorema que diz que a soma dos graus dos vértices é o dobro do número das arestas? Sim. Conferindo: 22 = 2 x 11. -- .. Desenhe um grafo completo com 6 nodos e verifique se o número de arcos é latexmath:[$6 \cdot (6-1)/2 = 15$] Desenhe um grafo 4-partido. Desenhe um grafo 2-regular com 6 vértices. Desenhe um grafo conexo. Desenhe um grafo com 2 partições desconexas. Insira um vértice no grafo acima, depois acrescente o menor número de arestas que o torne conexo. Aponte um vértice de corte e uma aresta ponte, no grafo modificado. .. Dê exemplo de dois grafos idênticos, mas um pouco difíceis de reconhecer isto à primeira vista. .. Desenhe 2 grafos não idênticos mas isomórficos, depois prove que realmente são isomórficos. .. Dê exemplo de um digrafo que seja cíclico, outro que seja acíclico. .. Dê exemplo de um digrafo conexo, outro de um desconexo. Escreva a matriz de adjacência e a lista de adjacência para o digrafo desconexo. .. Elabore um grafo de 7 vértices e divida-o em dois: latexmath:[$G$] (com 4 vértices) e latexmath:[$H$] (com 3 vértices) podendo haver uma pequena interseção entre eles. Agora, ache latexmath:[$G-H$]. === Percursos em Grafos em Geral e em Cliques ==== Passeio ((Passseio)):: Um *passeio* (_walk_) ligando o vértice v~1~ ao vértice v~k~ de um grafo é uma sequência de arcos contíguos (cada arco começa no vértice onde o anterior terminou), de modo que a sequência começa em v~1~ e termina em v~k~. Tal sequência de arcos pode ser escrita somente como uma sequência dos nomes dos vértices, por exemplo v~1~v~2~v~3~ ... v~k~; ou como uma sequência somente das representações dos arcos como pares de vértices, por exemplo (v~1~v~2~), (v~2~v~3~), ..., (v~i~v~i+1~), (v~i+1~v~i+2~), ..., (v~k-1~v~k~); ou como uma sequência somente dos nomes dos arcos, por exemplo abcde; ou como uma sequência intercalando nomes de vértices e nomes de arcos, como em AcCgDfB. (Note que não se proibiu passar mais de 1 vez pelo mesmo vértice). (Exemplo no grafo das 7 pontes de Königsberg: AcCdAbBbAeD é um passeio desde A até D). ==== Passeio elementar ((Passeio elementar)):: Um passeio é dito *elementar* se não passar duas vezes pelo mesmo vértice. O grafo latexmath:[$AcCgDfB$] é um passeio elementar desde latexmath:[$A$] até latexmath:[$B$]. ==== Passeio simples ((Passeio Simples)):: Um passeio é dito simples se não passa mais que 1 vez em nenhum vértice ou aresta. ==== Trilha ((Trilha)):: Um passeio é chamado de trilha se não passa duas vezes pela mesma aresta. No grafo: _AaBfDeAcCgD_ é uma trilha desde latexmath:[$A$] até latexmath:[$D$]. Note que passou 2 vezes pelos vértices latexmath:[$A e D$], mas não passou nenhuma duas vezes por nenhuma aresta. ==== Ciclo ((Ciclo)):: Um *ciclo* é um passeio simples e fechado (o vértice inicial é o mesmo que o vértice final). (Exemplo no mesmo grafo: _AcCdAbBbA_ é um ciclo desde latexmath:[$A$] até latexmath:[$A$].) ==== Caminho no Digrafo ((Caminho no Digrafo)):: Em um digrafo, um *((caminho))* é um passeio no qual todos os arcos possuem a mesma orientação. (Exemplo no diagrama da definição de digrafo: 5, arco, 11, arco, 10) Um caminho não repete vértices nem arcos. Em um grafo não direcionado, a relação caminho é uma equivalência, pois é reflexiva (caminho(u,u)), simétrica (caminho(u,v) ssse caminho(v,u)) e transitiva (caminho(x,y) e caminho(y,z) implicam caminho(x,z)). ==== Circuito no Digrafo Circuito no Digrafo:: Em um digrafo, um *((circuito))* (ou ciclo direcionado simples) é um caminho simples (isto é, sem subcircuitos dentro dele) e fechado, retornando a qualquer vértice por onde o comecemos. (Exemplo: na <>, um circuito passará pelos vértices 1,2,4,3 e voltará ao vértice 1, sempre seguindo os arcos na direção correta.) [[fig_circuito]] .Digrafo com um circuito image::images/cap4/img14.eps[scaledwidth="30%"] ==== Grafo euleriano Grafo euleriano:: Um grafo conectado _G(V,A)_ é dito ser ((*euleriano*)) se existe uma _trilha_ (nela, cada aresta está presente e ocorre exatamente 1 vez) fechada (isto é, que volta ao ponto de partida). + ** *Exemplo 1:* Cada vértice do grafo (na <>) tem um grau par, portanto este é um grafo euleriano; realmente, seguindo as arestas em ordem alfabética obtém-se um circuito/ciclo euleriano. ** *Exemplo 2:* No clique latexmath:[$k5$] do Teorema de Ore (<>), se numerarmos os vértices como 1,2,3,4,5 no sentido dos ponteiros do relógio, o ciclo euleriano será 1,2,3,4,5,1,3,5,2,4,1.) [[fig_euleriano]] .Grafo euleriano image::images/cap4/img15.eps[scaledwidth="40%"] ===== Grafo semi-euleriano Grafo semi-euleriano:: Um grafo conectado e não-euleriano, _G_, é semi-euleriano se existe uma trilha que usa cada aresta de _G_ exatamente 1 vez (com isso, terá passado em todos os vértices pelo menos 1 vez, sem precisar fechar o circuito). No grafo da <>, se seguirmos as arestas na ordem _1,2,3,4,5,6,7_, teremos passado por todas as arestas exatamente 1 vez, portanto o grafo é *semi-euleriano*. Mas não fizemos um passeio simples, pois passamos mais de 1 vez em alguns vértices. Note que o grafo não é euleriano, pois tem vértices de grau ímpar. [[fig_semi_euleriano]] .Grafo semi-euleriano image::images/cap4/img16.eps[scaledwidth="40%"] ===== Teorema de Euler Teorema (Euler 1736) (pronuncie como ``Óilêr''):: Um grafo conectado latexmath:[$G$] é euleriano se e somente se o grau de cada um de seus vértices é par. Corolário::: Um grafo conectado latexmath:[$G$] é euleriano se e somente se ele pode ser decomposto em ciclos. Corolário II::: Um grafo conectado latexmath:[$G$] é semi-euleriano se e somente se ele possui exatamente 2 vértices de grau ímpar. Outra apresentação dos Teoremas de Euler:: Teorema de Euler 1::: - Se um grafo tem quaisquer vértices de grau ímpar, então ele não pode ter um Circuito de Euler. - Se um grafo é conexo e cada vértice tem grau par, então ele tem pelo menos um Circuito de Euler (usualmente, mais). Teorema de Euler 2::: - Se um grafo tem mais de 2 vértices de grau ímpar, então ele não pode ter uma Trilha de Euler. - Se o grafo é conexo e tem exatamente dois vértices de grau ímpar, então ele tem pelo menos uma Trilha de Euler (usualmente, mais). Tal trilha deve começar em um dos vértices de grau ímpar e terminar no outro. Teorema de Euler 3::: - A soma dos graus de todos os vértices de um grafo é um número par (exatamente o dobro do número de arestas). - Em cada grafo, o número de vértices de grau ímpar tem que ser par. [width="100%",cols="^1,^2,^3",frame="topbot",options="header,footer"] |==== |Número de vértices de grau IMPAR em G |Número de Circuitos de Euler |Número de Trilhas de Euler (passando por vértices de todos os vértices) | 0 | ≥1 | ≥ 1 (pois um circuito também é uma trilha) | 1 | Condição impossível | Condição impossível | 2 | 0 | ≥ 1 (começam em um vértice de grau ímpar, terminam no outro) | ≥2 | 0|0 |==== ==== Grafo hamiltoniano Grafo hamiltoniano:: + -- Um grafo latexmath:[$G(V,A)$] é dito ser hamiltoniano se existe um ciclo que passa exatamente uma vez em cada um dos vértices de latexmath:[$G$]. (O ciclo é uma sucessão de arestas adjacentes que visita todos os vértices do grafo uma só vez, sendo o último vértice visitado adjacente ao primeiro.) Todo grafo completo (clique) que contém mais de 2 vértices é hamiltoniano. .Grafo hamiltoniano image::images/cap4/img17.eps[scaledwidth="40%"] -- Teorema::: Um grafo completo de latexmath:[$n$] vértices tem latexmath:[$(n-1)!/2$] ciclos hamiltonianos. Prova do Teorema::: Fixe um vértice latexmath:[$v_1$]. O número de ciclos hamiltonianos começando e terminando nele (por exemplo, latexmath:[$v_1 v_2 \cdots v_n v_1$]) é o número de permutações com os latexmath:[$n-1$] outros vértices latexmath:[$\{v_2, \ldots ,v_n\}$], portanto é latexmath:[$(n-1)!$] Mas cada ciclo está sendo percorrido em 2 sentidos, direto e inverso (e.g.: 1234561 e 1654321), portanto, corrigindo, há latexmath:[$(n-1)!/2$] ciclos hamiltonianos começando e terminando em latexmath:[$v_1$]. Mas, por causa da circularidade (123451 é o mesmo que 234512 que é o mesmo que 3451234 que é o mesmo que ...), todos os ciclos começando e terminando em qualquer dos outros vértices diferentes de latexmath:[$v_1$] já estão contados. Portanto, o número de ciclos hamiltonianos é latexmath:[$(n-1)! / 2$]. ===== Grafo semi-hamiltoniano Grafo Semi-hamiltoniano:: Um grafo latexmath:[$G(V,A)$] é dito ser *semi-hamiltoniano* se não é hamiltoniano e existe um passeio que passa exatamente uma vez em cada um dos vértices de latexmath:[$G$]. .Grafo Semi-hamiltoniano image::images/cap4/img18.eps[scaledwidth="25%"] Teorema (Dirac 1952):: Uma condição suficiente, mas não necessária, para que um grafo simples latexmath:[$G$] com latexmath:[$n (>2)$] vértices seja hamiltoniano é que o grau de todo vértice de latexmath:[$g$] seja latexmath:[$\geq n/2$]. image::images/cap4/img19.eps[scaledwidth="40%"] ===== Teorema de Ore Teorema (Ore 1960):: Uma condição suficiente, mas não necessária, para que um grafo simples latexmath:[$G$] com latexmath:[$n (>2)$] vértices seja hamiltoniano é que a soma dos graus de cada par de vértices não adjacentes seja no mínimo latexmath:[$n$]. Exemplo::: A condição é satisfeita no clique latexmath:[$k5$] (<>). E, se numerarmos os vértices como 1,2,3,4,5 no sentido dos ponteiros do relógio, o ciclo será 1,2,3,4,5,1. [[fig_ore]] .Grafo ilustrando o Teorema de Ore image::images/cap4/img20.eps[scaledwidth="40%"] [[problema_caminho_mais_curto]] ==== Problema do caminho mais curto O problema do caminho mais curto consiste na minimização do custo total de travessia de um grafo ponderado (com custos associados a cada aresta) desde um vértice origem até um vértice destino. Se for oferecida como optativa a disciplina Análise (da complexidade) e Projeto de Algoritmos (do Bacharelado em Ciência da Computação, da UFPB), você poderá aprender e implementar algoritmos (tais como o de Dijkstra e o de Bellman-Ford) que resolvem o problema de forma muito eficiente. Exemplo::: Na <>, o caminho de custo mínimo entre latexmath:[$D$] e latexmath:[$E$] não é latexmath:[$D-E$], mas sim latexmath:[$D-F-E$], com uma custo total de latexmath:[$6+8 = 14$]. [[fig_caminho_mais_curto]] .Exemplo de grafo para cálculo do caminho mais curto image::images/cap4/img21.eps[scaledwidth="35%"] ==== Problema do carteiro chinês O problema do carteiro chinês consiste em encontrar um caminho mais curto ou um circuito fechado que, pelo menos uma vez, visite cada aresta de um grafo conectado. (Sim, quando o grafo possui um circuito euleriano (um passeio fechado que abrange toda aresta uma vez), esse circuito é uma solução ótima.) Exemplo::: Grafo não direcionado. Você tem 4 vértices 1,2,3,4. Os arcos, não direcionados, têm comprimentos: latexmath:[$(1,2) = 3; (1,3) = 12; (1,4) = 10; (2,3) = 4; (3,4) = 5$]. Desenhe o grafo. O carteiro precisa sair do vértice 1 e voltar a ele no final, passando por cada arco pelo menos 1 vez. Qual o passeio de menor comprimento total? (Resposta: passar nos vértices 1,2,3,4,1,2,3,2,1, percorrendo latexmath:[$12+5+10+3+4+4+3 = 41$] unidades de comprimento). ==== O problema do caixeiro viajante O problema do caixeiro viajante (TSM = Travelling SalesMan; TSP = Travelling Sales Person) consiste na procura de um circuito que possua o menor comprimento total, começando numa cidade qualquer, entre várias, visitando cada cidade precisamente uma vez e regressando à cidade inicial. Ver algoritmo aproximado, acima. === Árvores e Árvores Geradoras (((Árvores))) Um grafo conexo que não contém ciclos é chamado de árvore. Um grafo que não contém ciclos é uma floresta (portanto, uma floresta é uma união disjunta de árvores; e corresponde a um grafo disjunto; note que estamos falando de grafos (não de digrafos), portanto as arestas não são direcionadas). Seguindo o costume, chamaremos de nodos aos vértices de uma árvore. Uma árvore é denominada enraizada se um nodo é escolhido como especial, passando a ser chamado de raiz da árvore. Uma árvore que não é enraizada é denominada livre. Os nodos vizinhos à raiz são chamados de seus filhos ou ramos, e ela chamada de pai deles. Estes filhos levam a outros nodos que também possuem outros filhos deles, que os têm por pais. E assim por diante. Os nodos que não possuem filhos são conhecidos como folhas (nomenclatura melhor que nodos- terminais). Para cada folha, existe um só caminho entre a raiz e ela. Teorema:: Num grafo que é uma árvore, toda sua aresta é uma aresta de corte (ver definição, acima). Teorema:: Se latexmath:[$G$] é uma árvore com latexmath:[$n$] nodos, então latexmath:[$G$] possui latexmath:[$n-1$] arestas. Teorema:: Se latexmath:[$F$] é uma floresta com latexmath:[$n$] nodos e latexmath:[$k$] componentes conexos, então latexmath:[$F$] contém latexmath:[$n-k$] arestas. Teorema:: Seja latexmath:[$G$] um grafo de ordem latexmath:[$n$]. latexmath:[$G$] é uma árvore se, e somente se, latexmath:[$G$] é conexo e contém latexmath:[$n-1$] arestas. Teorema:: Seja latexmath:[$G$] um grafo de ordem latexmath:[$n$]. latexmath:[$G$] é uma árvore se, e somente se, latexmath:[$G$] não possui ciclos e contém latexmath:[$n-1$] arestas. Teorema:: Seja latexmath:[$T$] uma árvore (enraizada) de ordem latexmath:[$n \geq 2$]. Então latexmath:[$T$] possui no mínimo 1 folha. ==== Árvore Geradora (((Árvore, Geradora))) Dado um grafo conexo latexmath:[$G$], podemos sucessivamente remover uma qualquer aresta que esteja em um ciclo, até que não mais reste nenhum ciclo. Deste modo, teremos removido o menor número de arestas (latexmath:[$|E| - |V| + 1$]) necessário para transformar o grafo em acíclico e, portanto (uma vez que também é conexo), em uma árvore que contém todos os vértices de latexmath:[$G$] e será chamada de *árvore geradora* (ou árvore extensora, ou árvore de cobertura) de latexmath:[$G$]. Muitas árvores diferentes (e não serão isomórficas) podem ser geradoras de um mesmo grafo. Se o grafo for ponderado (cada aresta tendo um peso que representa quão desfavorável ela é), e se atribuirmos um peso à árvore geradora que seja calculado pela soma dos pesos das arestas que a compõem, então uma *árvore geradora mínima* (ou de peso total mínimo, ou de custo mínimo) é uma árvore geradora com peso menor ou igual a cada uma de todas as outras árvores geradoras possíveis. Qualquer grafo tem uma *((floresta)) de árvores mínimas*, que é uma união de árvores geradoras mínimas de cada uma de suas componentes conexas. [[fig_arvore_geradora]] .Arvore geradora mínima em negrito image::images/cap4/img22.eps[scaledwidth="40%"] Neste grafo, um peso aproximadamente igual ao seu comprimento foi atribuído a cada aresta. Uma árvore geradora mínima deste grafo está em negrito. === Atividades NOTE: resolva os exercícios abaixo, sem olhar as respostas. Só depois compare sua resposta com a deste livro (adaptei a partir de http://goo.gl/mfvvx2 ) . Utilize o algoritmo de força bruta para resolver o problema do caixeiro viajante para o grafo das quatro cidades mostradas abaixo. + [width="100%", cols="^.^",frame="none",grid="none"] |==== |image:images/cap4/img23.eps[width="150"] |==== . Pode um grafo ter um circuito euleriano , mas não um hamiltoniano? Explique sua resposta. . Pode um grafo ter um circuito hamiltoniano, mas não um euleriano ? Explique sua resposta. . No grafo abaixo, coloque em negrito arestas para indicar um circuito hamiltoniano. + [width="100%", cols="^.^",frame="none",grid="none"] |==== |image:images/cap4/img26.eps[width="130"] |==== . Qual é o grau (ou valência) do vértice A no grafo abaixo? + -- image::images/cap4/img28.eps[width="150"] [width="100%", cols="<,<,<,<", frame="none", grid="none"] |==== |a) 3 |b) 4 |c) 5 |d) 6 |==== -- . Qual das seguintes afirmações sobre um grafo conexo sempre é verdade? .. Cada par de vértices é ligado por uma única aresta. .. Um caminho de arestas existe entre quaisquer dois vértices do gráfico. .. Há um número par de vértices do gráfico. .. Há um número par de arestas no gráfico. . Qual dos grafos à abaixo tem um circuito euleriano? + -- image::images/cap4/img29.eps[scaledwidth="40%"] .. Grafo I, pois há um número par de arestas em cada um de todos os seus nodos. .. Grafo II, pois há um número par de arestas em cada um de todos os seus nodos. .. Ambos I e II .. Nem I nem II -- . Considere o caminho representado pela sequência de arestas numerados no gráfico seguinte. Por que o caminho não representa um circuito de Euler (pronuncie como ``Óilêr'')? + -- image::images/cap4/img30.eps[width="160"] .. O caminho não inicia e para no mesmo vértice. .. O caminho não cobre todas as bordas do gráfico. .. O caminho utiliza algumas arestas mais do que uma vez. .. O caminho não toca cada vértice do gráfico. -- . Se um gráfico tem 8 vértices de grau (valência) ímpar, qual é o número mínimo de arestas que têm de ser adicionadas (ou duplicadas) para que o grafo se transforme num euleriano ? + [width="100%", cols="<,<,<,<",frame="none",grid="none"] |==== |a) 2 |b) 4 |c) 6 |d) 8 |==== . Quais das seguintes sequências de letras descreve um circuito hamiltoniano para o grafo abaixo? + -- image::images/cap4/img31.eps[width="130"] [width="100%", cols="<,<",frame="none",grid="none"] |==== |a) latexmath:[$ABCDEFGA$] |c) latexmath:[$ACBFGDEA$] || |b) latexmath:[$ACBAEGFDEA$] |d) latexmath:[$ABCDGEF$] |==== -- . Para o grafo abaixo, qual é o custo do circuito hamiltoniano obtido usando o algoritmo do vizinho mais próximo (ainda não visitado), começando por latexmath:[$A$]? + -- image::images/cap4/img32.eps[width="160"] [width="100%", cols="<,<,<,<",frame="none",grid="none"] |==== |a) 60 |b) 54 |c) 62 |d) 66 |==== -- . Para o problema do caixeiro viajante (TSM ou TSP) (circuito hamiltoniano) aplicado a seis cidades, quantas tours são possíveis (e quantas são únicas)? + [width="100%", cols="<,<,<,<",frame="none",grid="none"] |==== |a) 60 possíveis |b) 120 possíveis |c) 360 possíveis |d) 720 possíveis |==== . Para o grafo abaixo, qual é o custo do circuito hamiltoniano obtido pelo algoritmo obtido usando o algoritmo das arestas ordenadas. + -- image::images/cap4/img33.eps[width="160"] [width="100%", cols="<,<,<,<",frame="none",grid="none"] |==== |a) 220 |b) 225 |c) 235 |d) 295 |==== -- . Um grafo latexmath:[$G$] tem 100 vértices e é formado por duas componentes conexas, cada uma delas sendo um grafo completo. Qual o menor número de arestas que latexmath:[$G$] pode ter? . Um grafo _G_ tem 100 vértices e é formado por duas componentes conexas, cada uma delas sendo um grafo completo. Qual o menor número de arestas que _G_ pode ter? === Soluções . Caminhos ABCDA e ACBDA têm custo 155. Caminho ABDCA tem o mínimo custo, 120. . Sim. Por exemplo, o grafo abaixo. + -- image::images/cap4/img24.eps[width="40%"] -- . Sim. Por exemplo, o grafo abaixo. + -- image::images/cap4/img25.eps[width="40%"] -- . {zwsp} + -- image::images/cap4/img27.eps[width="40%"] -- . D . B . A . C . B . C . D (corresponde a latexmath:[$AEDCBA: 12+8+10+20+16=66$]) (Note que esta é somente uma resposta aproximada, e o mínimo exato é latexmath:[$ABDCEA = 16+12+10+15+12= 65$]) . A (latexmath:[$60/6 = 10$] únicas) . C (corresponde a latexmath:[$ACEBDA$]) . B (que corresponde a latexmath:[$8+20+15 = 43$] minutos) . Quando um componente tem latexmath:[$50-y$] vértices, terá latexmath:[$(50-y)(49-y)/2$] arestas, e o outro tem latexmath:[$50+y$] vértices e terá latexmath:[$(50+y)(49+y)/2$] arestas, totalizando latexmath:[$2450+y^2$] arestas; quando cada componente tem igual número de vértices, 50, cada um terá latexmath:[$50(50-1)/2 = 50 \cdot 49/2$] arestas, e latexmath:[$G$] terá o dobro disso, *2450*, que será o mínimo desejado. === Recapitulando Parabéns! Você concluiu o capítulo 6, só falta mais um capítulo! E, se você foi disciplinado e realmente ``suou'' estudando 4 a 8 h cada semana, deve ter aprendido muitas coisas da parte básica da ``Teoria dos Grafos'' que lhe serão indispensáveis ou muito úteis em todo o resto do curso e sua vida profissional: conceitos básicos e propriedades de grafos; grafos completos (cliques), bi e k-partidos, regulares, rotulados, valorados, conexos, isométricos; conceitos básicos de digrafos; representações de grafos e digrafos em computadores; passeios, ciclos, trilhas, caminhos, circuitos, grafos eulerianos e hamiltonianos, problemas do caminho mais curto, do carteiro chinês e do caixeiro viajante. Muitas e importantes novidades. Para você treinar ainda melhor, recomendamos a Lista de Exercícios sobre Grafos, Prof. Antonio Alfredo Ferreira Loureiro, http://goo.gl/ByNhuq, com soluções em http://goo.gl/jnmMSF. No próximo capítulo, você será introduzido à Análise Combinatória, que analisa estruturas e relações discretas procurando determinar métodos de enumeração ou contagem nelas: Você relembrará técnicas básicas de contagem (permutações, arranjos, combinações), relações de recorrência e coeficientes binomiais, e verá outras sequências de contagem e o teorema de Ramsey. //// Sempre termine os arquivos com uma linha em branco. ////