Teoria dos grafos

Grafo com quatro vértices e 6 arestas. É um grafo completo, conexo e planar.

Ateoria dos grafosoude grafosé um ramo damatemáticaque estuda as relações entre os objetos de um determinado conjunto. Para tal são utilizadas estruturas chamadas de grafos,$G(V,E)$,onde$V$é um conjunto não vazio de objetos denominadosvértices(ou nós) e$E$(doinglêsedges- arestas) é um subconjunto de pares não ordenados de V.

Dependendo da aplicação, arestas podem ou não ter direção, pode ser permitido ou não arestas ligarem um vértice a ele próprio e vértices e/ou arestas podem ter um peso (numérico) associado. Se as arestas têm um sentido associado (indicado por uma seta na representação gráfica) temos umdígrafo(grafo orientado). Um grafo com um único vértice e sem arestas é conhecido comografo trivial.

Estruturas que podem ser representadas por grafos estão em toda parte e muitos problemas de interesse prático podem ser formulados como questões sobre certos grafos. Por exemplo, a estrutura de ligações daWikipédiapode ser representada por um dígrafo: os vértices são os artigos da Wikipédia e existe uma aresta do artigoApara o artigoBse e somente seAcontém um link paraB.Dígrafos são também usados para representarmáquinas de estado finito.O desenvolvimento dealgoritmospara manipular grafos é um tema importante daciência da computação.

Histórico

O problema das pontes de Königsberg

O artigo deLeonhard Euler,publicado em 1736, sobre o problema dassete pontes de Königsberg,é considerado o primeiro resultado da teoria dos grafos.É também considerado um dos primeiros resultados topológicos nageometria;isto é, não dependente de quaisquer medidas. Isso ilustra a profunda conexão entre a teoria dos grafos etopologia.

Mais de um século após a publicação do artigo de Euler sobre as pontes deKönigsberge enquantoListingintroduzia o conceito de topologia,Cayleyfoi levado por um interesse em formas analíticas particulares decorrentes do cálculo diferencial para estudar uma classe particular de grafos, asárvores.Esse estudo teve diversas implicações naquímicateórica. As técnicas usadas por ele eram relacionadas a enumeração de grafos com propriedades particulares.

O primeiro livro didático sobre teoria dos grafos foi escrito porDénes Könige publicado em 1936.

Um dos problemas mais conhecidos em teoria dos grafos éproblema das quatro cores:"É possível que qualquer mapa desenhado num plano, dividido em regiões, possa ser colorido com apenas quatro cores de tal forma que as regiões vizinhas não partilhem a mesma cor?". O primeiro a notar o problema das quatro cores foiAugust Ferdinand Möbiusem 1840. Em 1852,Francis Guthrieescreveu em uma carta para seu irmão Frederick, estudante na University College London, sobre o problema. Mas nenhum deles conseguiu resolvê-lo. Então Frederick perguntou a um de seus professores,DeMorgan.

Definições de grafos e dígrafos

Na literatura, as definições básicas da teoria dos grafos variam bastante. Aqui estão as convenções usadas nesta enciclopédia.

Umgrafo direcionado(também chamadodígrafoouquiver) consiste de

• umconjuntoVdevértices(não vazio),
• umconjuntoEdearestase
• mapass,t:E→V,ondes(e) é afonteet(e) é oalvoda aresta direcionadae.

Umgrafo não direcionado(ou simplesmentegrafo) é dado por

• umconjuntoVdevértices(não vazio),
• umconjuntoEdearestase
• uma funçãow:E→P(V)que associa a cada aresta um subconjunto de dois ou de um elemento deV,interpretado como os pontos terminais da aresta.

Em um grafo ou dígrafocom pesos,uma função adicional E →Rassocia um valor a cada aresta, o que pode ser considerado seu "custo"; tais grafos surgem emproblemas de rota ótimatais como oproblema do caixeiro viajante.

Representação gráfica

Um grafo com seis vértices e 7 arestas

