Teoria Grafos

Prévia do material em texto

�
UNIVERSIDADE DO ESTADO DE MINAS GERAIS
FACULDADE DE INFORMÁTICA DE PASSOS
R. Dr Carvalho,1410 – Bairro Belo Horizonte - Passos/ MG
Fone: 3529 8092
��EMBED Paint.Picture�����
Curso…….. 	Sistemas de Informação
Disciplina… Teoria de Grafos					 Período: 3º
Professor…	Marcelo Galvao Fonseca
Teoria de Grafos - Plano de Ensino
EMENTA: 
Definição de Grafos, elementos dos grafos e propriedades. Breve histórico, primeiros problemas, aplicação. Isomorfismo, subgrafos, passeios, caminhos e circuito. Grafos de Euler, operações em grafos, caminho e circuito Hamiltoniano. Circuitos fundamentais e árvores. Propriedades de árvores, distância, centro, raio e diâmetro em árvores. Raiz e árvores binárias. Propriedades de ávores binárias. Cortes, conjuntos de corte, conectividade, separabilidade, e fluxo de rede. Representação de um grafo, algoritmos, menor distância, pesquisa horizontal, pesquisa em profundidade, árvore de expansão, teste de planaridade, performance de algoritmos em grafos.
OBJETIVOS GERAIS:
Apresentar uma teoria matemática de tratamento das relações entre elementos de conjuntos discretos em contraposição à “matemática do contínuo”. Formulação dos conceitos da topologia e geometria da posição. 
OBJETIVOS ESPECÍFICOS:
Permitir ao aluno desenvolver soluções para os problemas associados aos conjuntos de elementos discretos, intimamente ligados à matemática combinatória, aos processos de enumeração e de contagem. 
PROCEDIMENTOS DIDÁTICOS:
Aulas expositivas
CONTEÚDO PROGRAMÁTICO:
Introdução: 
Definições, Conceitos, Problema da Ponte de Königsberg, Breve histórico da Teoria de Grafos, Teoremas, Exercícios;
Caminhos e Circuitos: 
Isomorfismo, Subgrafos, Passeio, Caminho, Passeio fechado, Circuito, Grafos conectos, Linha de Euler, Circuito de Euler, Grafo de Euler, Teoremas, Operações em Grafos, Caminhos Hamiltonianos, Circuitos Hamiltonianos, Exercícios.
Representações de um grafo: 
Representação matricial, Representação vetorial, Algoritmo do caminho mínimo. O problema da coloração dos vértices de um grafo, O problema do caixeiro viajante.
Árvores: 
Definição, Teoremas, Grafos minimamente conectos, Distância entre vértices, Excentricidade, Centro de uma árvore, Métrica, Diâmetro e raio de uma árvore,Teoremas, Exercícios.
Árvores Binárias
Definição, conceitos, propriedades, raiz, contagem, árvore de expansão, circuitos fundamentais;
Conjuntos de cortes e vértices de corte
Conjunto de corte, propriedades, todos os conjuntos de corte de um grafo, circuitos fundamentais e conjuntos de corte, conectividade e separabilidade.
Grafos planares e grafos duais
Combinatória x geometria dos grafos, grafos planares, grafos de Kuratowski, diferentes representações de um grafo planar, detecção da planaridade de um grafo.
Algoritmos computacionais para grafos
Representações de um grafo, apresentação de um grafo, algoritmo do caminho minimo, verificação da conectividade e dos componentes, árvore de expansão, um conjunto de circuitos fundamentais, conjunto de corte e separabilidade, busca em profundidade, teste de planaridade, verificação de isomorfismo, performance e avaliação da complexidade de algoritmos.
AVALIAÇÃO:
Provas bimestrais, P1 e P2, e uma terceira prova substitutiva a faltas ou para recuperação de notas caso as primeiras provas não obtenham média suficiente para aprovação conforme regimento da unidade.
REFERÊNCIA BIBLIOGRÁFICA BÁSICA: 
Deo, Narsing, Graph theory with application to engineering and computer science; Prentice Hall
Maculan, Nelson; Grafos, teoria, modelos e algoritmos
Boaventura, Paulo; Grafos: teoria, modelos e algoritmos; Edgard Blücher Ltda
REFERÊNCIA BIBLIOGRÁFICA COMPLEMENTAR: 
Szwarcfiter e Markenzon, Jayme Luiz e Lilian; Estruturas de dados e seus algoritmos.
�
Teoria de Grafos
1-Introdução
	Um grafo G=(V,E) consiste de um conjunto de objetos V={v1,v2,….}, chamados de vértices (ou nós), e um outro conjunto E={e1,e2, ….}, chamados de arestas (ou arcos), tal que cada aresta ei pertencente a E está associado a dois nós vp e vq pertencentes a V. Uma aresta pode também ser identificada pelo par de vértices a ela associadas ei=(vp,vq). Um grafo pode também ser identificado por uma figura onde os vértices sejam designados por pontos, e as arestas por linhas que interliguem os vértices a elas associados.
