Teoria dos grafos

Elementos, tipos e notação

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 ${\displaystyle G=(V,E)}$. A letra ${\displaystyle V}$ designa o conjunto de vértices, e ${\displaystyle 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 é ${\displaystyle |V|}$, e seu tamanho é ${\displaystyle |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 ${\displaystyle \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

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

A distância ${\displaystyle 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

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 ${\displaystyle 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

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

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.

Origens e século XIX

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

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

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ção visual: desenho de grafos

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

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 ${\displaystyle (i,j)}$ informa se ${\displaystyle i}$ e ${\displaystyle j}$ são adjacentes. Quando ${\displaystyle A}$ é essa matriz, a entrada ${\displaystyle (i,j)}$ de ${\displaystyle A^{k}}$ conta os passeios de comprimento ${\displaystyle k}$ que vão de ${\displaystyle i}$ a ${\displaystyle 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

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.

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.

Transformações, equivalências e dualidades

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.

Caminhos, ciclos e conectividade

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

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

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 ${\displaystyle 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

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

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 ${\displaystyle \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 ${\displaystyle K_{3,3}}$, relacionado ao problema das três casas, nem o grafo completo ${\displaystyle 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 ${\displaystyle K_{3,3}}$ nem o grafo completo ${\displaystyle 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 ${\displaystyle 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

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 ${\displaystyle n-1}$ árvores especificadas, com respectivamente 1, 2, 3, ..., ${\displaystyle n-1}$ arestas, sejam empacotadas sem sobreposição de arestas no grafo completo ${\displaystyle 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 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

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.

Teoria estrutural dos grafos

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

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 ${\displaystyle 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 ${\displaystyle 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

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

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

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 ${\displaystyle 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 ${\displaystyle \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

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 ${\displaystyle G(n,p)}$, começa-se com ${\displaystyle n}$ vértices. Cada par distinto recebe uma aresta, de modo independente, com probabilidade ${\displaystyle p}$. Mudar ${\displaystyle p}$ produz fenômenos de limiar. Considere ${\displaystyle p=c/n}$, com ${\displaystyle c}$ constante e ${\displaystyle n}$ crescendo sem limite. Se ${\displaystyle c<1}$, as componentes têm tamanho sublinear com probabilidade que tende a 1. Se ${\displaystyle c>1}$, surge com a mesma garantia assintótica uma componente conexa com número de vértices proporcional a ${\displaystyle 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.

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 ${\displaystyle n^{n-2}}$ árvores rotuladas com ${\displaystyle n}$ vértices. Esse também é o número de árvores geradoras do grafo completo ${\displaystyle K_{n}}$.

Teoria algorítmica dos grafos

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.

Ciência de 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

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

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

Física, química e engenharia

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

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

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.

Recursos em português

Recursos de consulta e pesquisa em outras línguas

Software e algoritmos em outras línguas

Livros em outras línguas disponíveis na internet

• Portal da matemática