Pesquisa · Mapa mental

Teoria dos grafos

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.

Fonte: Wikipédia (pt)Atualizado em 31/10/2026
01

Definição e conceitos fundamentais

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.[nota 1] 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.[nota 2] 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.[nota 3] 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.

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.[nota 9] 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.[nota 10] 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.[nota 11]

Distâncias, parâmetros e invariantes

A distância d ( u , v ) {\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.[nota 12] 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.[nota 13] 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 n − 1 {\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.[nota 14] Todo grafo conexo contém uma árvore geradora, uma árvore que passa por todos os seus vértices.[nota 15] 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.[nota 16]

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.[nota 17] 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.[nota 18] 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.

02

História

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.[nota 19] 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.[nota 20] 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.[nota 21] 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.

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.[nota 22] 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.

03

Representações de grafos

Como um grafo é uma abstração de relações, a mesma estrutura pode receber representações diferentes.[nota 24] 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

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.

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

04

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.[nota 28] 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.[nota 29]

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.[nota 30]

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.[nota 31]

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.[nota 32] 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.[nota 33]

05

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. 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.[nota 42] Harary e Palmer reúnem uma parte ampla desses problemas. Na geometria computacional, grafos de visibilidade registram quais pontos ou regiões podem ser ligados por segmentos que não atravessam obstáculos.[nota 43] 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.

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. 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.[nota 34]

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.[nota 35] 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. 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.[nota 36] 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.

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.[nota 37] 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.

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.[nota 38] 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 ) ) {\displaystyle \exp((\log n)^{O(1)})} .[nota 39]

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 n − 1 {\displaystyle n-1} árvores especificadas, com respectivamente 1, 2, 3, ..., n − 1 {\displaystyle n-1} arestas, sejam empacotadas sem sobreposição de arestas no grafo completo K n {\displaystyle K_{n}} . Os problemas estudados abrangem os itens abaixo.

06

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

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.

Teoria topológica dos grafos

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.[nota 44] 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.[nota 45] 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.

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.[nota 47] 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.[nota 48] 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.

Teoria geométrica dos grafos

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.[nota 49] 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.

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.[nota 50] 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 {\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.[nota 51]

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

07

Aplicações

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.[nota 55] 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.[nota 67] 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.

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.[nota 56]

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.

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.[nota 61] 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.[nota 63] 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.

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.[nota 65]

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.[nota 66] 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.

Vídeos recomendados

Fontes consultadas

Continue pesquisando