Auto-Loop: São arestas cujos vértices são um único vértice. 
Arestas paralelas: São arestas distintas que possuam os mesmos dois vértices associados.
Grafos simples: São grafos sem auto-loops nem arestas paralelas.
Grafos genéricos: São grafos que possuam auto-loops e/ou arestas paralelas.
Nota 1: O formato do desenho de um grafo não é relevante na sua definição. O uso de linhas longas ou curtas, retas ou curvas, ou a disposição diferenciada dos vértices no desenho não interferem na definição do grafo. O importante é a definição do conjunto de vértices e dos arcos. Portanto, as figuras abaixo representam exatamente o mesmo grafo.
Nota 2: Eventualmente ao se desenhar um grafo, duas ou mais arestas se cruzam. Estes cruzamentos não devem ser confundido com a existência de mais um vértice. Sugere-se fortemente que os vértices sejam desenhados por bolas suficientemente destacadas para que não se confundam com possíveis cruzamentos de arestas.
Problema 1: A ponte de Königsberg
Duas ilhas C e D, formadas pelo rio Pregel em Königsberg (na época a capital do leste da Prucia, atualmente chamada de Kalinigrado no oeste da Russia), são interligadas entre si e às margens por sete pontes tal como mostra a figura abaixo.
O problema consiste de, partindo de qualquer margem, encontrar um caminho, acessando as quatro margens, passando exatamente uma única vez em todas as pontes, retornar ao ponto de partida. Sem naturalmente atravessar o rio a nado.
O problema foi proposto e ficou sem solução por centenas de anos, até que e, 1736 foi equacionado e resolvido por Leonard Euler (1707-1783). Sua publicação é considerada como o berço da Teoria de Grafos bem como o resto da Topologia.
Breve Histórico da Teoria de Grafos
Motivado pelo problema da ponte de Königsberg, Leonard Euler publicou em 1736 a proposição da modelagem no formato de grafos. Entretanto esta proposta não foi explorada e não teve continuidade nos 110 anos seguintes. Provavelmente avaliado como resultado de pouca importância. Em 1847 Kirchhoff propôs a teoria de árvores (subconjunto da teoria de grafos) para resolver problemas de circuitos elétricos. 1857 Cayey apresentou um método de enumeração de hidrocarburetos alifáticos. 1869 Jordan apresentou a teoria de árvores como modelagem estritamente matemática. 1968 ocorreu o primeiro simpósio nacional brasileiro de Pesquisa Operacional com destaques em teoria de grafos.
Incidência: Quando um vértice vp é um dos limites de uma aresta ei, diz-se que vp incide em ei, da mesma forma diz-se também que ei é incidente em vp.
Adjacência: Duas arestas não paralelas são ditas adjacentes, quando são incidentes em um mesmo vértice. Dois vértices são adjacentes quando existir uma aresta que incida em ambos.
Grau: O número de arestas incidentes sobre um vértice (neste caso os auto-loops contam dobrado), determina o grau deste vértice.
Corolário 1: A soma dos graus dos vértices de um grafo é o dobro do número de arestas do grafo.
Teorema 1.1: 
O número de vértices de grau impar num grafo é sempre par.
Prova 1.1:
Como a soma dos graus dos vértices de um grafo é o dobro do número de arestas do grafo, então a soma dos graus dos vértices de um grafo é sempre par.
Considere a soma dos graus dos vértices de um grafo em duas parcelas, onde a primeira parcela representa a soma dos graus dos vértices de grau impar, e a segunda parcela a soma dos graus dos vértices de grau par. Como a soma dos vértices de grau paré par, e a soma das parcela é par, então a soma dos graus dos vértices de grau impar é um número par.
Como a soma dos graus dos vértices de grau impar é par, então o número de parcelas desta soma é par. Cqd
Vétices Isolados: Os vértices que tenham grau zero são ditos vértices isolados.
Vértices pendentes: Os vértices que tenham grau 1 (um) são ditos vértices pendentes.
Problema 2:
Tres casas A, B e C, necessitam ser conectadas a tres serviços públicos subterrâneos, Água, Gaz e Esgoto. Seria possível efetuar ligações sem haver cruzamentos das redes? Ou qual seria a ligação com a menor quantidade de cruzamentos? 
Problema 3:
Nove amigos saem toda sexta-feira para tomar chopp num determinado bar da cidade. Sentam-se ao redor de uma mesma mesa redonda. De quantas formas diferentes eles podem se sentar de tal forma que nunca repitam os mesmos vizinhos?
Grafos Finitos: Um grafo G=(V,E) é finito quando o número de vértices de V é finito e quando o número de arestas de E também é finito.
Grafos Infinitos: Um grago G=(V,E) é infinito quando o número de vértices de V ou o número de arestas de E for infinito.
Grafos Nulos: São os grafos cuja soma dos graus de seus vértices é 0 (zero); ou seja, é um grafo sem arestas.
Exercícios
Desenhe todos os grafos simples com 1, 2, 3 e 4 vértices.
Desenhe um grafo com 64 vértices representando um tabuleiro de xadrez. Interligue estes vértices com arestas representando os movimentos admissíveis do cavalo.
Convença-se de que um grafo infinito com um número finito de arestas possui um número infinito de vértices isolados.
Convença-se de que um grafo infinito com um número finito de vértices possui pelo menos um vértices de grau infinito.
Convença-se de que o grau máximo de qualquer vértice num grafo simples com n vértices é n-1.
Mostre que o número máximo de arestas num grafo simples com n vértices é n(n-1)/2.
�
2-Caminhos e Circuitos
Isomorfismo: Dois grafos G e G’ são isomorfos se possuirem correspondência um a um entre seus vértices e arestas, tal que as relações de incidência sejam preservadas em ambos. Em outras palavras, se uma aresta e incidente nos vértices v1 e v2 de G, então sua aresta correspondente em G’ deve corresponder a v’1 e v’2 de G’, sendo v’1 e v’2 também correspondem a v1 e v2 de G.
Isomorfos	 não isomorfos
Condições necessárias (porém não suficientes) para verificar o isomorfismo:
G e G’ devem possuir o mesmo número de vértices;
G e G’ devem possuir o mesmo número de arestas;
G e G’ devem possuir o mesmo número de vértices de quaisquer grau;
�
Subgrafos: Um grafo G’ é um subgrafo de G se todos os vértices de G’ são vértices de G, se todas as arestas de G’ também são arestas de G, e cada aresta de G’ tenha os mesmos vértices em G.
Todo grafo é subgrafo de si mesmo;
Todo subgrafo de um subgrafo de G é subgrafo de G;
Todo vértice de G é um subgrafo de G;
Toda aresta com seus vértices incidentes de G é um subgrafo de G;
Subgrafos disjuntos por arestas: Dois ou mais subgrafos de G são disjuntos por arestas quando não possuirem nenhuma aresta em comum.
Subgrafos disjuntos por vértices: Dois ou mais subgrafos de G são disjuntos por vértices quando não possuirem nenhum vértice em comum.
Passeio: em um grafo G é uma seqüência finita e alternada de vértices e arestas, tal que cada aresta é precedida por um vértice incidente sobre a aresta, e sucedida pelo outro vértice sobre o qual ela incide. Nenhuma aresta pode ocorrer mais que uma vez em um mesmo passeio. Um passeio determina um subgrafo de G.
Passeio fechado: em um grafo G é um passeio cujo vértice inicial e final são o mesmo. Ou seja o passeio termina onde começou.
Passeio aberto: em um grafo G é um passeio onde o vértice inicial e final são diferentes.
Caminho: em um grafo G é um passeio em que nenhum vértice é percorrido mais que uma vez.
Circuito: é um passeio fechado em que apenas o vértice inicial e final são percorridos mais que uma vez.
Grafos conectos: Um grafo é conecto se e somente se é sempre possível encontrar um caminho entre quaisquer dois de seus vértices.
Grafos disconectos: Um grafo é disconecto se existir pelo menos um par de vértices onde não seja possível encontrar um caminho que os interligue.
Um grafo disconecto consiste de um ou mais subgrafos conectos. Cada um destes subgrafos conectos é chamado de componente.
Teorema 2.1
Um grafo G é disconecto se e somente se seus vértices V podem ser particionados em dois subgrupos disjuntos V1 e V2 tal que não exista nenhuma aresta de G que ligue nenhum vértice de V1 a qualquer vértice de V2.
Prova:
Suponha que exista tal particionamento. Considere dois vértices arbitrários a e b de G, tal que a pertença a V1 e b pertença a V2. Nenhum caminho pode existir entre a e b, caso contrário existiria pelo menos uma aresta que interligaria um vértice de V1 a um vértice de V2.
Seja G um grafo disconecto. Considere a um vértice de G. Seja V1 o conjunto de vértices de G que sejam interligados a a por algum caminho. Se G é um grafo disconecto, então V1 não incluirá todos os vértices de G. Os vértices remanescentes formarão um conjunto não vazio V2 de vértices de G. Então, por construção, nenhum vértice de V1 é interligável a qualquer vértice de V2. cqd.
�
Teorema 2.2
Se um grafo G (conecto ou disconecto) tem exatamente dois vértices de grau impar, então existe um caminho em G que interligue estes dois vértices.
 Prova:
