Teoria dos grafos

Teoria dos grafos
Um grafo simples com seis vértices e sete arestas reduz relações a uma estrutura que pode ser percorrida e analisada
Informações gerais
Área	Matemática discreta
Objeto de estudo	Grafos
Trabalho fundador	Solutio Problematis ad Geometriam Situs Pertinentis, de Leonhard Euler, publicado em 1736

Na matemática e na ciência da computação, a teoria dos grafos estuda os grafos, estruturas matemáticas que organizam redes de objetos e as relações entre eles. Cada objeto vira um vértice, também chamado de nó ou ponto, e cada relação vira uma aresta, também chamada de arco, ligação ou linha. Em um grafo não orientado, a ligação vale igualmente nos dois sentidos. Em um grafo orientado, ela segue uma direção determinada. Essa forma simples de organizar relações faz dos grafos um dos objetos da matemática discreta.

Com esse modelo, é possível perguntar se há um caminho entre dois pontos, qual caminho custa menos, onde há ciclos, como formar pares ou atribuir cores sem conflito, quanto pode passar por uma rede, quais subestruturas ela contém e quantos grafos cumprem certa condição. A escolha do que vira vértice, aresta, direção ou peso define a pergunta matemática. Algumas respostas dependem da forma da rede, outras de matrizes, da geometria, da probabilidade ou de algoritmos, e problemas parecidos à primeira vista podem exigir recursos computacionais muito diferentes.

O estudo começou a tomar forma em 1736, quando Leonhard Euler resolveu o problema das sete pontes de Königsberg ao deixar de lado distâncias e formatos e examinar apenas as conexões. A mesma ideia ganhou usos em redes de comunicação e transporte, química, física, biologia, linguística, ciências sociais, gestão de projetos e aprendizado de máquina.

Definição e conceitos fundamentais

Ver artigo principal: Grafo (matemática)

Elementos, tipos e notação

Um grafo é formado por vértices ligados por arestas. O termo pode designar:

• um grafo não orientado, no alto à esquerda, em oposição ao grafo orientado, cujas arestas têm setas, no alto à direita. Arestas orientadas e não orientadas podem coexistir em um grafo misto, embaixo à esquerda
• um grafo simples, em oposição ao multigrafo, embaixo à direita

A teoria dos grafos pertence à matemática discreta e costuma fazer parte da combinatória, mas suas perguntas e seus métodos formaram um campo próprio. O termo "grafo" entrou nesse vocabulário em 1878, quando James Joseph Sylvester publicou na revista Nature uma analogia entre os "invariantes quânticos" e "covariantes" da álgebra e os diagramas moleculares.

Embora as definições variem, um grafo reúne vértices, também chamados de nós ou pontos, e arestas, também chamadas de arcos, ligações ou linhas. Os dois vértices tocados por uma aresta são suas extremidades. Em um grafo não orientado, a aresta não aponta para nenhum lado. No grafo orientado, cada aresta recebe uma direção, chamada orientação, que costuma ser desenhada com uma seta. Um grafo misto aceita arestas dos dois tipos. Um grafo simples não tem duas arestas com o mesmo par de extremidades nem laços, que saem de um vértice e voltam a ele. O multigrafo admite essas possibilidades. Quando cada aresta recebe um número chamado peso, a estrutura é um grafo ponderado.

Para escrever essa ideia em linguagem matemática, um grafo simples não orientado pode ser indicado por $G=(V,E)$. A letra $V$ designa o conjunto de vértices, e $E\subseteq \{\{x,y\}:x,y\in V,\ x\neq y\}$ designa um conjunto de pares não ordenados de vértices distintos. A ordem do grafo é $|V|$, e seu tamanho é $|E|$. O grau, também chamado de valência, de um vértice conta quantas extremidades de arestas chegam a ele. Cada laço conta duas vezes.

Quando dois vértices são extremidades da mesma aresta, eles são adjacentes, e a aresta é incidente nos dois. A vizinhança de um vértice reúne seus vértices adjacentes. Essas relações locais determinam propriedades do grafo inteiro e podem ser guardadas em listas ou matrizes.

Ao somar os graus de todos os vértices, cada aresta entra duas vezes na conta, uma em cada extremidade. O lema do aperto de mãos escreve essa relação como $\sum _{v\in V}\deg(v)=2|E|$ para todo grafo finito não orientado. O número de vértices de grau ímpar é, por esse motivo, sempre par.

Percursos e conectividade

Ver artigos principais: Caminho (teoria dos grafos) e Conectividade (teoria dos grafos)

Um percurso torna a conectividade verificável. As arestas coloridas formam um caminho entre dois vértices do grafo.

Um passeio é uma sequência alternada de vértices e arestas, na qual cada aresta une os vértices que vêm imediatamente antes e depois dela. Uma trilha é um passeio que não repete arestas. Um caminho não repete vértices. Se o primeiro e o último vértices coincidem, o passeio é fechado. Um caminho fechado que não repete os demais vértices forma um ciclo. O comprimento de um passeio, trilha ou caminho é o número de arestas percorridas.

Um grafo não orientado é conexo quando existe um caminho entre cada par de vértices. Caso contrário, ele se divide em componentes conexas, que são seus subgrafos conexos maximais. Nos grafos orientados, distingue-se a conectividade forte, na qual há caminhos orientados nos dois sentidos entre cada par de vértices, da conectividade fraca, obtida quando as orientações das arestas são desconsideradas.

Distâncias, parâmetros e invariantes

O diâmetro é a maior distância mínima entre dois vértices. No mesmo grafo, caminhos mínimos diferentes podem atingir esse valor.

A distância $d(u,v)$ entre dois vértices da mesma componente de um grafo não orientado é o comprimento do menor caminho que os une. Em um grafo conexo, a maior distância de um vértice a qualquer outro é sua excentricidade. O menor valor de excentricidade do grafo é seu raio, e o maior é seu diâmetro. Os vértices de excentricidade mínima formam o centro do grafo. Outra medida baseada em percursos é a cintura, o comprimento do ciclo mais curto, quando existe.

Uma propriedade ou quantidade que não muda quando o grafo é trocado por outro isomorfo recebe o nome de invariante de grafos. A ordem, o tamanho, a sequência de graus, o número de componentes, a planaridade e o fato de ser bipartido são exemplos. Os parâmetros numéricos também abrangem o número cromático, o número de clique, o número de independência, a conectividade por vértices ou arestas e a largura de árvore. Cada um resume uma parte da estrutura e pode dar limites para outros parâmetros ou controlar a dificuldade de algoritmos. Alguns valores iguais, porém, não bastam para concluir que dois grafos são isomorfos.

Árvores e florestas

Ver artigo principal: Árvore (grafo)

Uma árvore pode ter forma de caminho, estrela ou estrutura ramificada e ainda conectar os vértices sem formar ciclos.

Uma árvore é um grafo conexo sem ciclos, enquanto uma floresta é um grafo sem ciclos cujas componentes são árvores. Em um grafo finito, ser uma árvore equivale a haver exatamente um caminho entre cada par de vértices. Também equivale a ser conexo e ter $n-1$ arestas, ou a ser conexo e tornar-se desconexo quando qualquer aresta é removida. Esses critérios reconhecem a mesma estrutura por propriedades diferentes.

Todo grafo conexo contém uma árvore geradora, uma árvore que passa por todos os seus vértices. Se as arestas têm pesos, uma árvore geradora mínima escolhe a menor soma possível. O estudo das árvores reúne os conceitos de caminho e conectividade com problemas de otimização, decomposição e estruturas de dados.

Classes elementares e generalizações

Em um hipergrafo, uma única hiperaresta pode reunir mais de dois vértices e guardar uma relação que ocorre em grupo.

Um grafo completo contém uma aresta entre cada par de vértices distintos. Em um grafo bipartido, os vértices podem ser separados em dois conjuntos e todas as arestas têm uma extremidade em cada conjunto. Um grafo regular tem o mesmo grau em todos os vértices.

A maior parte dos problemas algorítmicos usa grafos finitos. Há também grafos infinitos, para os quais conectividade, caminhos, árvores e menores são adaptados a conjuntos infinitos de vértices ou arestas. Quando uma relação precisa reunir mais de dois vértices de uma só vez, o hipergrafo permite que uma aresta incida em qualquer quantidade deles.

Subgrafos, isomorfismo e operações

A contração funde as duas extremidades de uma aresta e é uma das operações usadas para obter menores de um grafo.

Um subgrafo nasce da escolha de parte dos vértices e das arestas de um grafo, sem mudar quais arestas tocam quais vértices. Um subgrafo gerador contém todos os vértices do grafo original. O subgrafo induzido por um conjunto de vértices contém todas as arestas do original cujas duas extremidades pertencem a esse conjunto. Dois grafos são isomorfos quando há uma correspondência bijetiva entre seus vértices que mantém as adjacências. Os rótulos, as posições e as formas do desenho podem mudar sem alterar o grafo abstrato.

Para produzir novas estruturas e comparar problemas, pode-se eliminar um vértice ou uma aresta, ou fazer uma contração de aresta, que funde as duas extremidades em um único vértice. O grafo obtido por eliminações e contrações é um menor, também chamado de subcontração, do original. O grafo complementar conserva os vértices e põe arestas onde não havia adjacência. O grafo linha transforma as arestas do original em vértices e une aquelas que tinham uma extremidade comum.

História

Origens e século XIX

No mapa de Königsberg de 1651, o Pregel está em azul e as sete pontes, em verde. O problema levou Euler a substituir a geografia detalhada por relações de conexão, passo fundador da teoria dos grafos e da topologia.

Em 1736, Leonhard Euler publicou Solutio Problematis ad Geometriam Situs Pertinentis, sobre as sete pontes de Königsberg, e iniciou o estudo matemático das estruturas definidas por conexões. Seu texto e Remarques sur les Problèmes de Situation, escrito em 1771 por Alexandre-Théophile Vandermonde a respeito do passeio do cavalo, seguiram a chamada analysis situs. Gottfried Wilhelm Leibniz havia iniciado essa linha de investigação. A característica de Euler relaciona o número de arestas, vértices e faces de um poliedro convexo. Augustin-Louis Cauchy e Simon Antoine Jean L'Huillier estudaram e generalizaram essa relação. Trabalhos desse tipo abriram o ramo da matemática que recebeu o nome de topologia.