Os grafos são geralmente representados graficamente da seguinte maneira: é desenhado um círculo para cada vértice, e para cada aresta é desenhado um arco conectando suas extremidades. Se o grafo for direcionado, seu sentido é indicado na aresta por uma seta.

O grafo de exemplo exibido na figura é um grafo simples com o conjunto de vérticesV= {1, 2, 3, 4, 5, 6} e um conjunto de arestasE= { {1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6} } (com o mapeamentowsendo aidentidade).

Note que essa representação gráfica não deve ser confundida com o grafo em si (a estrutura abstrata, não-gráfica). Diferentes representações gráficas podem corresponder ao mesmo grafo.O que importa é quais vértices estão conectados entre si por quantas arestas.

O trabalho pioneiro deWilliam Thomas Tuttefoi de grande influência no desenho de grafos. Entre outras realizações, ele introduziu o uso de técnicas daálgebra linearpara desenhar grafos.

Convenções alternativas para a representação de grafos incluem representações por adjacência como empacotamento de círculos, onde vértices são representados como regiões disjuntas no plano e arestas são representadas por adjacências entre regiões; representações por intersecção no qual vértices são representados como objetos geométricos não disjuntos e arestas são representadas por suas intersecções; representações por visibilidade onde vértices são representados por regiões no plano e arestas são representadas por regiões com uma linha de visão desobstruída para cada vértice; desenhos confluentes, nos quais arestas são curvas suaves dentro de trilhos de trem; texturas onde vértices são linhas horizontais e arestas são linhas verticais;e visualizações damatriz de adjacênciade um grafo.

O desenho de grafos em superfícies diferentes do plano é também estudado.

Armazenamento de grafos em memória

Há diversas maneiras de armazenarmos grafos em computadores. A estrutura de dados usada dependerá tanto da estrutura do grafo quanto do algoritmo usado para manipulá-lo. Teoricamente, podemos dividir entre estruturas do tipo lista e do tipo matriz, mas em aplicações reais, a melhor estrutura é uma combinação de ambas. Estruturas do tipo lista são frequentemente usadas em grafos esparsos (grafos que possuem um pequeno número de arestas em relação ao número de vértices, oposto ao grafo denso, onde o número de arestas se aproxima do máximo de arestas possível) já que exigem menor uso da memória. Por outro lado, estruturas do tipo matriz fornecem um rápido acesso em algumas aplicações, mas podem consumir uma grande quantidade de memória.

Estruturas do tipo lista incluem alista de adjacênciaque associa a cada vértice do grafo uma lista de todos os outros vértices com os quais ele tem uma aresta e a lista de incidência, que armazena para cada vértice uma lista de objetos que representam as arestas incidentes a esse vértice.

Estruturas do tipo matriz incluem amatriz de incidência,uma matriz de 0's e 1's com suas linhas representando vértices e suas colunas as arestas e amatriz de adjacênciaonde ambas linhas e colunas possuem vértices. Em ambos casos um 1 indica dois objetos adjacentes e 0 indica dois objetos não adjacentes.

Definições de teoria dos grafos

Relações de incidência e de adjacência

Se uma aresta conecta dois vértices, então esses dois vértices são ditosincidentesà aresta. Usando o grafo ao lado como exemplo temos: 1 é incidente a 2 e 5, mas não é incidente a 3, 4 ou 6; 4 é incidente a 5, 3 e 6, mas não a 2 nem a 1.

Dois vértices são consideradosadjacentesse uma aresta existe entre eles. No grafo acima, os vértices 1 e 2 são adjacentes, mas os vértices 2 e 4 não são. O conjunto devizinhosde um vértice consiste de todos os vértices adjacentes a ele. No grafo-exemplo, o vértice 1 possui 2 vizinhos: vértice 2 e vértice 5.

Na computação, um grafo finito direcionado ou não-direcionado (com, digamos,nvértices) é geralmente representado por suamatriz de adjacência:umamatrizn-por-ncujo valor na linhaie colunajfornece o número de arestas doi-ésimo aoj-ésimo vértices.

