Mostrar código-fonte de Teoria dos grafos

{{mais-notas|data=Agosto de 2013}}
{{Reciclagem|data=fevereiro de 2013}}
[[Imagem:Grafo k4 plano.PNG‎|thumb|Grafo com quatro vértices e 6 arestas. É um grafo completo, conexo e planar.]]

A '''teoria dos grafos''' ou '''de grafos''' é um ramo da [[matemática]] que estuda as relações entre os objetos de um determinado conjunto. Para tal são utilizadas estruturas chamadas de grafos, <math>G(V, E)</math>, onde <math>V</math> é um conjunto não vazio de objetos denominados [[Vértice (teoria dos grafos)|vértices]] (ou nós) e <math>E</math> (do [[língua inglesa|inglês]] ''edges'' - 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 um [[grafo orientado|''dígrafo'']] (grafo orientado). Um grafo com um único vértice e sem arestas é conhecido como '''grafo 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 da [[Wikipédia]] pode ser representada por um dígrafo: os vértices são os artigos da Wikipédia e existe uma aresta do artigo ''A'' para o artigo ''B'' [[se e somente se]] ''A'' contém um link para ''B''. Dígrafos são também usados para representar [[máquina de estado finito|máquinas de estado finito]]. O desenvolvimento de [[algoritmo]]s para manipular grafos é um tema importante da [[ciência da computação]].

== Histórico ==
[[Imagem:Konigsberg bridges.png|thumb|O problema das pontes de Königsberg]]
O artigo de [[Leonhard Euler]], publicado em 1736, sobre o problema das ''[[sete pontes de Königsberg]]'', é considerado o primeiro resultado da teoria dos grafos.<ref name="Biggs">{{Citation|autor=Biggs, N.; Lloyd, E. and Wilson, R.|titulo=Graph Theory, 1736-1936|publicado=Oxford University Press|ano=1986}}</ref><ref name= obm>{{citar web|url=https://www.obm.org.br/content/uploads/2017/01/Nivel1_grafos_bruno.pdf|título=Teoria dos Grafos|website=OBM|data=|acessodata=14 de junho de 2018|publicado=|ultimo=Holanda|primeiro=Bruno}}</ref> É também considerado um dos primeiros resultados topológicos na [[geometria]]; isto é, não dependente de quaisquer medidas. Isso ilustra a profunda conexão entre a teoria dos grafos e [[Topologia (matemática)|topologia]].

Mais de um século após a publicação do artigo de Euler sobre as pontes de [[Königsberg]] e enquanto [[Johann Benedict Listing|Listing]] introduzia o conceito de topologia, [[Arthur Cayley|Cayley]] foi levado por um interesse em formas analíticas particulares decorrentes do cálculo diferencial para estudar uma classe particular de grafos, as ''[[Árvore (grafo)|árvores]].''<ref>{{citation|primeiro=A.|último=Cayley|autorlink=Arthur Cayley|ano=1857|titulo=On the theory of the analytical forms called trees|periódico=[[Philosophical Magazine]]|series=Series IV|volume=13|número=85|páginas=172–176|doi=10.1017/CBO9780511703690.046}}</ref> Esse estudo teve diversas implicações na [[química]] teó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 por [[Dénes König]] e publicado em 1936.<ref>{{citation|último1=Tutte|primeiro1=W.T.|autorlink=William Thomas Tutte|titulo=Graph Theory|publicado=Cambridge University Press|ano=2001|isbn=978-0-521-79489-3|página=30|url=https://books.google.com/books?id=uTGhooU37h4C&pg=PA30|acessodata=2016-03-14}}</ref>

Um dos problemas mais conhecidos em teoria dos grafos é [[teorema das quatro cores|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 foi [[August Ferdinand Möbius]] em 1840. Em 1852, [[Francis Guthrie]] escreveu 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, [[Augustus De Morgan|DeMorgan]].<ref>{{Citar web|url=http://www.mathpages.com/home/kmath266/kmath266.htm|título=The Four Color Theorem|publicado=Mathpages.com|acessodata=3 de junho de 2016}}</ref>

== 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.

Um '''grafo direcionado''' (também chamado '''dígrafo''' ou '''[[quiver]]''') consiste de
* um [[conjunto]] ''V'' de ''vértices(não vazio)'',
* um [[conjunto]] ''E'' de ''arestas'' e
* [[função (matemática)|mapas]] ''s'', ''t'' : ''E'' → ''V'', onde ''s''(''e'') é a ''fonte'' e ''t''(''e'') é o ''alvo'' da aresta direcionada ''e''.

Um '''grafo não direcionado''' (ou simplesmente '''grafo''') é dado por
* um [[conjunto]] ''V'' de ''vértices(não vazio)'',
* um [[conjunto]] ''E'' de ''arestas'' e
* uma função ''w'' : ''E'' → [[conjunto das partes|P(''V'')]] que associa a cada aresta um subconjunto de dois ou de um elemento de ''V'', interpretado como os pontos terminais da aresta.

Em um grafo ou dígrafo '''com pesos''', uma função adicional E → '''R''' associa um valor a cada aresta, o que pode ser considerado seu "custo"; tais grafos surgem em [[Problema do caminho mínimo|problemas de rota ótima]] tais como o [[problema do caixeiro viajante]].

== Representação gráfica ==
[[Imagem:6n-graf.svg|thumb|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értices  ''V'' = {1, 2, 3, 4, 5, 6} e um conjunto de arestas  ''E'' = { {1,2}, {1,5}, {2,3}, {2,5}, {3,4}, {4,5}, {4,6} } (com o mapeamento ''w'' sendo a [[função inclusão|identidade]]).

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.<ref>{{citation|primeiro1=Giuseppe|último1=Di Battista|primeiro2=Peter|último2=Eades|primeiro3=Roberto|último3=Tamassia|primeiro4=Ioannis G.|último4=Tollis|ano=1994|titulo=Algorithms for Drawing Graphs: an Annotated Bibliography|periódico=Computational Geometry: Theory and Applications|volume=4|páginas=235–282|doi=10.1016/0925-7721(94)00014-x}}</ref><!--<ref>Ver {{citar web | url=http://www.aisee.com/gallery/graph23.htm | título=exemplo | publicado=www.aisee.com }}</ref>--> O que importa é quais vértices estão conectados entre si por quantas arestas.

O trabalho pioneiro de [[William Thomas Tutte]] foi de grande influência no desenho de grafos. Entre outras realizações, ele introduziu o uso de técnicas da [[álgebra linear]] para 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<ref>{{citation | último = Longabaugh | primeiro = William | doi = 10.1186/1471-2105-13-275 | periódico = BMC Bioinformatics | páginas = 275 | titulo = Combing the hairball with BioFabric: a new approach for visualization of large networks | url = http://www.biomedcentral.com/content/pdf/1471-2105-13-275.pdf | pmid = 23102059 | volume = 13 | ano = 2012}}</ref>; e visualizações da [[matriz de adjacência]] de 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 a [[lista de adjacência]] que 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.<ref>{{Citar livro|autor=Goodrich, Michael T.; Tamassia, Roberto|título=Estruturas de Dados e Algoritmos em Java|edição=2ª |local=Porto Alegre |editora=Bookman|ano=2001|página=502-503|isbn = 85-363-0043-4}}</ref><ref>{{Citar livro|autor=Goodrich, Michael T.; Tamassia, Roberto|título=Projeto de Algoritmos|subtítulo=Fundamentos, Análise e Exemplos da Internet |local=Porto Alegre|editora=Bookman|ano=2004|página=299-303|isbn = 85-363-0303-4}}</ref>

Estruturas do tipo matriz incluem a [[matriz de incidência]], uma matriz de 0's e 1's com suas linhas representando vértices e suas colunas as arestas e a [[matriz de adjacência]] onde 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 ditos '''incidentes''' à 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 considerados '''adjacentes''' se 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 de '''vizinhos''' de 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, ''n'' vértices) é geralmente representado por sua '''matriz de adjacência''': uma [[Matriz (matemática)|matriz]] ''n''-por-''n'' cujo valor na linha ''i'' e coluna ''j'' fornece o número de arestas do ''i''-ésimo ao ''j''-ésimo vértices.

=== Valência (Grau) ===
A '''valência''' (ou '''grau''') de um vértice é o número de arestas incidentes a ele. Se houver [[Laço (teoria dos grafos)|laç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. Se ''E'' é finito, então a valência total dos vértices é o dobro do número de arestas. Em um dígrafo, distingue-se o '''grau de saída''' (o número de arestas saindo de um vértice) e o '''grau 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ão]]''' diz 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 <math>G = (V, E)</math> um grafo não direcionado com <math>m</math> arestas. Então,
<math>2m = \sum_{v \in V} deg(v)</math>

=== Passeio ===
[[Imagem:Walk-trail-path.png|miniaturadaimagem|Grafo com cinco vértices e 9 arestas]]
Um passeio <math>p</math> entre dois vértices <math>A</math> e <math>B</math>, definido como <math>p(A,B)</math>, é uma lista alternada de vértices e arestas
<math> p(A,B) = v_0, e_1, v_1, e_2, v_2, ..., e_k, v_k </math> tal que
* <math>A = v_0</math> e <math>B = v_k</math>
* existe no mínimo uma aresta
* para <math>1 \le i \le k </math> a aresta <math>e_i</math> incide sobre <math>v_{i-1}</math> e <math>v_i</math>

O tamanho de um passeio, definido por <math> \left\vert p  \right\vert </math> corresponde ao número de arestas que possui, incluindo as repetições<ref name="dbwest" />. Na figura ao lado, um passeio do vértice <math>a</math> até o vértice <math>d</math> possível é a lista <math>p(a,d) = a, e_9, c, e_2, b, e_1, a, e_9, c, e_8, d</math> de tamanho <math>5</math>. Note que a aresta <math>e_9</math> 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.<ref name="dbwest" />

=== Caminho ===
'''[[Caminho (teoria dos grafos)|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 é chamado '''simples''' se nenhum dos vértices no caminho se repete. O '''comprimento do caminho''' é o número de arestas que o caminho usa, contando-se arestas múltiplas vezes. O '''custo de um caminho''' num grafo balanceado é a soma dos custos das arestas atravessadas. Dois caminhos são '''independentes''' se 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 euleriano]]''' em um grafo é o caminho que usa cada '''aresta''' exatamente uma vez. Se tal caminho existir, o grafo é chamado ''traversável''. Um '''ciclo euleriano''' é um ciclo que usa cada aresta exatamente uma vez.
* '''[[Caminho hamiltoniano]]''' em um grafo é o caminho que visita cada '''vértice''' exatamente uma vez. Um '''ciclo 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 (teoria dos grafos)|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. Um '''ciclo 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-se '''acíclico''' se não contém ciclos simples.

'''[[Laço (teoria dos grafos)|Laço]]''' (''loop'') num grafo ou num dígrafo é uma aresta ''e'' em ''E'' cujas 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 de ''n'' vértices é frequentemente denotado por ''K<sub>n</sub>''. Ele tem ''n''(''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 é [[conjunto vazio|vazio]].
* '''[[Grafo vazio]]''' é o grafo cujo conjunto de arestas é [[conjunto vazio|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 conexo]]''' um grafo é ''conexo'' se 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 remover ''k''-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ém ''k'' caminhos 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érico ''G'', o '''corte''' associado a um conjunto ''X'' de vértices é o conjunto de todas as arestas que têm uma ponta em ''X'' e outra em ''V(G) - X'', onde ''V(G)'' é o conjunto de todos os vértices pertencentes ao grafo ''G''.
* '''[[Vértice de corte (teoria dos grafos)|Ponto de articulação]]''' ou '''Vértice de corte''' é um vértice cuja remoção desliga um grafo. Uma '''[[ponte (teoria dos grafos)|ponte]]''' é uma aresta cuja remoção desliga um grafo. Um '''componente biconectado''' é um conjunto máximo de arestas tal que qualquer par de arestas do conjunto fazem parte de um ciclo simples comum. O '''[[contorno]]''' de um grafo é o comprimento do ciclo simples mais curto no grafo. O contorno de um grafo acíclico é, por definição, [[infinito]].
* '''[[Árvore (teoria dos grafos)|Árvore]]''' é um grafo simples acíclico e conexo.  Às vezes, um vértice da árvore é distinto e chamado de ''raiz''. As árvores são muito usadas como [[estrutura de dados|estruturas de dados]] em informática (veja [[Árvore (estrutura de dados)|estrutura de dados em árvore]]).
* '''[[Floresta (teoria dos grafos)|Floresta]]''' é um conjunto de árvores; equivalentemente a uma floresta, em algum grafo acíclico.
* '''[[Subgrafo]]''' de um grafo ''G'' é um grafo cujo conjunto dos vértices é um subconjunto do conjunto de vértices ''G'', cujo conjunto de arestas é um subconjunto do conjunto de arestas de ''G'', e cuja função ''w'' é uma restrição da função de ''G''
* '''[[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 parcial]]''' de um grafo ''G'' é um subgrafo com o mesmo conjunto de vértices que ''G''. Uma '''árvore parcial''' é um grafo parcial que é árvore. Todo grafo tem pelo menos uma árvore parcial.
* '''[[Clique]]''' em 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 independente]]''' em 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 de ''n'' vértices, para ''n''> 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.
*# '''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.
*# '''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-partido]]''' ou '''grafo de ''k''-coloração''' é um grafo cujos vértices podem ser particionados em ''k'' [[conjuntos disjuntos]], nos quais não há arestas entre vértices de um mesmo conjunto. Um grafo 2-partido é o mesmo que grafo bipartido.
* '''[[Acoplamento (teoria dos grafos)|Emparelhamento de grafos]]''' consiste 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.
** Existem ''n'' percursos 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 largura|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). Um [[algoritmo de busca]] em 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]]:
** [[Teorema das quatro cores|o Teorema das quatro cores]]
* Conjuntos de Grafos
** [[Conjunto independente]]
** [[Clique]]
* [[Problema do caminho mínimo|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:
** [[Algoritmo de Ford-Fulkerson|Problema de fluxo máximo]]

== Algoritmos importantes ==
* [[algoritmo de Dijkstra]]
* [[algoritmo de Kruskal]]
* [[algoritmo do vizinho mais próximo]]
* [[algoritmo de Prim]].

== Generalizações ==
Num [[hipergrafo]] uma aresta pode conectar mais que dois vértices.

Um grafo não-direcionado pode ser visto como um [[complexo simplicial]] consistindo de [[símplice]]s de 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.

{{Referências|refs =
<ref name="dbwest">{{citar livro|primeiro=Douglas Brent|ultimo=West|ano=2001|titulo=Introduction to Graph Theory|edicao=2nd|local=USA|editora=Prentice Hall|pagina= 20|capitulo=Chapter 1 - Fundamental Concepts|isbn=0-13-014400-2}}</ref>
}}

== 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 ==
{{Commonscat|Graph theory}}
* [http://www.ime.usp.br/~pf/teoriadosgrafos/texto/TeoriaDosGrafos.pdf Uma Introdução Sucinta à Teoria dos Grafos]
* {{link|en|2=http://www.utm.edu/departments/math/graph/|3=Graph theory tutorial}}
* [http://www.graphs.ee/Fundamentals.pdf Fundamentos de identificação e sistematização dos grafos] (pdf)
* {{link|en|2=http://students.ceid.upatras.gr/~papagel/project/contents.htm|3=Graph theory Algorithms |4=— algoritmos em pseudocódigo}}
* {{link|en|2=http://www2.hig.no/~algmet/animate.html|3=Algorithm Animations}}
* {{link|en|2=http://graphtheorysoftware.com/|3=Graph Theory Software}}
* {{link|en|2=http://martinbroadhurst.com/Graph-algorithms.html|3=Lista de algoritmos de grafos |4=— com referências e links para bibliotecas de implementação de grafos}}

=== Ferramentas de grafos populares ===
* {{link|en|2=http://www.graphviz.org/ |3=Graph Visualization Software |4=— ferramenta para visualizar e interagir com diagramas de grafos}}
* {{link|en|2=http://www.rw.cdl.uni-saarland.de/users/sander/html/gsvcg1.html|3=Visualization of Compiler Graphs}}
* {{link|en|2=http://www.tulip-software.org|3=Data Visualization Software}}
* {{link|en|2=http://planarity.net|3=Planarity Game |4=— jogo sobre Grafos Planares}}

{{Matemática industrial e aplicada}}
{{Áreas da matemática}}
{{Categorização AD e AB de outras wikis}}

[[Categoria:Teoria dos grafos| ]]
[[Categoria:Pesquisa operacional]]