Mais de um século após o artigo de Euler, Johann Benedict Listing introduzia o conceito de topologia e Arthur Cayley, interessado em formas analíticas do cálculo diferencial, começou a estudar as árvores. Cayley concentrou suas técnicas na enumeração de grafos com propriedades determinadas e também relacionou as árvores à composição química. A teoria enumerativa dos grafos cresceu a partir desses resultados, dos trabalhos de George Pólya publicados entre 1935 e 1937 e da generalização feita por Nicolaas Govert de Bruijn em 1959. A aproximação com a química teórica também trouxe termos que entraram no vocabulário da teoria dos grafos.

O desenvolvimento independente da topologia, entre 1860 e 1930, levou suas ideias de volta à teoria dos grafos nos trabalhos de Camille Jordan, Kazimierz Kuratowski e Hassler Whitney, enquanto técnicas da álgebra moderna aproximaram os dois campos. Um exemplo anterior veio do físico Gustav Kirchhoff, que publicou em 1845 suas leis de Kirchhoff para calcular a tensão elétrica e a corrente elétrica em circuitos elétricos.

Consolidação da disciplina

Colorir mapas como grafos transforma regiões em vértices e fronteiras comuns em adjacências. Dessa tradução veio o teorema das quatro cores.

Dénes König escreveu o primeiro livro didático de teoria dos grafos, publicado em 1936. Em 1969, um livro de Frank Harary tornou-se manual de referência internacional e deu a matemáticos, químicos, engenheiros eletricistas e cientistas sociais uma linguagem comum. Harary destinou todos os direitos autorais ao financiamento do Prêmio George Pólya.

O problema das quatro cores pergunta se qualquer mapa desenhado em um plano pode ter suas regiões coloridas com quatro cores, sem que duas regiões de fronteira comum recebam a mesma cor. Francis Guthrie formulou a questão em 1852, e o primeiro registro escrito está em uma carta enviada naquele ano por Augustus De Morgan a William Rowan Hamilton. Proliferaram provas incorretas, inclusive as propostas por Cayley e Alfred Kempe. As investigações e generalizações de Peter Tait, Percy John Heawood, Frank P. Ramsey e Hugo Hadwiger levaram ao estudo da coloração de grafos imersos em superfícies de gênero arbitrário. A reformulação de Tait abriu uma classe de questões chamada de problemas de fatoração, estudada sobretudo por Julius Petersen e Dénes König. Os trabalhos de Ramsey sobre coloração e os resultados obtidos por Pál Turán em 1941 abriram a teoria extremal dos grafos.

Desenvolvimento computacional e contemporâneo

A animação do algoritmo de Dijkstra mostra a construção passo a passo de caminhos mínimos, para além da prova de que eles existem.

Os métodos probabilísticos entraram na teoria dos grafos por meio de estudos como os de Paul Erdős e Alfréd Rényi sobre a probabilidade assintótica de um grafo ser conexo. Dessa linha nasceu a teoria dos grafos aleatórios.

Na segunda metade do século XX, a computação tornou-se instrumento e objeto de estudo da teoria dos grafos. Em 1959, Edsger Dijkstra publicou algoritmos para encontrar caminhos mínimos e árvores geradoras mínimas. Nas décadas seguintes, a análise de algoritmos e a complexidade computacional passaram a separar problemas tratáveis em tempo polinomial de problemas NP-completos.

O problema das quatro cores permaneceu sem solução por mais de um século. Em 1969, Heinrich Heesch publicou um método para resolvê-lo com computadores. A prova assistida por computador que Kenneth Appel e Wolfgang Haken produziram em 1976 empregou o método de descarga desenvolvido por Heesch. O procedimento começou com um conjunto inevitável de 1.936 configurações, reduzido depois a 1.476 para a verificação computacional. O computador era indispensável e essa parte não podia ser conferida integralmente à mão, o que provocou debate. Duas décadas depois, Neil Robertson, Paul Seymour, Daniel P. Sanders e Robin Thomas apresentaram uma prova mais simples, baseada em 633 configurações.

O conjunto de artigos Graph Minors, iniciado por Robertson e Seymour em 1983, levou à prova de que, em qualquer conjunto infinito de grafos finitos, algum deles é menor de outro. Toda classe de grafos fechada pela operação de menores pode, a partir desse resultado, ser caracterizada por um conjunto finito de menores proibidos.

No fim da década de 1990, os modelos de redes de pequeno mundo e de redes em crescimento por ligação preferencial deram novo impulso à ciência de redes, que estuda a estrutura e a dinâmica de redes encontradas em sistemas naturais, tecnológicos e sociais.

Representações de grafos

Como um grafo é uma abstração de relações, a mesma estrutura pode receber representações diferentes. Um desenho comunica visualmente, matrizes permitem usar métodos algébricos e estruturas de dados guardam o grafo para que um computador possa processá-lo.

Representação visual: desenho de grafos

Ver artigo principal: Desenho de grafos

Desenhos diferentes podem mostrar o mesmo grafo. A correspondência entre vértices, não a posição na página, decide o isomorfismo.

Um grafo costuma ser desenhado com um ponto ou círculo para cada vértice e uma linha para cada aresta que une dois vértices. Nos grafos orientados, uma seta dá a direção. Nos grafos ponderados, o peso fica junto à aresta.

O desenho não deve ser confundido com o próprio grafo, uma estrutura abstrata e não visual, pois o mesmo grafo admite desenhos diferentes. O que importa é saber quais vértices estão unidos e por quantas arestas, não a posição exata de cada elemento. Na prática, nem sempre é fácil decidir se dois desenhos correspondem ao mesmo grafo. Certas disposições são mais legíveis em alguns domínios do que em outros.

W. T. Tutte introduziu procedimentos da álgebra linear para obter desenhos de grafos e, com eles, ampliou os métodos disponíveis para essa tarefa.

O desenho de grafos, uma área da visualização da informação, procura tornar a estrutura legível. Em diagramas de nós e ligações, os vértices podem ser discos, caixas ou rótulos, enquanto as arestas podem ser segmentos de reta, linhas poligonais ou curvas. A qualidade pode ser medida pelo número de cruzamentos, pela área, pela exibição de simetrias, pela minimização de curvas, pela resolução angular e pelo número de inclinações. Um grafo planar admite um desenho sem cruzamentos. O campo também estuda desenhos em outras superfícies, empacotamentos de círculos, grafos de interseção e visualizações da matriz de adjacência.

Representações algébricas

Ver também: Teoria algébrica dos grafos e Teoria espectral de grafos

Na matriz de adjacência, as linhas e colunas correspondem aos vértices, e cada entrada guarda uma ligação mostrada no desenho.

As matrizes levam as relações do grafo para a linguagem da álgebra linear. Na matriz de incidência, as linhas correspondem aos vértices e as colunas, às arestas. Na matriz de adjacência, linhas e colunas correspondem aos vértices. Em um grafo simples, a entrada $(i,j)$ informa se $i$ e $j$ são adjacentes. Quando $A$ é essa matriz, a entrada $(i,j)$ de $A^{k}$ conta os passeios de comprimento $k$ que vão de $i$ a $j$.

A matriz de grau reúne os graus dos vértices e, ao ser combinada com a matriz de adjacência, dá a matriz laplaciana. Esta é usada em resultados como o teorema de Kirchhoff, que conta as árvores geradoras de um grafo. Na matriz de distâncias, cada entrada contém o comprimento do caminho mínimo entre dois vértices.

Estruturas de dados

Ver artigo principal: Grafo (tipo abstrato de dados)

Uma lista de adjacência guarda apenas os vizinhos que existem para cada vértice, o que costuma economizar memória em grafos esparsos.

Em aplicações computacionais, a estrutura de dados escolhida depende da estrutura do grafo e do algoritmo usado para manipulá-lo. Entre as representações por listas estão a lista de arestas, um arranjo de pares de vértices, e a lista de adjacência, que enumera separadamente os vizinhos de cada vértice. A matriz de adjacência também pode ser usada diretamente como estrutura de dados.

As listas tendem a ocupar menos memória e costumam ser escolhidas para grafos esparsos, comuns em aplicações reais. As matrizes dão acesso rápido em certas tarefas, mas podem consumir muita memória. Uma aplicação pode combinar as duas formas. Matrizes esparsas eficientes para arquiteturas paralelas ainda são desenvolvidas e permitem escrever algoritmos de grafos como operações de álgebra linear.

Modelagem e métodos de análise

Construção do modelo

Para modelar uma situação por um grafo, é preciso decidir quais entidades serão vértices e quais relações serão arestas. A pergunta orienta a escolha. Em uma rede viária, os vértices podem ser cruzamentos e as arestas, trechos de rua. Em outra escala, os vértices podem ser cidades e as arestas, ligações diretas entre elas. Uma relação recíproca aceita arestas não orientadas, enquanto uma relação assimétrica exige orientação. Distância, tempo, capacidade ou custo podem entrar como pesos.

O modelo conserva as relações necessárias para a pergunta e deixa outros aspectos do sistema de fora. Dois modelos do mesmo objeto podem, por isso, responder a perguntas distintas, e a conclusão matemática só vale dentro das escolhas feitas. Também é preciso decidir se laços e arestas paralelas têm sentido, se o sistema muda com o tempo e se cada relação ocorre realmente entre pares. Essas decisões dizem se um grafo simples basta ou se o problema pede uma generalização.

Da pergunta ao problema matemático

Depois de construído o modelo, a pergunta original é traduzida em uma propriedade, estrutura ou quantidade do grafo. A formulação determina o resultado procurado e os métodos disponíveis.