Valência (Grau)

Avalência(ougrau) de um vértice é o número de arestas incidentes a ele. Se houverlaços,serão contados duas vezes. No grafo de exemplo os vértices 1 e 3 possuem uma valência de 2, os vértices 2, 4 e 5 têm a valência de 3 e o vértice 6 tem a valência de 1. SeEé finito, então a valência total dos vértices é o dobro do número de arestas. Em um dígrafo, distingue-se ograu de saída(o número de arestas saindo de um vértice) e ograu de entrada(o número de arestas entrando em um vértice). O grau de um vértice em um dígrafo é igual à soma dos graus de saída e de entrada. O grau de um vértice é definido somente quando o número de arestas incidentes sobre o vértice é finito.

• Lema do aperto de mãodiz que se os convidados de uma festa apertarem as mãos quando se encontrarem pela primeira vez, o número de convidados que apertam a mão um número ímpar de vezes é par. Também em grafos não direcionados a soma dos graus de todos os vértices é igual ao dobro do número de arestas.
  • Fórmula:Seja$G=(V,E)$um grafo não direcionado com$m$arestas. Então,

$2m=\sum _{v\in V}deg(v)$

Passeio

Grafo com cinco vértices e 9 arestas

Um passeio$p$entre dois vértices$A$e$B$,definido como$p(A,B)$,é uma lista alternada de vértices e arestas $p(A,B)=v_{0},e_{1},v_{1},e_{2},v_{2},...,e_{k},v_{k}$tal que

• $A=v_{0}$e$B=v_{k}$
• existe no mínimo uma aresta
• para$1\leq i\leq k$a aresta$e_{i}$incide sobre$v_{i-1}$e$v_{i}$

O tamanho de um passeio, definido por$\left\vert p\right\vert$corresponde ao número de arestas que possui, incluindo as repetições.Na figura ao lado, um passeio do vértice$a$até o vértice$d$possível é a lista$p(a,d)=a,e_{9},c,e_{2},b,e_{1},a,e_{9},c,e_{8},d$de tamanho$5$.Note que a aresta$e_{9}$se repete. É necessário listarmos as arestas em um passeio para distinguirmos entre as diversas arestas existentes quando estamos trabalhando em um grafo que não é simples. Em um grafo simples, basta listarmos os vértices.

Caminho

Caminhoé uma sequência de vértices tal que de cada um dos vértices existe uma aresta para o vértice seguinte. Um caminho é chamadosimplesse nenhum dos vértices no caminho se repete. Ocomprimento do caminhoé o número de arestas que o caminho usa, contando-se arestas múltiplas vezes. Ocusto de um caminhonum grafo balanceado é a soma dos custos das arestas atravessadas. Dois caminhos sãoindependentesse não tiverem nenhum vértice em comum, exceto o primeiro e o último.

No grafo de exemplo, (1, 2, 5, 1, 2, 3) é um caminho com comprimento 5, e (5, 2, 1) é um caminho simples de comprimento 2.

• Caminho eulerianoem um grafo é o caminho que usa cadaarestaexatamente uma vez. Se tal caminho existir, o grafo é chamadotraversável.Umciclo eulerianoé um ciclo que usa cada aresta exatamente uma vez.
• Caminho hamiltonianoem um grafo é o caminho que visita cadavérticeexatamente uma vez. Umciclo hamiltonianoé um ciclo que visita cada vértice uma só vez. O grafo do exemplo contém um caminho hamiltoniano. Enquanto determinar se um dado grafo contém um caminho ou ciclo euleriano é trivial, o mesmo problema para caminhos e ciclos hamiltonianos é trabalhoso.