Seja G’ uma componente de G que possua pelo menos um dos dois vértices de grau impar de G. Pelo teorema 1.1, todo grafo, e portanto qualquer componente, tem um número par de vértices de grau impar. Portanto os vértices vi e vj de G forçosamente pertencem a um mesmo componente. Então existe um caminho em G que interligue estes dois vértices. cqd.
Teorema 2.3
Um grafo simples G (sem auto-loops nem arestas paralelas) com n vértices e k componentes, pode ter no máximo (n-k)(n-k+1)/2 arestas.
Passeio de Euler (ou Linha de Euler): Um Passeio de Euler em um grafo G é um passeio fechado que percorra todas as arestas de G exatamente uma vez. Um grafo onde seja possível realizar um passeio de Euler é chamado de Grafo de Euler.
Teorema 2.4
Um grafo conecto G é um grafo de Euler se e somente se todos os vértices de G são de grau par.
 Prova:
Suponha que um grafo G é um grafo de Euler. Então existe um passeio fechado de Euler. Ao percorrer a linha de Euler, observa-se que a todo tempo ao chegar em um vértice sempre encontra-se uma aresta não percorrida pelo passeio partindo do vértice alcançado. Assim para cada aresta incidente sobre um vértice observa-se uma nova aresta incidida ainda não contada. O fechamento do passeio encerra exatamente no vértice de partida, desta forma comprova-se que todos os vértices de G são de grau par.
Suponha agora que todos os vértices de G sejam de grau par. Comecemos entao a construir um caminho, partindo de um vértice v arbitrário de G, tal que nenhuma aresta seja percorrida mais de uma vez. Desde que nenhum vértice é de grau impar, então sempre ao chegar em vértice haverá uma aresta de saida, exceto ao chegar no vértice inicial. Como este vértice v também é de grau par, se eventualmente for alcançado e ainda tiver arestas de saida sem ter sido percorrida, continua valendo sua condição de vértice final. Seja então h o passeio fechado construido como acima. Se h contiver todas as arestas de G, então G já é um grafo de Euler, como queriamos comprovar. Considere H o subgrafo de G formado pelo passeio h. Se h ainda não contiver todas as arestas de G, construa H’ um subgrafo de G, excluindo de G todas as arestas percorridas por h. Como G e H possuem todos os vértices de grau par, então H’ também possuirá somente vértices de grau par. Mais que isto, H e H’ possuirão pelo menos um vérticeem comum pois G é um grafo conecto. Seja u um vértice comum a H e H’. Como seu grau é par, indica que existem pelo menos duas arestas em u que não foram percorridas por h, pertencentes a H’. Então é possivel percorrer um passeio fechado h’ em H’ a partir de u. E este caminho poderia ter sido incorporado a h quando h tivesse passado por u, e com isto redefiniriamos h, H e H’. Este processo se repete indefinidamente até que se encontre um caminho de euler em G.
Com este teorema concluimos que o problema da ponte de Königsberg não tem solução, pois nem todos os vértices do grafo que o representa possui grau par.
Linha Unicursal: Um passeio aberto que percorra todas as arestas de um grafo G sem repetir nenhuma aresta é chamada de Linha Unicursal de G ou uma Linha Aberta de Euler em G. 
Evidentemente, se um grafo G possui uma Linha Unicursal, e for adicionado uma aresta em tal que interligue o vértice inicial ao vértice final da Linha Unicursal, obteremos uma Linha de Euler. Então, um grafo conecto é unicursal se e somente se possuir exatamente dois vértices de grau impar!
Grafo Unicursal: Um grafo G que possua uma linha Unicursal é chamado de Grafo Unicursal.
Teorema 2.5
Em um grafo conecto G com exatamente 2k vértices de grau impar, existem exatamente k subgrafos disjuntos por arestas que em conjunto contenham todas as arestas de G e que cada um seja um Grafo Unicursal.
Prova
Sejam os vértices de grau impar em um grafo G rotulados por v1, v2, … vk e w1, w2, …, wk em qualquer ordem arbitrária. Adicione k arestas em G interligando os pares de vértices (v1, w1), (v2, w2) … (vk, wk) e formando um novo grafo G’.
Desde que cada vértice de G’ passam a ter grau par, então G’ é contituido de uma Linha de Euler P. Se forem retirados de P as k arestas inseridas na construção de G’, P será quebrado em k passeios, sendo que cada passeio não possui repetições de arestas nem arestas comuns a passeios distintos. Considerando cada um dos k passeios como um subgrafo de G. Por construção cada um dos k subgrafos é unicursal; cqd.
Operações em Grafos
União: A união de dois grafos G1=(V1, E1) e G2=(V2, E2) é um terceiro grafo G3 escrito como G3 = G1 U G2 onde V3 = V1 U V2 e E3 = E1 U E2.
Intercessão: A intercessão de dois grafos G1=(V1, E1) e G2=(V2, E2) é um terceiro grafo G3 escrito como G3 = G1 G2 onde V3 = V1 V2 e E3 = E1 E2.
Soma Exclusiva: A soma exclusiva de dois grafos, G1 e G2, é um terceiro grafo G3, formado pela união dos vértices de G1 e G2 e das arestas de G1 e G2 mas não pelas arestas comuns a ambos. A soma exclusiva é escrita como G3 = G1  G2.
Conclusões 
G1 U G2 = G2 U G1 G1 G2 = G2 G1
G1  G2 = G2  G1
G U G = G G = G
G  G = nulo
Decomposição: Um grafo G pode ser decomposto em dois subgrafos G1 e G2 se G1 U G2 = G e G1 G2 = um grafo nulo. Em outras palavras, todas as arestas de G ocorrem em G1 ou G2 mas não em ambos. Alguns vértices entretanto podem ocorrer em ambos. Na decomposição, os vértices isolados são descartados. 
Deleção: Se v é um vértice de um grafo G, então G – v determina um subgrafo de G obtido pela deleção (remoção) de v. A remoção de v em G determina também a remoção de todas as arestas de G incidentes em v. Se d é uma aresta de G, então G – d determina um subgrafo de G obtido pela deleção (remoção) de d. Ou seja G  d. Entretanto a remoção de d em G não implica na remoção dos vértices incididos por em G.
Fusão: A fusão par de vértices v e w em um grafo G é a substituição deste par de vértices por um só vértice y tal que todas as arestas incidentes em v e w se tornem incidentes em y.Portanto a fusão de dois vértices não altera o número de arestas, mas apenas reduz e 1 (um) o número de vértices.
Teorema 2.6
Um grafo conecto G é um grafo de Euler se e somente se possa ser decomposto em circuitos.
Prova
Suponha que G possa decomposto em circuitos; isto é, G é a união de circuitos disjuntos por arestas. Como cada vértice de um circuito possui grau 2 (dois), então todos os vértices de G possuem grau par, e portanto implica em G ser um grafo de Euler.
Por outro lado, suponha que G seja um grafo de Euler. Considere um vértice v1. Existem pelo menos duas arestas incidentes em v1. Tomando uma destas arestas de incidentes em v1, chamemos de v2 o outro vértice de G incidido pela aresta escolhida. Novamente este vértice também terá grau par, e portanto haverá outra aresta saindo de v2 (diferente da aresta anterior), formando um caminho em G. Procedendo assim sucessivamente, eventualmente em algum instante alcançaremos um dos vértices já percorridos pelo caminho citado, formando assim um circuito T em G. Se removermos este circuito T de G, todos os vértices remanescentes ainda terão grau par, mesmo que o subgrafo restante não seja conecto. Tomando novo vértice deste subgrafo remanescente podemos repetir o procedimento acima, o processo só se encerrará quando todos os vértices e arestas forem excluidos. Provando desta maneira o teorema como desejamos.
Grafos arbitrariamente traçáveis: Um grafo de Euler é arbitrariamente traçável a partir de um vértice, se qualquer caminho que se trace a partir deste vértice sempre é possível percorrer todos os vértices e arestas deste grafo.
 a o o b o o
 
 o c o o o o
 d o o e o não arbitrariamente traçável
 arbitrariamemente traçável