Pergunta no sistema modelado	Formulação típica em grafos	Resultado procurado
É possível ir de uma entidade a outra?	Caminhos e conectividade	Uma resposta de decisão ou um caminho que a certifique
Qual é a rota de menor custo?	Caminho mínimo em grafo ponderado	Um caminho que minimize a soma dos pesos
Como conectar todos os pontos com custo total mínimo?	Árvore geradora mínima	Uma árvore geradora que minimize a soma dos pesos
Como formar pares ou atribuir tarefas sem conflitos?	Emparelhamento	Um conjunto de arestas sem extremidades em comum
Como separar atividades incompatíveis?	Coloração	Uma atribuição de cores que respeite as adjacências
Quanto pode ser transportado por uma rede com capacidades?	Fluxo máximo e corte mínimo	O valor máximo do fluxo e um corte que forneça o limite correspondente

Transformações, equivalências e dualidades

No grafo complementar, cada não adjacência do original vira uma aresta. Uma clique, por exemplo, vira um conjunto independente.

Uma transformação pode expor a equivalência entre dois problemas. Uma clique de um grafo vira um conjunto independente em seu complemento. Colorir as arestas de um grafo equivale a colorir os vértices de seu grafo linha. Em um grafo plano conexo, a dualidade relaciona ciclos do original a cortes do dual. Essas correspondências levam definições, teoremas e algoritmos de uma formulação para outra.

Métodos de prova e análise

Entre as técnicas combinatórias usadas para provar resultados sobre grafos, a dupla contagem calcula a mesma coleção de duas maneiras, como ocorre no lema do aperto de mãos. A indução costuma remover um vértice ou uma aresta, aplicar a hipótese ao grafo menor e reconstruir a solução. Um argumento extremal escolhe um objeto máximo ou mínimo e prova que qualquer violação permitiria melhorá-lo. A prova clássica da existência de árvores geradoras, por exemplo, começa com um subgrafo gerador conexo que tem o menor número possível de arestas.

Os métodos algébricos transformam o grafo em matrizes, polinômios ou grupos, enquanto o método probabilístico prova que uma estrutura existe ao mostrar que ela ocorre com probabilidade positiva, mesmo sem construí-la diretamente. As decomposições estruturais separam o grafo em partes mais simples. Os métodos algorítmicos acrescentam a construção efetiva e calculam quanto tempo e quanta memória ela exige. Uma prova de existência, por si só, não dá um algoritmo eficiente.

Problemas fundamentais

Depois que o modelo está definido, um problema pode pedir que se decida se uma estrutura existe, que se construa um caminho ou emparelhamento, que se encontre o melhor valor possível ou que se contem configurações. A dificuldade da mesma pergunta pode mudar conforme a classe do grafo, os pesos, a orientação das arestas e os parâmetros escolhidos.

Caminhos, ciclos e conectividade

Ao transformar cidades em vértices e distâncias em pesos, uma rota geográfica torna-se um problema de caminhos em um grafo ponderado.

Problemas de percursos perguntam se determinados vértices podem ser ligados e quais restrições devem ser impostas ao trajeto. Problemas de conectividade procuram determinar quantos vértices ou arestas precisam ser retirados para desconectar o grafo, ou quantos caminhos independentes existem entre dois pontos. O teorema de Menger relaciona o número máximo de caminhos internamente disjuntos ao tamanho mínimo de um conjunto separador.

• Problema do caminho hamiltoniano
• Árvore geradora mínima
• Problema da inspeção de rotas, também chamado de problema do carteiro chinês
• Sete pontes de Königsberg
• Problema do caminho mínimo
• Árvore de Steiner
• Problema do caixeiro-viajante, que é NP-difícil

A existência de um caminho ou circuito euleriano pode ser decidida pelos graus e pela conectividade, e o percurso pode ser construído em tempo linear no tamanho do grafo. Decidir se existe um caminho ou circuito hamiltoniano, embora a pergunta pareça semelhante, é NP-completo.

Emparelhamentos, coberturas e empacotamentos

As arestas destacadas não compartilham extremidades e formam um emparelhamento. A pergunta passa de uma regra local para a busca do maior conjunto possível.

Um emparelhamento reúne arestas sem extremidades em comum. Conforme a pergunta, busca-se um emparelhamento máximo, com o maior número possível de arestas, ou um emparelhamento perfeito, que cubra todos os vértices. O teorema do casamento de Hall dá as condições para que um emparelhamento cubra uma das partes de um grafo bipartido. O mesmo raciocínio pode ser usado para atribuir pessoas, tarefas e recursos.

Em grafos, os problemas de cobertura podem designar formas do problema da cobertura de conjuntos aplicadas a subconjuntos de vértices ou subgrafos.

• O problema do conjunto dominante é o caso em que os conjuntos são as vizinhanças fechadas.
• O problema da cobertura de vértices é o caso em que os elementos cobertos são as arestas.
• O problema original da cobertura de conjuntos, também chamado de conjunto de interseção, pode ser formulado como uma cobertura de vértices em um hipergrafo.

Problemas de empacotamento procuram selecionar subestruturas mutuamente disjuntas, como caminhos, ciclos ou árvores. Emparelhamentos são o caso em que as subestruturas escolhidas são arestas.

Coloração de grafos

Ver artigo principal: Coloração de grafos

Uma coloração válida separa por cores os vértices que não podem compartilhar a mesma escolha, convertendo conflitos em uma restrição visual.

Muitos problemas e teoremas procuram colorir um grafo de modo que dois vértices adjacentes não recebam a mesma cor ou impondo restrições semelhantes. Também é possível colorir arestas, por exemplo impedindo que duas arestas incidentes tenham a mesma cor. A área reúne estes resultados e conjecturas.

• o teorema das quatro cores
• o teorema forte do grafo perfeito
• a conjectura de Erdős–Faber–Lovász, provada para todo $n$ suficientemente grande em um artigo publicado em 2023
• a conjectura da coloração total, também chamada de conjectura de Behzad, ainda sem solução
• a conjectura da coloração de arestas por listas, ainda sem solução no caso geral
• a conjectura de Hadwiger, ainda sem solução no caso geral

Fluxos, cortes e circulação

O maior fluxo possível da fonte ao sorvedouro tem o mesmo valor que o menor gargalo capaz de separá-los.

Uma rede de fluxo é um grafo orientado cujas arestas têm capacidades, com uma fonte, um sorvedouro e conservação do fluxo nos demais vértices. O teorema do fluxo máximo e corte mínimo afirma que o maior valor enviado da fonte ao sorvedouro é igual à menor capacidade de um corte que os separa. O resultado está na base de algoritmos de transporte, comunicação, circulação e alocação de recursos. Diferentes redes de fluxo levam aos problemas listados abaixo.

• o teorema do fluxo máximo e corte mínimo
• o problema do fluxo de custo mínimo
• fluxos com mais de uma fonte ou mais de um sorvedouro

Subestruturas, isomorfismo e menores

Subdividir arestas acrescenta vértices de grau dois sem mudar a forma topológica do grafo. A mesma estrutura pode, então, ser reconhecida em escalas diferentes.

O problema do isomorfismo de subgrafos pergunta se um grafo ocorre como subgrafo de outro. Quando o padrão também faz parte da entrada, a versão de decisão é NP-completa. A pergunta também entra no estudo de propriedades de grafos hereditárias para subgrafos. Se um grafo tem uma propriedade desse tipo, todos os seus subgrafos também a têm. Nos problemas de otimização, um subgrafo maximal não aceita nenhum acréscimo sem perder a propriedade, enquanto um subgrafo máximo tem o maior tamanho possível. Encontrar uma clique máxima é NP-difícil. A versão de decisão correspondente, o problema do clique, é NP-completa.

O problema do isomorfismo de grafos é o caso particular que pergunta se dois grafos são isomorfos. Não se sabe se ele é NP-completo nem se pode ser resolvido em tempo polinomial. Desde 2016, conhece-se um algoritmo geral de tempo quase polinomial, com limite superior da forma $\exp((\log n)^{O(1)})$.

A busca por subgrafos induzidos levanta um problema próximo, pois algumas propriedades também passam para essas partes do grafo. Encontrar um subgrafo induzido máximo com determinada propriedade pode ser NP-difícil, embora uma solução apenas maximal por inclusão possa ser mais simples. Procurar o maior subgrafo induzido sem arestas equivale a procurar o maior conjunto independente. A versão de decisão desse problema é NP-completa.

No problema da contenção de menores, procura-se um grafo fixo entre os menores de outro grafo. Muitas propriedades passam para os menores. O teorema de Wagner dá um exemplo dessa relação.

• um grafo é planar se, e somente se, não contém como menor o grafo bipartido completo $K_{3,3}$, relacionado ao problema das três casas, nem o grafo completo $K_{5}$

No problema da contenção de subdivisões, procura-se um grafo fixo como subdivisão de outro. Uma subdivisão, ou homeomorfismo, surge quando novos vértices são inseridos em algumas arestas. A planaridade pode ser testada por esse tipo de contenção, como afirma o teorema de Kuratowski.

• um grafo é planar se, e somente se, não contém como subdivisão o grafo bipartido completo $K_{3,3}$ nem o grafo completo $K_{5}$

O teorema de Kelmans–Seymour, formulado primeiro como conjectura, foi provado em um conjunto de artigos concluído em 2020.

• todo grafo 5-conexo por vértices que não seja planar contém uma subdivisão do grafo completo $K_{5}$

Alguns problemas perguntam até que ponto um grafo pode ser recuperado a partir dos subgrafos obtidos quando se elimina um vértice. A conjectura da reconstrução segue em aberto. Buscas computacionais confirmaram sua validade para todos os grafos com até 13 vértices e para algumas classes limitadas de grafos maiores.

Decomposições e parâmetros estruturais

Uma decomposição organiza uma estrutura densa como uma árvore de partes. A largura das separações pode, então, controlar propriedades e algoritmos.

A decomposição divide o conjunto de arestas de um grafo em partes, cada qual acompanhada dos vértices necessários. Muitas perguntas buscam decompor um grafo em subgrafos isomorfos a um grafo fixo, como na decomposição de um grafo completo em ciclos hamiltonianos. Outras determinam uma família de grafos para receber a decomposição, como uma família de ciclos. A conjectura de empacotamento de árvores de Gyárfás, por exemplo, pede que $n-1$ árvores especificadas, com respectivamente 1, 2, 3, ..., $n-1$ arestas, sejam empacotadas sem sobreposição de arestas no grafo completo $K_{n}$.