Ciclo(ou circuito) é um caminho que começa e acaba com o mesmo vértice. Ciclos de comprimento 1 são laços. No grafo de exemplo, (1, 2, 3, 4, 5, 2, 1) é um ciclo de comprimento 6. Umciclo simplesé um ciclo que tem um comprimento pelo menos de 3 e no qual o vértice inicial só aparece mais uma vez, como vértice final, e os outros vértices aparecem só uma vez. No grafo acima, (1, 5, 2, 1) é um ciclo simples. Um grafo chama-seacíclicose não contém ciclos simples.

Laço(loop) num grafo ou num dígrafo é uma arestaeemEcujas terminações estão no mesmo vértice.

Tipos de grafos

• Grafo simplesé um grafo não direcionado, sem laços e existe no máximo uma aresta entre quaisquer dois vértices (sem arestas paralelas). Para um grafo simples, o número de vizinhos de um vértice é igual à sua valência.
• Multigrafoé um grafo que permite múltiplas arestas ligando os mesmos vértices (arestas paralelas).
• Pseudografoé um grafo que contém arestas paralelas e laços.
• Grafo completoé o grafo simples em que, para cada vértice do grafo, existe uma aresta conectando este vértice a cada um dos demais. Ou seja, todos os vértices do grafo possuem mesmo grau. O grafo completo denvértices é frequentemente denotado porK_n.Ele temn(n-1)/2 arestas (correspondendo a todas as possíveis escolhas de pares de vértices).
• Grafo nuloé o grafo cujo conjunto de vértices évazio.
• Grafo vazioé o grafo cujo conjunto de arestas évazio.
• Grafo trivialé o grafo que possui apenas um vértice e nenhuma aresta.
• Grafo regularé um grafo em que todos os vértices tem o mesmo grau.
• Grafo conexoum grafo éconexose for possível estabelecer um caminho de qualquer vértice para qualquer outro vértice de um grafo. Se for sempre possível estabelecer um caminho de qualquer vértice para qualquer outro vértice mesmo depois de removerk-1 vértices, então diz-se que o grafo esták-conexo.Note que um grafo esták-conexo se, e somente se, contémkcaminhos independentes entre qualquer par de vértices. O grafo de exemplo acima é conexo (e portanto 1-conexo), mas não é 2-conexo. Em um grafo genéricoG,ocorteassociado a um conjuntoXde vértices é o conjunto de todas as arestas que têm uma ponta emXe outra emV(G) - X,ondeV(G)é o conjunto de todos os vértices pertencentes ao grafoG.
• Ponto de articulaçãoouVértice de corteé um vértice cuja remoção desliga um grafo. Umaponteé uma aresta cuja remoção desliga um grafo. Umcomponente biconectadoé um conjunto máximo de arestas tal que qualquer par de arestas do conjunto fazem parte de um ciclo simples comum. Ocontornode um grafo é o comprimento do ciclo simples mais curto no grafo. O contorno de um grafo acíclico é, por definição,infinito.
• Árvoreé um grafo simples acíclico e conexo. Às vezes, um vértice da árvore é distinto e chamado deraiz.As árvores são muito usadas comoestruturas de dadosem informática (vejaestrutura de dados em árvore).
• Florestaé um conjunto de árvores; equivalentemente a uma floresta, em algum grafo acíclico.
• Subgrafode um grafoGé um grafo cujo conjunto dos vértices é um subconjunto do conjunto de vérticesG,cujo conjunto de arestas é um subconjunto do conjunto de arestas deG,e cuja funçãowé uma restrição da função deG
• Subgrafo geradoré aquele obtido pela remoção de uma ou mais arestas de um outro grafo, dizemos então que este novo grafo obtido é gerador do primeiro,
• Subgrafo induzidoé obtido pela remoção de vértices e consequente das arestas relacionadas com ele de um outro grafo, dizemos que este novo grafo é um grafo induzido do original.
• Grafo parcialde um grafoGé um subgrafo com o mesmo conjunto de vértices queG.Umaárvore parcialé um grafo parcial que é árvore. Todo grafo tem pelo menos uma árvore parcial.
• Cliqueem um grafo é um subgrafo que também é um grafo completo. No grafo do exemplo acima, os vértices 1, 2 e 5 formam um clique.
• Conjunto independenteem um grafo é um conjunto de vértices não adjacentes entre si. No exemplo acima, os vértices 1, 3 e 6 formam um conjunto independente e 3, 5 e 6 são outro conjunto independente.
• Grafo planaré aquele que pode ser representado em um plano sem qualquer intersecção entre arestas. O grafo do exemplo é planar; o grafo completo denvértices, paran> 4, não é planar.
• Grafo bipartidoé o grafo cujos vértices podem ser divididos em dois conjuntos, nos quais não há arestas entre vértices de um mesmo conjunto. Para um grafo ser bipartido ele não pode conter circuitos de comprimento ímpar.
  1. Se um grafo G é bipartido, todo o circuito de G possui comprimento par.Sejam V1 e V2 os dois conjuntos em que, de acordo com a definição de grafo bipartido, se particiona V(G). Toda a aresta de G conecta um vértice em V1 com outro em V2. Assim sendo, se X for um vértice de V1, para “voltar” a esse vértice terá de se ir a V2 e voltar a V1 um número indeterminado de vezes, e de cada vez serão percorridas duas arestas, uma de um vértice em V1 para um vértice em V2 e outra de um vértice em V2 para um vértice em V1. Logo, o número de arestas a percorrer será par, ou seja, o comprimento do circuito é par.
  2. Se todo o circuito de um grafo G possui comprimento par, então o grafo é bipartido.Seja G um grafo em que todo o circuito tem comprimento par, e seja X um vértice de G. Denotemos por V1 o conjunto formado por X e por todos os vértices cuja distância a X é par. Seja V2 = V(G)\V1 (isto é, o conjunto formado pelos vértices de G que não pertencem a V1). Pretende mostrar-se que não existe qualquer aresta que conecte vértices de V1 ou vértices de V2. Suponhamos a existência de tal aresta, isto é, suponhamos a existência de dois vértices em V1 (ou V2), digamos Xi e Xj, conectados por uma aresta. Ora existe já um caminho de comprimento par entre Xi e Xj, já que existem caminhos, ambos de comprimento par (ou ímpar, no caso de Xi e Xj pertencerem a V2), entre Xi e X e entre X e Xj. Se a esse caminho juntarmos a aresta {Xi;Xj} obtemos um circuito de comprimento ímpar o que contraria a hipótese de apenas existirem circuitos de comprimento par.