Teorema 2.7
Um grafo de Euler G é arbitrariamente traçavel a partir de um vértice v se e somente se v pertença a qualquer circuito existente em G.
Caminhos Hamiltonianos em um grafo G é um caminho que percorra todos os vértices de G exatamente uma vez.
Circuitos Hamiltonianos em um grafo G é um caminho fechado que percorra todos os vértices de G exatamente uma vez, exceto, naturalmente, o primeiro e último vértice que é o mesmo. 
Naturalmente em um circuito hamiltoniano for retirada exatamente uma aresta (qualquer uma) obter-se-á um caminho hamiltoniano. 
Para se obter um caminho hamiltoniano em um grafo conecto G, pode-se disprezar de G os seus auto-loops e suas arestas paralelas, posto que cada vértice só poderá ser percorrido uma única vez.
Grafo completo: Um grafo simple é chamado de grafo completo se existir uma aresta entre quaisquer dois vértices do grafo. Nos grafos completos, cada vértice possui grau n-1 onde n é o número total de vértices do grafo. O numero total de arestas de um grafo completo é n(n-1)/2 (combinação de n, 2 a 2).
Número de circuitos hamiltonianos em um grafo: Um dado grafo pode possuir mais de um circuito hamiltoniano. Nosso interesse está em descobrir todos os circuitos hamiltonianos disjuntos por arestas, em um grafo. Determinar o número de circuitos (ou caminhos) hamiltonianos em um grafo é por vezes um problema sem solução. Entretanto…
Teorema 2.8
Em um grafo completo com n vértices, existem (n-1)/2 circuitos hamiltonianos disjuntos por arestas se e somente se n for impar e maior que 1.
Teorma 2.9
Se em um grafo simples G que possua todos os vértices com grau maior ou igual a n/2, onde n é o número de vértices de G, então existe um circuito hamiltoniano em G.
Exercícios do capítulo 2
Prove que todo grafo simples com n vértices, todos possuindo grau 2 são isomorfos.
Desenhe um grafo conecto tal que se torne disconect se qualquer uma de suas arestas for removida.
Desenhe todos os grafos simples e conectos com 1, 2, 3, 4 e 5 vértices.
Desenhe um grafo que possua um caminho hamiltoniano mas que não possua um circuito hamiltoniano.
�
Representações de um grafo
Matricial:
Considere um grafo simples G com n vértices, enumeradosde v1, v2, … vn. Considere suas arestas representadas por (vi, vj) interligando os vértices vi e vj. Pode-se representar G atravéz de uma matriz quadrada n x n, dispondo os vértices de G em cada linha e em cada coluna; e cada elemento desta matriz, associado à linha vi e à coluna vj possui o valor 0 (zeros) se não existir nenhuma aresta que interligue vi a vj, ou 1 (um) se existir. 
Considere o grafo abaixo representando algumas cidades do sudeste brasileiro e algumas das estradas que as interligam.
Belo Horizonte 		 Juiz de Fora Rio de Janeiro
 O 