Os problemas estudados abrangem os itens abaixo.

• a arboricidade, decomposição no menor número possível de florestas
• a cobertura dupla por ciclos, coleção de ciclos que cobre cada aresta exatamente duas vezes
• a coloração de arestas, decomposição no menor número possível de emparelhamentos
• a fatoração de grafos, decomposição de um grafo regular em subgrafos regulares com graus determinados
• a decomposição em árvore e a largura de árvore, que medem quanto a estrutura de um grafo se aproxima de uma árvore. Muitos problemas difíceis em grafos gerais admitem algoritmos eficientes de programação dinâmica quando a largura de árvore é limitada

Enumeração

A enumeração a menos de isomorfismo conta cada estrutura uma só vez, mesmo quando rótulos ou desenhos diferentes levam ao mesmo grafo.

A enumeração de grafos conta os grafos que satisfazem condições determinadas. Os grafos rotulados têm vértices com identidades fixadas. Os não rotulados são contados a menos de isomorfismo. Harary e Palmer reúnem uma parte ampla desses problemas.

Problemas geométricos e de visibilidade

O grafo de visibilidade converte a geometria dos obstáculos em adjacências, permitindo estudar cobertura e rotas por métodos combinatórios.

Na geometria computacional, grafos de visibilidade registram quais pontos ou regiões podem ser ligados por segmentos que não atravessam obstáculos. Entre os problemas associados estão o problema da galeria de arte, que procura posicionar observadores para cobrir uma região poligonal, e questões de reconhecimento e caracterização de grafos de visibilidade.

Subáreas

As subáreas da teoria dos grafos se sobrepõem, pois um mesmo problema pode exigir estrutura combinatória, simetria algébrica, representação geométrica, probabilidade e algoritmos. Cada divisão dá mais atenção a certo tipo de pergunta e às ferramentas usadas para respondê-la.

Teoria estrutural dos grafos

Ver artigo principal: Teoria estrutural dos grafos

Uma decomposição em árvore organiza sobreposições locais sem formar ciclos. Sua largura mede quanto o grafo se afasta do comportamento de uma árvore.

A teoria estrutural dos grafos investiga como as propriedades do grafo inteiro nascem de suas subestruturas e das maneiras de separá-lo em partes mais simples. Ela estuda conectividade, caminhos disjuntos, subgrafos e menores proibidos, decomposições em árvore e relações entre classes de grafos.

A ausência de certas subestruturas define muitas classes, e o teorema de Robertson–Seymour garante que toda classe de grafos finitos fechada pela operação de menores é determinada por um conjunto finito de menores proibidos. Os parâmetros estruturais também podem antecipar a dificuldade de um problema. A largura de árvore mede quanto um grafo se aproxima de uma árvore, e muitos problemas difíceis em grafos gerais admitem algoritmos eficientes quando esse parâmetro é limitado.

O estudo estrutural procura ainda enumerar os membros de uma classe, caracterizá-la por subestruturas proibidas, determinar relações de inclusão entre classes, reconhecer seus membros por algoritmos eficientes e encontrar representações adequadas para eles.

Teoria topológica dos grafos

Ver artigo principal: Teoria topológica dos grafos

A teoria topológica relaciona a estrutura do grafo ao espaço em que ele é desenhado. O conjunto reúne a imersão do grafo de Heawood em um toro, uma imersão em livro de uma página do grafo diamante, o número de cruzamentos de $K_{4,7}$, com 18 cruzamentos em vermelho, e a coloração dos Estados Unidos pelo teorema das quatro cores, sem contar lagos e oceanos.

A teoria topológica dos grafos estuda grafos como espaços topológicos. Um grafo simples pode ser construído geometricamente com simplexos de dimensão zero para os vértices e de dimensão um para as arestas. Juntos, eles formam um complexo simplicial unidimensional. Essa subárea abrange a imersão de grafos em superfícies, a imersão sem enlace, os menores de grafos, o número de cruzamentos, a coloração de mapas e o grafo de tensão.

Na imersão de um grafo em uma superfície, pontos são associados aos vértices e arcos simples, às arestas. As extremidades de cada arco correspondem aos vértices terminais da aresta. Nenhum arco contém um ponto associado a outro vértice e dois arcos nunca se cruzam em um ponto interior a qualquer um deles. O conceito pode ser generalizado pela imersão sem enlace, na qual dois ciclos do grafo não formam um enlace no espaço euclidiano tridimensional, e pela imersão em livro, feita em uma coleção de semiplanos que têm a mesma reta como fronteira.

Para obter o grafo dual de uma imersão no plano, coloca-se um vértice em cada face e, para cada aresta do grafo original, traça-se uma aresta dual que separa as mesmas duas faces. Em grafos planos conexos, essa dualidade troca ciclos por cortes e permite transportar resultados entre problemas de coloração, conectividade e fluxo.

Um grafo é menor de outro quando pode ser formado pela eliminação de vértices e arestas e pela contração de arestas. Um dos primeiros resultados da teoria dos menores é o teorema de Wagner, pelo qual um grafo finito é planar se, e somente se, não contém como menor o grafo completo de cinco vértices $K_{5}$ nem o grafo utilitário. O teorema de Robertson–Seymour garante que toda classe de grafos finitos fechada pela operação de menores pode ser caracterizada por um conjunto finito de menores proibidos.

O número de cruzamentos é a quantidade mínima de interseções entre arestas em um desenho do grafo. Esse estudo nasceu de uma pergunta feita por Pál Turán, que buscava uma planta industrial com o menor número possível de cruzamentos entre as linhas que ligavam fornos de tijolos a depósitos. O problema da fábrica de tijolos de Turán pode ser formulado como a busca do número de cruzamentos de um grafo bipartido completo.

A coloração de mapas pode ser formulada como uma coloração de grafos. Cada região vira um vértice, e uma aresta une as regiões que compartilham uma fronteira. O teorema das quatro cores afirma que quatro cores bastam para colorir as regiões de qualquer mapa sem que duas regiões com uma fronteira comum tenham a mesma cor. O resultado é mais forte que o teorema das cinco cores. O problema Terra–Lua, ainda em aberto, estende o problema da coloração de mapas planares resolvido pelo teorema das quatro cores.

Um grafo de tensão é um grafo orientado cujas arestas recebem rótulos invertíveis formados por elementos de um grupo. A estrutura especifica de modo compacto o grafo derivado. Ela também é usada para formar um grafo de cobertura.

Teoria algébrica dos grafos

Ver artigo principal: Teoria algébrica dos grafos

Ver também: Teoria espectral de grafos

A teoria algébrica dos grafos usa a teoria dos grupos para estudar simetrias. O grafo de Petersen, por exemplo, é vértice-transitivo, simétrico, distância-transitivo e distância-regular. Seu grupo de automorfismos tem 120 elementos e é o grupo simétrico $S_{5}$.

A teoria algébrica dos grafos usa métodos da álgebra, sobretudo a álgebra linear e a teoria dos grupos. A teoria espectral de grafos trabalha com a matriz de adjacência e com seu espectro, formado pelo polinômio característico e pelos autovalores e autovetores da matriz. O campo também estuda a matriz laplaciana, definida a partir da matriz de grau, uma matriz diagonal que reúne os graus dos vértices, e da matriz de adjacência.

Na teoria dos grupos, os grupos de automorfismos e a teoria geométrica dos grupos permitem classificar famílias de grafos por suas simetrias. Entre elas estão os grafos simétricos, vértice-transitivos, aresta-transitivos, distância-transitivos, distância-regulares e fortemente regulares. O teorema de Frucht afirma que todo grupo finito é o grupo de simetrias de algum grafo finito não orientado. Em uma forma mais forte, há infinitos grafos simples, conexos e não isomorfos cujos grupos de automorfismos são isomorfos a cada grupo finito.

A teoria algébrica também trata de invariantes algébricos, do polinômio cromático, do polinômio de Tutte e dos invariantes de nós. O polinômio cromático conta as colorações de um grafo em função do número de cores. O polinômio de Tutte tem duas variáveis e codifica propriedades da conectividade do grafo.

Teoria geométrica dos grafos

Ver artigo principal: Teoria geométrica dos grafos

A teoria geométrica estuda propriedades combinatórias e geométricas de grafos desenhados com arestas retas ou curvas. O conjunto reúne uma árvore geradora mínima euclidiana, o grafo dodecaédrico de um dodecaedro regular, um grafo moeda obtido por empacotamento de círculos e o grafo de Heawood como grafo de Levi do plano de Fano.

A teoria geométrica dos grafos estuda as propriedades combinatórias e geométricas de grafos desenhados no espaço euclidiano, com arestas em segmentos de reta ou curvas contínuas. Inserida na geometria discreta e na geometria computacional, abrange os grafos planares, sua relação com politopos convexos de dimensões superiores, a interseção entre conjuntos de formas geométricas e campos como a geometria de incidência e a geometria projetiva.

Um grafo planar desenhado no plano euclidiano com vértices pontuais e segmentos de reta sem cruzamentos como arestas chama-se grafo planar de linhas retas. Pelo teorema de Fáry, todo grafo planar admite esse desenho. Trata-se de um caso particular de grafo euclidiano, no qual o comprimento de cada aresta é a distância euclidiana entre suas extremidades. Nessa área, a árvore geradora mínima euclidiana minimiza o comprimento total dos segmentos entre pontos finitos de um espaço euclidiano. O problema de Hadwiger–Nelson procura o menor número de cores para colorir o plano sem dar a mesma cor a dois pontos separados por distância unitária. O problema do caminho mínimo busca um caminho cuja soma dos valores das arestas seja a menor possível.