• Grafo bipartido completoé o grafo bipartido, cujo qualquer vértice do primeiro conjunto é adjacente a todos vértices do segundo conjunto
• Grafo k-partidoougrafo dek-coloraçãoé um grafo cujos vértices podem ser particionados emkconjuntos disjuntos,nos quais não há arestas entre vértices de um mesmo conjunto. Um grafo 2-partido é o mesmo que grafo bipartido.
• Emparelhamento de grafosconsiste em partir o grafo em conjuntos de vértices a qual não compartilham nenhuma aresta entre eles.
• Teorema das quatro coresé baseado no problema das cores necessárias para se colorir um mapa sem que os países vizinhos compartilhem da mesma cor. Transformando o mapa em um grafo pode-se provar que pode-se representar qualquer mapa (um grafo planar) com apenas 4 cores (4 partições).

Buscas em Grafos

Percurso em grafos

• • É possível percorrer de modo sistemático todos os vértices e arestas do grafo. O grafo pode ser dirigido ou não.
  • O percurso em árvores é o processo de visitar cada nó da árvore exatamente uma vez.
  • O percurso pode ser interpretado como colocar todos os nós em uma linha, não existe uma ordem para ser seguida.
  • Existemnpercursos diferentes, quase todos caóticos.
  • Os básicos são percurso em profundidade e percurso em largura
  • Fila: busca em largura
  • Pilha: busca em profundidade