Divinopolis 		 Barbacena Volta Redonda
 O 
Passos Varginha 		 Aparecida do Norte
 O 
 Poços de Caldas 		 São Paulo
 
 BH DV PA JF BC VG PC RJ VR AN SP
		 1 2 3 4 5 6 7 8 9 10 11
Belo Horizonte	1 0 1 0 1 1 1 0 0 0 0 0
Divinopolis	2 1 0 1 0 1 0 0 0 0 0 0
Passos		3 0 1 0 0 0 1 1 0 0 0 1
Juiz de Fora	4 1 0 0 0 1 0 0 1 0 0 0
Barbacena	5 1 1 0 1 0 1 0 0 0 0 0
Varginha		6 1 0 1 0 1 0 0 0 1 0 1
Pocos de Caldas	7 1 0 1 0 0 0 0 0 0 0 1
Rio de Janeiro	8 0 0 0 1 0 0 0 0 1 0 0
Volta Redonda	9 0 0 0 0 0 1 0 1 0 1 0
Aparecida do Norte	10 0 0 0 0 0 0 0 0 1 0 1
São Paulo	11 0 0 1 0 0 1 1 0 0 1 0
	Esta representação matricial de um grafo permite que cada elemento da matriz não só indique a existência ou não de uma aresta que interligue os vértices associados, mas também que apresente até mesmo o esforço necessário para se deslocar de um vértice até o outro por esta aresta. No exemplo acima este esforço poderia ser a própria distância. Assim, na matriz cada elemento seria 0 (zero) se não houvesse estrada interligando ou d, a distância entre os vértices por esta estrada. Apesar de ser possível representar auto-loops, a forma matricial não é capaz de representar arestas paralelas. Observe que esta matriz apresenta os dados de forma duplicada, é uma matriz simétrica, a triangular superior é igual à tringular inferior. A dimensão da matriz é proporcional ao quadrado do número de vértices. Assim, em grafos com grande número de vértices, esta matriz assume dimensões gigantescas. É comum a existência de grafos com grande número de vértices mas cada vértice (em média) com grau muito baixo, e portanto poucas arestas. Nestes casos a representação matricial seria desnecessáriamente grande.
	Se tomarmos um dos vetores linha de uma matriz representativa de um grafo, teremos a relação das vizinhanças do vértice associado a este vetor. Observe que a multplicação booleana deste vetor com a matriz irá representar as vizinhaças deste vértice com distância 2 no grafo, conforme mostramos abaixo…
Passos		3 0 1 0 0 0 1 1 0 0 0 1
 X
 BH DV PA JF BC VG PC RJ VR AN SP
		 1 2 3 4 5 6 7 8 9 10 11
Belo Horizonte	1 0 1 0 1 1 1 0 0 0 0 0
Divinopolis	2 1 0 1 0 1 0 0 0 0 0 0
Passos		3 0 1 0 0 0 1 1 0 0 0 1
Juiz de Fora	4 1 0 0 0 1 0 0 1 0 0 0
Barbacena	5 1 1 0 1 0 1 0 0 0 0 0
Varginha		6 1 0 1 0 1 0 0 0 1 0 1
Pocos de Caldas	7 1 0 1 0 0 0 0 0 0 0 1
Rio de Janeiro	8 0 0 0 1 0 0 0 0 1 0 0
Volta Redonda	9 0 0 0 0 0 1 0 1 0 1 0
Aparecida do Norte	10 0 0 0 0 0 0 0 0 1 0 1
São Paulo	11 0 0 1 0 0 1 1 0 0 1 0
 =