No grafo de visibilidade, os vértices correspondem a pontos e as arestas, a conexões visíveis. Em um polígono simples, sem auto-interseções nem buracos, as arestas do grafo de visibilidade correspondem aos lados e às diagonais do polígono. Um grafo poliédrico é um grafo não orientado formado pelos vértices e arestas de um poliedro convexo tridimensional. Pelo teorema de Steinitz, ele deve ser planar e 3-conexo por vértices, isto é, permanecer conexo após a remoção de quaisquer dois vértices.

Em um grafo de interseção, cada vértice corresponde a um conjunto, e dois vértices são unidos quando os conjuntos têm interseção não vazia. O menor número de elementos necessários para construir dessa forma um grafo de conjuntos finitos chama-se número de interseção. Quando os conjuntos são objetos geométricos, o grafo resultante também pode ser geométrico. A interseção de segmentos em uma dimensão forma um grafo de intervalos, e a de discos unitários no plano forma um grafo de discos unitários. O grafo de interseção de um empacotamento de círculos é um grafo moeda, no qual os vértices correspondem aos círculos e as arestas, aos pares de círculos tangentes. Pelo teorema de Koebe–Andreev–Thurston, os grafos de tangência de empacotamentos de círculos com interiores disjuntos são exatamente os grafos planares finitos. O teorema de Scheinerman afirma que todo grafo planar é o grafo de interseção de algum conjunto de segmentos de reta no plano.

O grafo de Levi é um grafo bipartido associado a uma estrutura de incidência e a uma configuração projetiva.

Teoria extremal dos grafos

Ver artigo principal: Teoria extremal dos grafos

A teoria extremal dos grafos procura o maior número possível de arestas de um grafo, chamado de número extremal. O ponto de partida foi o teorema de Mantel, que determina o número extremal de um grafo sem triângulos, como o da imagem, em $\lfloor n^{2}/4\rfloor$.

A teoria extremal dos grafos, parte da combinatória extremal, procura o maior número possível de arestas que um grafo pode ter sob certas condições. Esse valor recebe o nome de número extremal. O teorema de Mantel determina o número extremal de um grafo sem triângulos e abriu essa linha de investigação. O teorema de Turán estendeu o resultado a qualquer grafo não orientado que não contenha um subgrafo completo de tamanho fixado. O teorema de Erdős–Stone generaliza o teorema de Turán e também recebe o nome de "teorema fundamental da teoria extremal dos grafos".

A área também abrange o problema do subgrafo proibido, a densidade de homomorfismos e o lema de regularidade de Szemerédi. No problema do subgrafo proibido, procura-se o número extremal de um grafo com $n$ vértices que não contenha um subgrafo isomorfo a um grafo dado. A densidade de homomorfismos é um parâmetro do homomorfismo de grafos e pode expressar a probabilidade de que uma função escolhida uniformemente ao acaso entre os vértices de dois grafos seja um homomorfismo. Isso ocorre quando a função leva vértices adjacentes do primeiro grafo a vértices adjacentes do segundo. O lema de regularidade de Szemerédi afirma que um grafo pode ser dividido em um número limitado de partes, de modo que as arestas entre elas sejam $\varepsilon$-regulares.

A teoria dos limites de grafos leva essas ideias a sequências de grafos cada vez maiores. Em grafos densos, as densidades de homomorfismos podem convergir para um objeto-limite dado por uma função simétrica mensurável, chamada de graphon. Com esse recurso, a combinatória extremal encontra os grafos aleatórios, a amostragem de grandes redes e os testes de propriedades.

Teoria dos grafos aleatórios

Ver artigo principal: Grafo aleatório

A teoria dos grafos aleatórios estuda grafos por meio do método probabilístico. O campo foi iniciado pelos matemáticos húngaros Paul Erdős e Alfréd Rényi, cujo procedimento produz grafos aleatórios no chamado modelo de Erdős–Rényi.

No modelo $G(n,p)$, começa-se com $n$ vértices. Cada par distinto recebe uma aresta, de modo independente, com probabilidade $p$. Mudar $p$ produz fenômenos de limiar. Considere $p=c/n$, com $c$ constante e $n$ crescendo sem limite. Se $c<1$, as componentes têm tamanho sublinear com probabilidade que tende a 1. Se $c>1$, surge com a mesma garantia assintótica uma componente conexa com número de vértices proporcional a $n$, chamada de componente gigante. Essas transições de fase aproximam os grafos aleatórios da teoria da percolação e da física estatística.

Sobre o mesmo grafo, pesos sorteados ao acaso fazem da árvore geradora mínima uma variável aleatória que preserva todos os vértices.

Árvores aleatórias

Uma árvore aleatória é uma árvore, um grafo não orientado no qual cada par de vértices está unido por exatamente um caminho, formada por um processo estocástico regido por probabilidades. A lista abaixo reúne seus tipos e estruturas relacionadas.

• a árvore geradora uniforme, uma árvore geradora de um grafo em que todas as árvores possíveis têm a mesma probabilidade de ser escolhidas. Ela contém todos os vértices do grafo e pode ser produzida por uma caminhada aleatória com apagamento de laços, na qual os ciclos criados durante uma caminhada aleatória são eliminados
• o processo de ramificação, modelo populacional em que cada indivíduo tem um número aleatório de descendentes
• a árvore browniana, estrutura fractal formada por processos de agregação limitada por difusão
• a árvore binária aleatória, uma árvore binária escolhida ao acaso por alguma distribuição de probabilidade A expressão abrange árvores formadas por ordens aleatórias de inserção e árvores uniformemente distribuídas com um número determinado de nós
• a árvore geradora mínima aleatória, formada pela atribuição de pesos aleatórios às arestas de um grafo e pela escolha da árvore geradora mínima correspondente
• a árvore recursiva aleatória, uma árvore com rótulos crescentes que pode ser produzida por uma regra estocástica simples de crescimento

Enumeração de grafos

Ver artigo principal: Enumeração de grafos

A enumeração de grafos conta estruturas com propriedades prescritas e distingue os grafos rotulados, cujos vértices têm identidades fixadas, dos grafos não rotulados, contados a menos de isomorfismo. A fórmula de Cayley afirma que existem $n^{n-2}$ árvores rotuladas com $n$ vértices. Esse também é o número de árvores geradoras do grafo completo $K_{n}$.

Teoria algorítmica dos grafos

Ver artigo principal: Algoritmo em grafos

A busca em largura expande o grafo em camadas de distância crescente, convertendo a conectividade em uma ordem sistemática de visita.

A teoria algorítmica dos grafos estuda procedimentos para reconhecer propriedades de grafos e construir objetos como caminhos mínimos, árvores geradoras, emparelhamentos, colorações e fluxos. Entre suas ferramentas básicas estão a busca em largura e a busca em profundidade, que percorrem sistematicamente os vértices e as arestas de um grafo.

Além da correção dos algoritmos, a área compara tempo de execução, memória e complexidade computacional. Alguns problemas admitem algoritmos polinomiais, enquanto outros são NP-completos em grafos gerais, mas se tornam tratáveis em classes restritas ou quando certos parâmetros são limitados. Para redes de grande porte, também se empregam algoritmos de aproximação, aleatorizados, parametrizados, paralelos e distribuídos.

Um problema algorítmico pode pedir uma decisão, a construção de um objeto, a otimização de uma quantidade ou a enumeração de soluções. A estrutura e a forma de guardar o grafo mudam o algoritmo disponível. Decomposições estruturais, por exemplo, permitem usar programação dinâmica quando a largura de árvore é limitada.

Aplicações

Durante um mês de 2013, edições linguísticas da Wikipédia foram usadas como vértices e os editores que trabalharam em versões diferentes, como arestas. O grafo torna visíveis relações que uma lista de edições isoladas não mostraria.

Relações e processos de sistemas físicos, biológicos, sociais e de informação podem ser formulados como grafos. Quando o grafo recebe dados de um sistema real sobre entidades, ligações ou processos, costuma ser chamado de rede.

Ciência de redes

Ver artigo principal: Ciência das redes

A ciência de redes estuda como redes de sistemas naturais, tecnológicos e sociais se formam, se organizam e mudam. Para isso, reúne teoria dos grafos, probabilidade, estatística, sistemas dinâmicos e conhecimentos do sistema observado. A teoria dos grafos pode investigar uma estrutura abstrata. A ciência de redes também pergunta como uma rede empírica surgiu, como se modifica e de que maneira sua organização altera os processos que ocorrem nela.

Uma rede real pode ter mais de um tipo de ligação, conter camadas ou reunir interações com mais de duas entidades. As redes multicamadas separam relações ou sistemas interdependentes. Hipergrafos e complexos simpliciais guardam interações de ordem superior. Essas extensões evitam a perda de informação que ocorreria se todo o sistema fosse reduzido a uma única rede de relações aos pares.

Ciência da computação

Na ciência da computação, os grafos organizam redes de comunicação, dados, dispositivos computacionais, projetos de circuitos integrados e fluxos de execução, com ligações causais ou não causais. Em um site, por exemplo, as páginas podem ser vértices de um grafo orientado, e as hiperligações formam arestas que apontam de uma página para outra. A computação também desenvolve algoritmos para tratar grafos. Os sistemas de reescrita manipulam grafos em memória por meio de regras e formalizam suas transformações. Já os bancos de dados de grafos guardam e consultam dados estruturados como grafos de modo persistente e seguro para transações.

Nos grafos orientados usados em máquinas de estados finitos, fluxogramas, redes de Petri e cadeias de Markov, os vértices são estados, tarefas ou eventos, e as arestas são transições ou dependências.

Aprendizado de máquina e estruturas aleatorizadas

Em uma rede neural de grafos, cada vértice agrega informações dos vizinhos. As camadas seguintes aumentam a parte do grafo que pode alterar seu estado numérico.

No aprendizado de máquina, as redes neurais de grafos aprendem com dados estruturados em rede. Muitas delas atualizam o vetor de características de cada vértice ao agregar informações de seus vizinhos. O método é usado em moléculas, sistemas de recomendação e grafos de conhecimento.

Outras estruturas em forma de árvore usam escolhas aleatórias para tarefas computacionais específicas. A floresta aleatória combina árvores de decisão construídas com escolhas ao acaso. A árvore de exploração rápida cresce por amostragem para buscar caminhos em espaços de muitas dimensões. A treap combina propriedades de uma árvore de busca e de um heap por meio de prioridades aleatórias.