• Busca em extensão ou largura:(Breadth-First Search ou BFS). A propriedade especial está no fato de a árvore não possuir ciclos: dados dois vértices quaisquer, existe exatamente 1 caminho entre eles. Um percurso em extensão é visitar cada nó começando do menor nível e move-se para os níveis mais altos nível após nível, visitando cada nó da esquerda para a direita. Sua implementação é direta quando uma fila é utilizada. Depois que um nó é visitado, seus filhos, se houver algum, são colocados no final da fila e o nó no início da fila é visitado. Assim, os nós do nível n+1 serão visitados somente depois de ter visitados todos os nós do nível n. Computa a menor distância para todos os vértices alcançáveis. O sub-grafo contendo os caminhos percorridos é chamado de breadth-first tree.
• Busca em profundidade(Depth-first search ou DFS). Umalgoritmo de buscaem profundidade realiza uma busca não-informada que progride através da expansão do primeiro nó filho da árvore de busca, e se aprofunda cada vez mais, até que o alvo da busca seja encontrado ou até que ele se depare com um nó que não possui filhos (nó folha). Então a busca retrocede (backtrack) e começa no próximo nó. Numa implementação não-recursiva, todos os nós expandidos recentemente são adicionados a uma pilha, para realizar a exploração. A complexidade espacial de um algoritmo de busca em profundidade é muito menor que a de um algoritmo de busca em largura. A complexidade temporal de ambos algoritmos são proporcionais ao número de vértices somados ao número de arestas dos grafos aos quais eles atravessam. Quando ocorrem buscas em grafos muito grandes, que não podem ser armazenadas completamente na memória, a busca em profundidade não termina, em casos onde o comprimento de um caminho numa árvore de busca é infinito. O simples artifício de “lembrar quais nós já foram visitados” não funciona, porque pode não haver memória suficiente. Isso pode ser resolvido estabelecendo-se um limite de aumento na profundidade da árvore.

Problemas que envolvem grafos

• Coloração de grafos:
  • o Teorema das quatro cores
• Conjuntos de Grafos
  • Conjunto independente
  • Clique
• Problema do Caminho Mínimo
• Árvore de extensão mínima
• Problemas de roteamento:
  • Sete pontes de Königsberg
  • Problema da inspeção de rotas(também conhecido como o "Problema do carteiro chinês")
  • Problema do caixeiro viajante
• Fluxos de rede:
  • Problema de fluxo máximo

Algoritmos importantes

• algoritmo de Dijkstra
• algoritmo de Kruskal
• algoritmo do vizinho mais próximo
• algoritmo de Prim.

Generalizações

Numhipergrafouma aresta pode conectar mais que dois vértices.

Um grafo não-direcionado pode ser visto como umcomplexo simplicialconsistindo desímplicesde uma dimensão (as arestas) e símplices de dimensão zero (os vértices). Ou seja, complexos são generalizações de grafos que permitem símplices de maiores dimensões.

Ver também

• Estrutura de dadosárvore ordenada- DAGs, árvores binárias e outras formas especiais de grafos.
• Rede complexa
• Teoria espectral de grafos
• Redes de pequeno mundo
• Modelo de Watts e Strogatz

Ligações externas

• Uma Introdução Sucinta à Teoria dos Grafos
• «Graph theory tutorial»(em inglês)
• Fundamentos de identificação e sistematização dos grafos(pdf)
• «Graph theory Algorithms»(em inglês). — algoritmos em pseudocódigo
• «Algorithm Animations»(em inglês)
• «Graph Theory Software»(em inglês)
• «Lista de algoritmos de grafos»(em inglês). — com referências e links para bibliotecas de implementação de grafos

Ferramentas de grafos populares

• «Graph Visualization Software»(em inglês). — ferramenta para visualizar e interagir com diagramas de grafos
• «Visualization of Compiler Graphs»(em inglês)
• «Data Visualization Software»(em inglês)
• «Planarity Game»(em inglês). — jogo sobre Grafos Planares