Cid dist 2 de passos 1 0 1 0 1 0 1 0 1 1 1
Exercícios
Elabore um programa que lei os dados de um grafo a partir do teclado;que o presente na forma matricial; que a partir de um vértice dado como partida, verifique quais os vértices alcançáveis com 2 passos usando a multiplicação booleana mostrada no exemplo acima.
�
Outras representações de um grafo
	As informações associadas aos vértices e arestas de um grafo podem demandar representações especiais deste grafo. De uma forma genérica representamos um grafo por meio de um grupo de vetores, indicando a relação dos vértice e da relação de suas arestas. Uma das principais vantagens desta forma de representação está na economia de espaço, pois esta representação está na proporção direta de número de vértices e do número de arestas do grafo (contra o quadrado na representação matricial). Outra vantagem nesta forma está na possibilidade de representar auto-loops bem como arestas paralelas. 
	Considere mais uma vez o exemplo do grafo com as cidades acima, indicando agora em cada aresta o tamanho da aresta (ou a distância das cidades interligadas por esta estrada). Vamos ampliar o exemplo agora indicando algumas arestas paralelas.
Belo Horizonte 		 Juiz de ForaRio de Janeiro
 O 
Divinopolis 		 Barbacena Volta Redonda
 O 
Passos Varginha 		 Aparecida do Norte
 O 
 Poços de Caldas 		 São Paulo
�
Algoritmo de menor distância dos vértices de um grafo a partir de um vértice de partida dado.
	Este algoritmo trabalha sobre a representação vetorial dos vértices e arestas. Para cada vértice assinala sua situação não visitado, aberto ou fechado; indicando se o vértice ainda não foi analisado, se já foi encontrado algum caminho até ele, e se já foram vistoriados todos os vértices a partir dele. O objetivo é, partindo do vértice inicial, verificar todos os vértices adjacentes, e assinalar suas distâncias do vértice inicial. Cada vértice encontrando é assinalado como vértice aberto. Enquanto existirem vértices abertos, toma o próximo vértice aberto para analisar e encontra os próximos vértices adjacentes, assinalando sua distância ao vértice de partida. Cada vértice analisado é fechado e passa ao próximo vértice a aberto, até que todos os caminhos sobre o grafo a partir do vértice inicial sejam verificados.
PROGRAMA MENOR_DISTANCIA;
Inicio
	Inteiro 	N,	 		/ o número de vértices do grafo
		M,			/ o número de arestas do grafo
		AF (N),			/ o vetor indicativo de vértices abertos (0), 
/ ou fechados (1),
/ ou não visitado (-1)
		MenorDistancia (N), 	/ o vetor indicativo da menor distância encontrada 
					/ até este vértice
		Anterior (N),		/ o vértice anterior a este, por onde se chega pelo
					/ menor caminho
		V1 (M),			/ o primeiro vértice de uma aresta 
		V2 (M),			/ o segundo vértice de uma aresta
		Tamanho (M),		/ o tamanho (comprimento) da aresta
		NVA;			/ contador de número de vértices abertos
		Atual;			/ indicador do vértice atual
		Partida;			/ indicador do vértice de partida
		I, J, K, L		/ variaveis auxiliares diversas
	Ler n; 				/ lê o número de vértices do grafo
	Ler m; 				/ lê o número de arestas do grafo
	Para I:=1 ate N
	{	AF (I):=-1;			/ inicializa todos vértices não visitados
		MenorDistancia (I):=99999;	/ distância infinita
		Anterior (I):=-1;			/ 
	};
	Para J:=1 até M
	{	Ler V1(J);			/ lê as arestas
		Ler V2(J);			/
		Ler Tamanho (J);		/
	};
	Ler Partida;			/ lê qual o vértice de partida
	Atual := Partida;
	MenorDistancia (Partida) := 0;	/ o vértice de partida está a distância zero!
	AF (Partida) := 0;		/ abre o vértice de partida
	NVA:=1;			/ inicia contagem de vértices abertos;
	Enquanto NVA > 0 		/ loop principal do algoritmo
	{ 	FechaVertice (Atual);	/ analisa as adjacencias do vertice atual
		ProcuraProximoVerticeAberto;	
	};
	ImprimeAsMenoresDistanciasEncontradas;
Fim.
�
Procedimento FechaVertice (inteiro Atual);
Inicio
/ para cada aresta, se o vertice for uma das extremidades da aresta, abre os vertices
/ existentes na outra extremidade
	Para J := 1 ate M
	{	Se V1 (J) = Atual entao AbreVertice (V2 (J), Tamanho (J));
		Se V2 (J) = Atual entao AbreVertice (V1 (J), Tamanho (J));
	};
	AF (Atual) := 1;			/ fecha o vertice atual (adjacencias já analisadas);
	NVA := NVA – 1;		/ decrementa contagem de vértices abertos;
Fim;
Procedimento AbreVertice (Inteiro Destino, Distancia);
Inicio
	/ se a menor distância já encontrada ao vértice destino é maior que a distância
	/ encontrada pelo caminho atual, entao assinala a nova distância como menor
	/ distância, assinala o vértice atual como o anterior ao destino, e se o vértice 
	/ de destino não estava aberto, então abre este vértice para ser analizado.
	Se MenorDistancia (Destino) > MenorDistancia (Atual) + Distancia 
	Entao {	MenorDistancia (Destino) := MenorDistancia (Atual) + Distancia;
		Anterior (Destino) := Atual;
		Se AF (Destino) <> 0 
		Entao {	AF (Destino) := 0;
			NVA := NVA + 1;
		 };	
	 };
Fim;
�
Problema da coloração dos vértices de um grafo.
	Colorir os vértices de um grafo de tal forma que dois vértices adjacentes por uma aresta não possuam a mesma cor. Aplicar estas cores de forma a usar o menor número de cores diferentes possível.
	Este problema é uma representação genérica de alocação de recursos, onde os vértices representam as demandas destes recursos e as arestas representam as restrições de recursos comuns às entidades que os demandam. Por exemplo, alocar pessoas para trabalhar em projetos em determinados periodos, de tal forma que uma pessoa não seja alocado a dois projetos que transcorram em tempo simultâneo. Diversos outros exemplos desta natureza podem ser apresentados.