Segurança de redes e detecção de ataques cibernéticos

Ao converter registros de comunicação em vértices, arestas e atributos, padrões como hubs, agrupamentos e rotas tornam-se sinais mensuráveis para a análise de tráfego.

A detecção de ataques baseada em grafos aplica a teoria dos grafos à identificação de ataques contra redes de computadores, em especial ataques distribuídos de negação de serviço, chamados de DDoS, e outras formas de intrusão.

Nesses sistemas, dados de tráfego, como registros de fluxo IP, formam um grafo. Os nós correspondem a entidades da rede, como endereços de origem e destino ou portas, e as arestas são os fluxos de comunicação observados. Contagens de pacotes, volume de bytes e duração do fluxo ficam guardados como atributos dos nós ou das arestas.

Medidas estatísticas aplicadas à estrutura do grafo permitem detectar ataques, e uma delas é a entropia não extensiva baseada na formulação de Tsallis, sensível às mudanças na distribuição dos fluxos que acompanham o tráfego malicioso. A análise dos grafos de fluxo também permite localizar uso indevido de recursos, gargalos de tráfego e violações de políticas.

Linguística

Na análise de dependências, palavras tornam-se vértices e relações sintáticas tornam-se arestas orientadas, expondo a estrutura que organiza uma frase.

Na linguística, as estruturas discretas da linguagem natural podem ser estudadas por grafos. A sintaxe e a semântica composicional costumam usar árvores, cuja capacidade expressiva vem do princípio da composicionalidade aplicado a um grafo hierárquico. Abordagens como a gramática sintagmática nuclear modelam a sintaxe com estruturas de características tipadas, que são grafos acíclicos orientados.

Na semântica lexical, sobretudo em aplicações computacionais, o sentido de uma palavra pode ser modelado por suas relações com outras palavras. As redes semânticas são usadas na linguística computacional. A língua também pode ser analisada como grafo na fonologia, como ocorre na teoria da otimidade, que emprega reticulados, e na morfologia de estados finitos, que usa transdutores de estados finitos. A série de oficinas TextGraphs, da Association for Computational Linguistics, dedica-se a métodos baseados em grafos. WordNet e VerbNet organizam léxicos em rede.

Estruturas de características e unificação

As teorias de modelagem de restrições tratam de famílias de grafos orientados ordenadas por uma ordem parcial. Nessas aplicações, as estruturas de características guardam informação parcial em atributos e valores e podem ser ordenadas por especificidade. A unificação combina duas estruturas compatíveis no grafo mais geral que conserva as informações de cada uma. Quando não há conflito, ela se torna uma operação fundamental em gramáticas baseadas em restrições.

Em sistemas compatíveis com o princípio da composicionalidade, a unificação fornece uma operação para combinar e satisfazer restrições. Ela é usada na prova automática de teoremas e na modelagem da análise sintática em linguística computacional.

Física, química e engenharia

Em um diagrama de Feynman, o grafo organiza vértices de interação e linhas de propagação. As regras físicas dão sentido e valores a essa estrutura.

Na química e na física, a teoria dos grafos é usada para estudar moléculas. A física da matéria condensada pode analisar quantitativamente estruturas atômicas tridimensionais simuladas a partir de propriedades topológicas dos átomos. Os diagramas e regras de cálculo de Feynman organizam os termos de expansões perturbativas da teoria quântica de campos, associando fatores matemáticos a vértices de interação e linhas de propagação para calcular amplitudes de processos físicos. Na química, um grafo pode modelar uma molécula, com vértices para os átomos e arestas para as ligações químicas. Esse método é empregado no processamento computacional de estruturas moleculares, desde editores químicos até buscas em bancos de dados.

Na física estatística, grafos podem guardar as ligações locais entre partes interagentes de um sistema e a dinâmica de processos físicos. Na modelagem de redes elétricas, pesos atribuídos às arestas expressam a resistência dos segmentos de fio e permitem calcular propriedades da rede. Grafos também modelam canais microscópicos de meios porosos, com vértices para os poros e arestas para os canais menores que os ligam. A teoria química dos grafos usa o grafo molecular para modelar moléculas.

Ao retirar nós ou arestas, uma rede pode passar por uma transição de fase e se dividir em pequenos aglomerados. A teoria da percolação analisa o limiar dessa ruptura.

Ciências sociais

No sociograma de Jacob L. Moreno, de 1953, pessoas são vértices e escolhas são arestas. O desenho deixa visíveis posições centrais, grupos e assimetrias nas relações sociais.

Na sociologia, a teoria dos grafos permite medir, por exemplo, o prestígio de atores por relações de trabalho ou estudar a propagação de rumores em redes sociais, sobretudo com programas de análise de redes sociais. Nos grafos de conhecimento e amizade, uma aresta une duas pessoas que se conhecem. Os grafos de persuasão modelam a possibilidade de uma pessoa afetar o comportamento de outra. Nos grafos de colaboração, uma aresta une duas pessoas que trabalham juntas de alguma maneira, como na atuação em um mesmo filme.

A sociometria e a teoria dos grafos ganharam uma formulação matemática conjunta no fim da década de 1940. Alex Bavelas propôs um modelo para estruturas de grupos e relacionou a posição dos participantes em redes de comunicação ao desempenho de tarefas. As medidas de centralidade entraram, a partir desses estudos, na análise de redes sociais.

Biologia, medicina e ecologia

Em uma árvore filogenética, as ramificações expressam hipóteses de ancestralidade. A proximidade no desenho acompanha a descendência. A semelhança visual, sozinha, não determina essa proximidade.

Na biologia e na conservação, um vértice pode corresponder a uma região habitada por uma espécie, e as arestas, às rotas de migração ou deslocamento entre regiões. O modelo permite examinar padrões reprodutivos, acompanhar a propagação de doenças e parasitas e avaliar como mudanças de deslocamento afetam outras espécies.

Na biologia molecular e na genômica, métodos baseados em grafos organizam conjuntos de dados com muitas relações. Na análise de transcriptomas de células individuais, por exemplo, eles agrupam células em tipos celulares. Genes e proteínas também podem formar vias biológicas em grafos, como vias metabólicas e redes de regulação genética. Árvores evolutivas, redes ecológicas e agrupamentos hierárquicos de padrões de expressão genética também assumem a forma de grafos.

A teoria dos grafos ainda é empregada na conectômica e na neurociência computacional. Em um grafo do sistema nervoso, os nós podem ser neurônios ou regiões cerebrais, e as arestas podem ser conexões estruturais ou funcionais. Esses grafos permitem comparar padrões de conectividade presentes em condições neurológicas.

Transportes e gestão de projetos

Vértices, arestas, direções e pesos podem organizar rotas de transporte ou precedências de um projeto. O sistema modelado dá sentido a cada elemento.

Em uma rede viária, os pesos das arestas podem expressar o comprimento de cada estrada, o tempo de viagem, o consumo de energia ou o custo monetário. Esses grafos são usados na programação de aparelhos de GPS, no planejamento de rotas e em mecanismos de busca de viagens que comparam duração e preço de voos.

Na gestão de projetos, o PERT e o método do caminho crítico organizam atividades e relações de precedência em redes orientadas, em geral acíclicas. Dadas as estimativas de duração e as relações de precedência adotadas, o caminho crítico determina a duração mínima do projeto e aponta as atividades cuja demora adia a conclusão, enquanto os demais caminhos podem ter alguma folga.

Ver também

• Lista de termos técnicos relacionados à teoria dos grafos, glossário dos conceitos usados na área
• Teoria das redes complexas, estudo de redes com estrutura e dinâmica não triviais
• Modelo de Watts e Strogatz, modelo de rede de pequeno mundo
• Teoria algébrica dos grafos, estudo de grafos por meio de estruturas e métodos algébricos
• Teorema das quatro cores, problema de coloração que motivou parte do desenvolvimento do campo
• Sete pontes de Königsberg, problema resolvido por Euler no trabalho que deu início à teoria dos grafos
• Grafo de Petersen, grafo pequeno usado como exemplo e contraexemplo em muitos problemas
• Problema do caixeiro-viajante, problema de otimização formulado sobre rotas em um grafo
• Árvore de extensão mínima, subgrafo que conecta todos os vértices com peso total mínimo

Bibliografia