Problema do caixeiro viajante.
	Percorrer todas as cidades de uma região de forma a evitar passar por uma cidade mais que uma vez, e fazer este circuito na menor distância possivel.
	Este problema equivale a encontrar o circuito Hamiltoniano de um grafo. Como sabemos nem sempre é possivel atender a todas estas restrições. Entretanto para um caixeiro a viagem tem que ser realizada, e portanto alguma cidade pode ser efetivamente percorrida mais de uma vez a fim de viabilizar alguma solução. 
	Existem alguma variações nestes problemas que podem suavizar as necessidades. Por exemplo particionar o grafo de tal forma que as visitas sejam subdivididas por caixeiros distintos. Ou que um caixeiro realize cada partição em um dia diferente permitindo que a cada dia ele sempre volte para dormir em casa, e assim por diante.
	A busca nestes algoritmos é de encontrar a solução ótima, mas é fundamental identificar quando encontrar uma boa solução ou mesmo se satisfazer ao encontrar alguma solução viável.
�
3 – Árvores
Árvores são grafos conectos que não possuem nenhum circuito.
	O conceito de árvores é provavelmente o mais importante e de maior volume de aplicações em teoria de grafos. Alguns autores aceitam a definição de árvores nulas (sem nenhum vértice), entretanto não representa a concepção da maioria, e seguiremos neste texto excluindo esta possibilidade.
Exemplos de árvores:
Árvores genealógicas
Curso de rios e seus afluentes (sem registros de ilhas)
Código de endereçamento postal
Estruturas de diretórios e subdiretórios de discos de computador
Teorema 3.1
Existe um e somente um caminho entre quaisquer dois vértices de uma árvore T.
Prova:
Desde que T é uma árvore, portanto um grafo conecto, então existem um caminho entre quaisquer dois de seus vértices. Por outro lado se existir mais de um caminho entre algum par de seus vértices implicará na existência de um circuito, e neste caso T não seria uma árvore.
Teorema 3.2
Se em um grafo G existe um e só um caminho entre quaisquer par de seus vértices, então G é uma árvores.
Prova:
Se existe um caminho entre quaisquer par de vértices de um grafo G, então G é conecto. E se existir apenas um caminho entre quaisquer dois vértices de G, implica que G não possui nenhum circuito. Portanto G é uma árvore.
�
Teorema 3.3
Uma árvore com n vértices existem n – 1 arestas.
Prova:
Por indução temos que numa árvore com n = 1 e n = 2 vértices a afirmação do teorema é óbvia. Seja então T uma árvore com n vértices. Considere a aresta ep que interliga os vértice vi e vk. De acordo com o teorema 3.1 não existe nenhum outro caminho em T queinterlige vi e vk. Portanto a deleção de ep de T irá disconectar T em exatamente duas sub-árvores, Estas duas sub-árvores T1 e T2, possuem menos que n arestas cada e menos arestas que T possuia. Repetindo o processo de exclusão de arestas nas sub-árvores remanescentes encontraremos sub-árvores com 2 ou 1 vértices, comprovando o processo indutivo, pois a cada exclusão estaremos retirando uma aresta de cada vez.
Teorema 3.4
Qualquer grafo conecto com n vértices e n – 1 arestas é uma árvore.
Grafo minimamente conecto: um grafo conecto é dito minimamente conecto se ao ser excluído qualquer um de suas arestas ele se torne um grafo disconecto.
Teorema 3.5
Um grafo é uma árvore se e somente se for um grafo minimamente conecto.
Prova:
Se um grafo é minimamente conecto, então ele é conecto e não possui nenhum circuito, pois se possuisse algum circuito ele não seria minimamente conecto. Portanto é uma árvore. Por outro lado uma árvore é conecta, e por não possuir nenhum circuito, qualquer aresta que seja excluída de uma árvore o disconecta, portanto é minimamente conecto.
Teorema 3.6
Um grafo G com n vértices e n – 1 arestas, e nenhum circuito é conecto.
Prova:
Suponha por absurdo que exista um grafo G sem circuito, com n vértices e n – 1 arestas que seja disconecto. Neste caso G se constitui de dois ou mais componentes sem circuitos. Tomemos G1 e G2 quaisquer dois dos componentes de G, e seja v1 um vértice qualquer de G1 e v2 um vértice de G2. Se for criado uma nova aresta ek interligando v1 a v2, resultará na união de G1 e G2 por meio da nova aresta ek. Esta aresta não irá criar um circuito pois não havia nenhum outro caminho que interligasse v1 e v2 em G (pois estavam em componentes disconectas de G). Repetindo este procedimento até interligar todas as componentes de G, criariamos uma árvore (grafo conecto sem circuitos) com n vértices e mais que n – 1 arestas. O que contrariaria o teorema 3.3.
Os seis teoremas acima sintetizam as conclusões abaixo que servem como formas alternativas de definição de uma árvore. Assim podemos afirmar que um grafo G é uma árvore se
G é conecto e não possui circuitos, ou
G é conecto com n vértices e n – 1 arestas, ou
G não possui circuitos e tenha n vértices e n – 1 arestas, ou
Exista exatamente um caminho entre quaisquer dois vértices de G, ou
G é um grafo minimamente conecto.
�
Vértices Pendentes em uma árvore
Vértices pendentes em uma árvore são os vértices de grau 1 (um).
Toda árvore tem pelo menos dois vértices pendentes, podendo ter ainda vários outros. A razão para esta afirmação está na constatação que todo vértice de uma árvore tem grau pelo menos 1, pois a árvore é conecta. Com n vértices e n – 1 arestas, significa que existem 2 * (n – 1) graus a serem divididos entre n vértices. Como não pode haver nenhum vértice com grau zero, então existem pelo menos dois vértices de grau 1.
Teorema 3.7
Em qualquer árvore com dois ou mais vértices, existem pelo menos dois vértices pendentes.
A distância e o centro de uma árvore
Intuitivamente na figura abaixo percebemos que o vértice b é o vértice mais central da árvore. O objetivo é identificar se existe um (ou mais) vértice central ou o centro de uma árvore. 
 O c
 a b
 O O
 O d