• Seidel, Raimund; Aragon, Cecilia R. (1996). «Randomized Search Trees». Algorithmica. 16 (4–5): 464–497. doi:10.1007/BF01940876 
• Bavelas, Alex (1948). «A Mathematical Model for Group Structures». Human Organization. 7 (3): 16–30. doi:10.17730/humo.7.3.f4033344851gl053 
• Bavelas, Alex (1950). «Communication Patterns in Task-Oriented Groups». The Journal of the Acoustical Society of America. 22 (6): 725–730. doi:10.1121/1.1906679 
• Barabási, Albert-László; Albert, Réka (1999). «Emergence of Scaling in Random Networks». Science. 286 (5439): 509–512. PMID 10521342. doi:10.1126/science.286.5439.509 
• Lowell W. Beineke; Bjarne Toft; Robin J. Wilson (2025). Milestones in Graph Theory: A Century of Progress. Col: Spectrum. 108. [S.l.]: AMS/MAA. ISBN 978-1-4704-6431-8 
• Beineke, Lowell W.; Wilson, Robin J. (2009). Topics in Topological Graph Theory. [S.l.]: Cambridge University Press. ISBN 978-1-139-64368-9 
• Bender, Edward A.; Williamson, S. Gill (2010). Lists, Decisions and Graphs. With an Introduction to Probability. [S.l.: s.n.] 
• Berge, Claude (1958). Théorie des graphes et ses applications. Paris: Dunod  Edição inglesa, Wiley, 1961, Methuen & Co, Nova Iorque, 1962. Edições russa, Moscou, 1961, espanhola, México, 1962, romena, Bucareste, 1969, e chinesa, Xangai, 1963. Reimpressão da primeira edição inglesa de 1962, Dover, Nova Iorque, 2001.
• Biggs, Norman (1993). Algebraic Graph Theory 2 ed. [S.l.]: Cambridge University Press 
• Biggs, N.; Lloyd, E.; Wilson, R. (1986). Graph Theory, 1736–1936. [S.l.]: Oxford University Press 
• Bodlaender, Hans L. (1996). «A Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth». SIAM Journal on Computing. 25 (6): 1305–1317. doi:10.1137/S0097539793251219 
• Bollobás, Béla (2013). Modern Graph Theory. [S.l.]: Springer. ISBN 978-1-4612-0619-4 
• Bollobás, Béla; Riordan, O. M. (2003). S. Bornholdt; H. G. Schuster, eds. Mathematical results on scale-free random graphs in "Handbook of Graphs and Networks" 1 ed. Weinheim: Wiley VCH 
• Bollobás, B. (2001). Random Graphs 2 ed. [S.l.]: Cambridge University Press. ISBN 0-521-79722-5 
• Bondy, J. A.; Murty, U. S. R. (2008). Graph Theory. [S.l.]: Springer. ISBN 978-1-84628-969-9 
• Borgs, Christian; Chayes, Jennifer T.; Lovász, László; Sós, Vera T.; Vesztergombi, Katalin (2008). «Convergent sequences of dense graphs. I. Subgraph frequencies, metric properties and testing». Advances in Mathematics. 219 (6): 1801–1851. arXiv:math/0702004. doi:10.1016/j.aim.2008.07.008 
• Bounceur, Ahcene; Bezoui, Madani; Euler, Reinhardt (2019). Boundaries and Hulls of Euclidean Graphs: From Theory to Practice. [S.l.]: CRC Press. ISBN 978-1-351-69028-7 
• Breiman, Leo (2001). «Random Forests». Machine Learning. 45 (1): 5–32. doi:10.1023/A:1010933404324 
• Bretto, Alain; Faisant, Alain; Hennecart, François (2022). Elements of Graph Theory: From Basic Concepts to Modern Developments. [S.l.]: EMS Press. ISBN 978-3-98547-017-4. doi:10.4171/ETB/24 
• Brightwell, Graham R.; Scheinerman, Edward R. (1993). «Representations of planar graphs». SIAM Journal on Discrete Mathematics. 6 (2): 214–229. doi:10.1137/0406017 
• Bronstein, Michael M.; Bruna, Joan; Cohen, Taco; Veličković, Petar (2021). «Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges». arXiv. arXiv:2104.13478 
• Cauchy, A. L. (1813). «Recherche sur les polyèdres, premier mémoire». Journal de l'École Polytechnique. 9, caderno 16: 66–86 
• Cayley, Arthur (1857). «On the Theory of the Analytical Forms Called Trees». The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science. 4. 13 (85): 172–176. doi:10.1080/14786445708642275 
• Cayley, A. (1875). «Ueber die Analytischen Figuren, welche in der Mathematik Bäume genannt werden und ihre Anwendung auf die Theorie chemischer Verbindungen». Berichte der Deutschen Chemischen Gesellschaft. 8 (2): 1056–1059. doi:10.1002/cber.18750080252 
• Cayley, A. (2009). «On the theory of the analytical forms called trees». The Collected Mathematical Papers. 3. [S.l.: s.n.] pp. 242–246. ISBN 978-0-511-70369-0. doi:10.1017/CBO9780511703690.046 
• Cayley, Arthur (1889). «A Theorem on Trees». Quarterly Journal of Pure and Applied Mathematics. 23: 376–378 
• Carpenter, Bob (1992). The Logic of Typed Feature Structures: With Applications to Unification Grammars, Logic Programs and Constraint Resolution. Col: Cambridge Tracts in Theoretical Computer Science. 32. [S.l.]: Cambridge University Press. ISBN 978-0-521-41932-1 
• Chalopin, J.; Gonçalves, D. (2009). «Every planar graph is the intersection graph of segments in the plane: Extended abstract». Proceedings of the Forty-First Annual ACM Symposium on Theory of Computing. [S.l.: s.n.] pp. 631–638. ISBN 978-1-60558-506-2. doi:10.1145/1536414.1536500 
• Chartrand, Gary (1985). Introductory Graph Theory. [S.l.]: Dover. ISBN 0-486-24775-9 
• Chartrand, Gary; Jordon, Heather; Vatter, Vincent; Zhang, Ping (2024). Graphs & Digraphs 7 ed. [S.l.]: CRC Press. p. 73. ISBN 978-1-032-13340-9 
• Cvetković, Dragoš M.; Rowlinson, Peter (2004). «Spectral graph theory». In: Lowell W. Beineke; Robin J. Wilson. Topics in Algebraic Graph Theory. [S.l.]: Cambridge University Press. ISBN 978-0-521-80197-3 
• Deo, Narsingh (1974). Graph Theory with Applications to Engineering and Computer Science. Englewood, Nova Jérsei: Prentice-Hall. ISBN 0-13-363473-6 
• Diestel, Reinhard (2025). Graph Theory. Col: Graduate Texts in Mathematics. 173 6 ed. [S.l.]: Springer. ISBN 978-3-662-70107-2. doi:10.1007/978-3-662-70107-2 
• Di Battista, Giuseppe; Eades, Peter; Tamassia, Roberto; Tollis, Ioannis G. (1994). «Algorithms for Drawing Graphs: an Annotated Bibliography». Computational Geometry: Theory and Applications. 4 (5): 235–282. doi:10.1016/0925-7721(94)00014-x 
• Dijkstra, Edsger W. (1959). «A Note on Two Problems in Connexion with Graphs». Numerische Mathematik. 1: 269–271. doi:10.1007/BF01386390 
• Drmota, Michael (2009). Random Trees: An Interplay between Combinatorics and Probability. [S.l.]: Springer Vienna. ISBN 978-3-211-75357-6. doi:10.1007/978-3-211-75357-6 
• Erdős, Paul; Rényi, Alfréd (1960). «On the Evolution of Random Graphs» (PDF). Publications of the Mathematical Institute of the Hungarian Academy of Sciences. 5: 17–61 
• Everett, Hazel; Corneil, Derek (1995). «Negative results on characterizing visibility graphs». Computational Geometry: Theory & Applications. 5 (2): 51–63. doi:10.1016/0925-7721(95)00021-Z 
• Feofiloff, Paulo; Kohayakawa, Yoshiharu; Wakabayashi, Yoshiko (2004). Uma introdução sucinta à teoria dos grafos (PDF). [S.l.]: Instituto de Matemática e Estatística da Universidade de São Paulo 
• Ford, Lester R.; Fulkerson, Delbert R. (1956). «Maximal Flow Through a Network». Canadian Journal of Mathematics. 8: 399–404. doi:10.4153/CJM-1956-045-5 
• Foulds, L. R. (1992). Graph Theory Applications. Col: Universitext. [S.l.]: Springer. ISBN 978-1-4612-0933-1 
• Gardner, Martin (1992). Fractal Music, Hypercards, and More: Mathematical Recreations from Scientific American. [S.l.]: W. H. Freeman and Company. p. 203 
• Gibbons, Alan (1985). Algorithmic Graph Theory. [S.l.]: Cambridge University Press 
• Godsil, Chris; Royle, Gordon F. (2001). Algebraic Graph Theory. [S.l.]: Springer. ISBN 978-1-4613-0163-9 
• Golumbic, Martin (1980). Algorithmic Graph Theory and Perfect Graphs. [S.l.]: Academic Press 
• Gross, J. L.; Tucker, T. W. (2012). Topological Graph Theory. [S.l.]: Dover Publications. ISBN 978-0-486-41741-7 
• Grünbaum, Branko (2006). «Configurations of points and lines». The Coxeter Legacy. Providence, Rhode Island: American Mathematical Society. pp. 179–225 
• Hahn, Geňa; Tardif, Claude (1997). «Graph homomorphisms: structure and symmetry». In: Geňa Hahn; Gert Sabidussi. Graph Symmetry: Algebraic Methods and Applications. [S.l.]: Kluwer Academic Publisher. ISBN 978-0-7923-4668-5 
• Harary, Frank (1969). Graph Theory. Reading, Massachusetts: Addison-Wesley 
• Harary, Frank; Palmer, Edgar M. (1973). Graphical Enumeration. Nova Iorque: Academic Press 
• Karp, Richard M. (1972). «Reducibility Among Combinatorial Problems». In: Raymond E. Miller; James W. Thatcher. Complexity of Computer Computations. [S.l.]: Plenum Press. pp. 85–103. doi:10.1007/978-1-4684-2001-2_9 
• Kaveh, A. (2013). Optimal Analysis of Structures by Concepts of Symmetry and Regularity. [S.l.]: Springer. ISBN 978-3-7091-1565-7 
• Kepner, Jeremy; Gilbert, John (2011). Graph Algorithms in the Language of Linear Algebra. Filadélfia, Pensilvânia: SIAM. ISBN 978-0-89871-990-1 
• L'Huillier, S. A. J. (1812–1813). «Mémoire sur la polyèdrométrie». Annales de Mathématiques. 3: 169–189 
• LaValle, Steven M. (1998). Rapidly-Exploring Random Trees: A New Tool for Path Planning (PDF). Col: Relatório técnico TR 98-11. [S.l.]: Departamento de Ciência da Computação, Iowa State University 
• Lehman, Eric; Leighton, F. Thomson; Meyer, Albert R. (2015). Mathematics for Computer Science (PDF). [S.l.]: MIT OpenCourseWare. Consultado em 3 de outubro de 2026 
• Lovász, László (2006). «Graph minor theory». Bulletin of the American Mathematical Society. 43 (1): 75–86. doi:10.1090/S0273-0979-05-01088-8 
• Lovász, László (2012). Large Networks and Graph Limits. Col: American Mathematical Society Colloquium Publications. 60. [S.l.]: American Mathematical Society. ISBN 978-0-8218-9085-1. doi:10.1090/coll/060 
• Mahadev, N. V. R.; Peled, Uri N. (1995). Threshold Graphs and Related Topics. [S.l.]: North-Holland 
• Malcolm, Donald G.; Roseboom, John H.; Clark, Charles E.; Fazar, Willard (1959). «Application of a Technique for Research and Development Program Evaluation». Operations Research. 7 (5): 646–669. doi:10.1287/opre.7.5.646 
• Malitz, Seth; Papakostas, Achilleas (1994). «On the angular resolution of planar graphs». SIAM Journal on Discrete Mathematics. 7 (2): 172–183. doi:10.1137/S0895480193242931 
• McDiarmid, Colin; Johnson, Theodore; Stone, Harold S. (1997). «On finding a minimum spanning tree in a network with random weights». Random Structures & Algorithms. 10 (1–2): 187–204. doi:10.1002/(SICI)1098-2418(199701/03)10:1/2<187::AID-RSA10>3.0.CO;2-6 
• McKee, Terry A.; McMorris, F. R. (1999). Topics in Intersection Graph Theory. [S.l.]: Society for Industrial and Applied Mathematics. ISBN 978-0-89871-430-2 
• Mohar, Bojan; Thomassen, Carsten (2001). Graphs on Surfaces. [S.l.]: Johns Hopkins University Press. ISBN 978-0-8018-6689-0. OCLC 45102952 
• Morin, Pat (22 de março de 2014). «Chapter 7: Random Binary Search Trees». Open Data Structures (in pseudocode) (PDF) 0.1Gβ ed. [S.l.: s.n.] pp. 145–164 
• Newman, Mark (2010). Networks: An Introduction. [S.l.]: Oxford University Press 
• National Research Council (2005). Network Science. Washington, D.C.: National Academies Press. ISBN 978-0-309-10026-7. doi:10.17226/11516 
• Ore, Øystein (1962). Theory of Graphs. [S.l.]: American Mathematical Society 
• Pach, János (2018). «Geometric Graph Theory». In: Csaba D. Toth; Joseph O'Rourke; Jacob E. Goodman. Handbook of Discrete and Computational Geometry 3 ed. [S.l.]: CRC Press 
• Pach, János; Sharir, Micha (2009). «5.5 Angular resolution and slopes». Combinatorial Geometry and Its Algorithmic Applications: The Alcalá Lectures. Col: Mathematical Surveys and Monographs. 152. [S.l.]: American Mathematical Society. pp. 126–127 
• Persinger, C. A. (1966). «Subsets of $n$-books in $E^{3}$». Pacific Journal of Mathematics. 18: 169–173. doi:10.2140/pjm.1966.18.169 
• Richeson, D. (2008). Euler's Gem: The Polyhedron Formula and the Birth of Topology. [S.l.]: Princeton University Press 
• Robertson, Neil; Seymour, Paul D. (2004). «Graph Minors. XX. Wagner's conjecture». Journal of Combinatorial Theory, Series B. 92 (2): 325–357. doi:10.1016/j.jctb.2004.08.001 
• Sedgewick, Robert; Flajolet, Philippe (2013). «Chapter 6: Trees». An Introduction to the Analysis of Algorithms 2 ed. [S.l.]: Addison-Wesley. ISBN 9780133373486 
• Society for Industrial and Applied Mathematics (2002). «The George Polya Prize». Looking Back, Looking Ahead: A SIAM History (PDF). [S.l.: s.n.] p. 26. Consultado em 14 de março de 2016. Cópia arquivada (PDF) em 5 de março de 2016 
• Sylvester, James Joseph (1878). «Chemistry and Algebra». Nature. 17 (432): 284. doi:10.1038/017284a0 
• Thurston, William (março de 2002). «§13.6, Andreev's theorem and generalizations, and §13.7, Constructing patterns of circles». The Geometry and Topology of 3-manifolds. [S.l.]: MSRI Publications. pp. 330–346. Versão eletrônica 1.1. Consultado em 9 de dezembro de 2025 
• Tutte, W. T. (1963). «How to Draw a Graph». Proceedings of the London Mathematical Society. 3. 13 (1): 743–767. doi:10.1112/plms/s3-13.1.743 
• Tutte, W. T. (2001). Graph Theory. [S.l.]: Cambridge University Press. ISBN 978-0-521-79489-3 
• Watts, Duncan J.; Strogatz, Steven H. (1998). «Collective dynamics of 'small-world' networks». Nature. 393 (6684): 440–442. PMID 9623998. doi:10.1038/30918 
• Wilson, David Bruce (1996). «Generating random spanning trees more quickly than the cover time». Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing (STOC 1996). [S.l.: s.n.] pp. 296–303. ISBN 0-89791-785-5. doi:10.1145/237814.237880 
• Witten, T. A.; Sander, L. M. (1981). «Diffusion-Limited Aggregation, a Kinetic Critical Phenomenon». Physical Review Letters. 47 (19): 1400–1403. doi:10.1103/PhysRevLett.47.1400 
• Zhao, Yufei (2023). Graph Theory and Additive Combinatorics: Exploring Structure and Randomness. [S.l.]: Cambridge University Press. ISBN 978-1-009-31094-9 
• Ziegler, Günter M. (2007). «Convex polytopes: extremal constructions and $f$-vector shapes. Section 1.3: Steinitz's theorem via circle packings». In: Ezra Miller; Victor Reiner; Bernd Sturmfels. Geometric Combinatorics. Col: IAS/Park City Mathematics Series. 13. [S.l.]: American Mathematical Society. pp. 628–642. ISBN 978-0-8218-3736-8 