Em um grafo conecto G, a distância d(vi, vk) entre dois de seus vértices vi e vk, é o comprimento do menor caminho (isto é do caminho com o menor número de arestas) entre eles.
O conceito de distância é válido para qualquer tipo de grafo conecto, não apenas para árvores.
Métrica; uma função de duas variáveis f(x, y) é dita de métrica se as propriedades abaixo forem observadas:
Não negatividade: 		f(x, y) >= 0, e f(x, y) = 0 se e somente se x = y;
Simetria:			f(x, y) = f(y, x);
Desigualdade triangular: 	f(x, y) <= f(x, z) + f(z, y) para qualquer z
A função que representa a distância entre dois vértices em um grafo satisfaz as condições 1 e 2 de forma óbvia. Para confirmar a terceira condição, basta identificar que a distância de um vértice x qualquer a outro vértice z, mais a distância de z a y não pode ser menor que a menor distância entre x e y pela própria definição da função distância. Portanto:
Teorema 3.8 
A distância entre os vértices de um grafo conecto é uma métrica.
Excentricidade E(v) de um vértice v em um grafo conecto G é a distância de v ao vértice mais distante de v em G. Ou seja
 					E (vi) = máx (distância d(vi, vk)) para todo vk em G
Centro de G: O centro de um grafo conecto G é o vértice de G que possuir a menor excentricidade.
Um grafo conecto pode possuir diversos centros. Um grafo que se consista exatamente de um circuito tem todos os seus vértices como centro do grafo.
Teorema 3.9 
Toda árvore tem 1 (um) ou 2 (dois) centros.
Prova
A distância máxima de um vértice vi a qualquer outro vértice vk numa árvore T ocorre sempre em um vértice pendente, ou seja, sempre vk é um vértice pendente. Se assim não fosse, haveria mais algum vértice além de vk em T com distância maior de vi, e portanto vk não seria o vértice mais distante de vi. Sabemos que T possui pelo menos dois vértices pendentes. Se deletarmos de T todos seus vértices pendentes, formaremos um novo grafo T’ que ainda seria uma árvore. A excentricidade de T seria reduzida de 1 (uma) unidade. Certamente o centro de T ainda persistiria em T’, e o centro de T seria o mesmo centro de T’. Repetindo o processo de exclusão dos vértices pendentes de T’, obtendo T’’, continuaremos a observar os mesmos resultados. Podemos prosseguir este processo até que restem apenas 1 ou 2 vértices. Enquanto existirem 3 ou mais o processo ainda pode ser repetido. O vértice (ou os dois vértices) remanescente(s) será(ão) o(s) centro(s) de T.
�
P1 – Turma primeiro semestre de 2003, 07 de abril de 2003
Aluno: ________________________________________________
Seja G-Passos um grafo onde os vértices representem todas as esquinas da cidade de Passos, e as arestas representem as ruas que interliguem estas esquinas (independente da mão de trânsito de veículos). Você poderia afirmar que este é um grafo simples ou não? Porque?
O grafo G-Passos, conforme definido acima, seria um grafo conecto ou não? Porque?
Em um grafo simples com n vértices, qual o grau máximo que um vértice pode ter?
Desenhe dois grafos simples com 5 vértices que não sejam isomorfos e justifique porque não são isomorfos.
Considere no grafo G-Passos definido na questão 1, os subgrafos Bairrok como sendo as esquinas e ruas do bairro k. O seria o subgrafo formado pela intercessão de dois destes subgrafos? (Considere que as ruas limites entre dois bairros fazem parte dos dois).
A – O conjunto apenas das esquinas comuns aos dois bairros;
B – O conjunto de todas as esquinas dos dois bairros;
C – O conjunto apenas das esquinas e ruas comuns aos dois bairros;
D – O conjunto de todas as esquinas dos dois bairros;
E – Um subgrafo nulo independente de quais bairros escolhidos.
Suponha que no grafo G-Passos a representação das vielas (beco sem saída), sejam feitas pela representação de vértices pendentes. Sabendo que existem vielas em Passos, podemos afirmar que o G-Passos é um grafo de Euler? Porque?
O que se pode dizer da relação entre o diâmetro e o raio de uma árvore que só possua um centro?
Considere a árvore genealógica T onde cada vértice represente uma pessoa, e as arestas a relação de paternidade entre duas pessoas. Ou seja de a é pai de b, então existe uma aresta direcionada de a para b. T poderia representar todas as pessoas de uma cidade? Porque?
Considere que na árvore T acima que estejam representadostodos os descendentes de um famoso milionário falecido recentemente (cuja fortuna era constituida apenas de um crédito bancário, não possuía nenhum bem imóvel). Considere ainda que nem todos os seus descentes representados em T ainda estejam vivos. Suponha que a justiça determine distribuir aos filhos do falecido, toda sua fortuna em partes iguais. Para os filhos que já tiverem falecidos, sua parte será distribuída aos netos, também em partes iguais, e assim sucessivamente. Imagine que o milionário tenha tido 3 filhos, seu filho mais velho tenha tido 2 filhos (seus netos), destes, o primeiro tenha tido outros 4 filhos (bisnetos), destes, o primeiro tenha tido um filho que se chamava João. Se o pai, o avô e o bisavô de João também já tivesse falecido, indique em forma de uma fração da fortuna, qual a parte que caberia ao João. Sugestão desenhe a árvore genealógica e calcule.
Se no problema acima estão representadas n pessoas (maior que 2), qual o número mínimo e o número máximo de descendentes sem filhos que podem existir?
A prova está fácil apesar das aparências. Tenha calma e faça uma boa prova.
_1092847946/’>