Leitura adicional

• Introdução à teoria dos grafos, percurso introdutório do Portal da Matemática OBMEP/IMPA, com videoaulas, textos e exercícios
• Uma introdução sucinta à teoria dos grafos, de Paulo Feofiloff, Yoshiharu Kohayakawa e Yoshiko Wakabayashi, IME-USP
• Exercícios de teoria dos grafos, organizado por Paulo Feofiloff, IME-USP
• Teoria dos grafos, notas de aula de Gabriel Coutinho, UFMG
• Matemática discreta, livro da eduCAPES com uma unidade de teoria dos grafos
• Teoria dos grafos, apontamentos da Universidade de Coimbra
• Mathematics for Computer Science, texto e materiais do MIT OpenCourseWare, com capítulos sobre grafos (em inglês)
• Graph Theory, de Reinhard Diestel, livro de graduação avançada e pós-graduação disponibilizado pelo autor (em inglês)
• Digraphs: Theory, Algorithms and Applications, de Jørgen Bang-Jensen e Gregory Gutin, Royal Holloway, Universidade de Londres (em inglês)
• Network Science, relatório das Academias Nacionais dos Estados Unidos sobre ciência de redes (em inglês)

Ligações externas

• Commons
• Wikiversidade

Recursos em português

• Uma introdução sucinta à teoria dos grafos, livro de Paulo Feofiloff, Yoshiharu Kohayakawa e Yoshiko Wakabayashi, Instituto de Matemática e Estatística da Universidade de São Paulo (edição integral em PDF)
• Exercícios de teoria dos grafos, Instituto de Matemática e Estatística da Universidade de São Paulo
• Livros de teoria dos grafos, bibliografia comentada do Instituto de Matemática e Estatística da Universidade de São Paulo
• Teoria dos grafos, material da Olimpíada Brasileira de Matemática
• Introdução à teoria dos grafos, videoaulas, textos, exercícios e aplicativo do Portal da Matemática OBMEP/IMPA
• Teoria dos grafos, material didático da Universidade Federal do Rio Grande do Sul
• Teoria dos grafos, notas de Gabriel Coutinho, Departamento de Ciência da Computação da Universidade Federal de Minas Gerais
• Teoria dos grafos, material do Departamento de Informática da Universidade Federal do Paraná
• Teoria dos grafos, aulas e materiais do Programa de Engenharia de Sistemas e Computação da Universidade Federal do Rio de Janeiro
• Teoria dos grafos, notas de aula e exercícios da Universidade Federal de Campina Grande
• Matemática discreta, livro didático com unidade introdutória sobre teoria dos grafos, portal eduCAPES
• Grafos: conceitos fundamentais, algoritmos e aplicações, livro da Editora do Instituto Federal Catarinense
• Introdução à teoria dos grafos, notas de aula da Universidade Tecnológica Federal do Paraná
• Teoria dos grafos, apontamentos da Universidade de Coimbra
• Combinatória e teoria dos grafos, apontamentos e fichas do Instituto Superior Técnico da Universidade de Lisboa
• Rocs, ambiente de desenvolvimento para teoria dos grafos

Recursos de consulta e pesquisa em outras línguas

• "Graph theory", Encyclopedia of Mathematics (em inglês)
• Graph theory tutorial, tutorial da Universidade do Tennessee em Martin, arquivado em 16 de janeiro de 2012 (em inglês)
• Banco de dados pesquisável de pequenos grafos conexos (em inglês)
• House of Graphs, banco de dados com busca por desenhos de grafos (em inglês)
• Galeria de imagens de grafos, arquivada em 6 de fevereiro de 2006 (em inglês)
• Lista comentada de recursos para pesquisadores, versão arquivada (em inglês)
• The Social Life of Routers, texto introdutório sobre grafos de pessoas e computadores (em inglês)
• Obras sobre teoria dos grafos no WorldCat (em inglês)

Software e algoritmos em outras línguas

• Graph Theory Software, ferramentas de ensino e aprendizagem (em inglês)
• Lista de algoritmos de grafos, com referências e ligações para bibliotecas de programação, arquivada em 13 de julho de 2019 (em inglês)

Livros em outras línguas disponíveis na internet

• Hartmann, Alexander K.; Weigt, Martin (2005). «Introduction to graphs». Phase Transitions in Combinatorial Optimization Problems: Basics, Algorithms and Statistical Mechanics. [S.l.]: Wiley. pp. 25–66. ISBN 978-3-527-60673-3. arXiv:cond-mat/0602129. doi:10.1002/3527606734.ch3  (em inglês)
• Digraphs: Theory, Algorithms and Applications, de Jørgen Bang-Jensen e Gregory Gutin, 2007 (em inglês)
• Graph Theory, de Reinhard Diestel (em inglês)