Teoria algébrica dos grafos

Um gráfico altamente simétrico, o gráfico de Petersen, que é transitivo em vértices, simétrico, transitivo a distância e regular a distância . Possui diâmetro 2. Seu grupo de automorfismo possui 120 elementos e é de fato o grupo simétrico $S_{5}$ .

A teoria algébrica dos grafos é um ramo da matemática em que os métodos algébricos são aplicados a problemas sobre grafos. Isso contrasta com as abordagens geométricas, combinatórias ou algorítmicas . Existem três ramos principais da teoria de grafos algébricos, envolvendo o uso de álgebra linear, o uso de teoria de grupos e o estudo de grafos invariantes.

Ramos da teoria algébrica dos grafos

Usando álgebra linear

O primeiro ramo da teoria algébrica de grafos envolve o estudo de grafos em conexão com álgebra linear . Especialmente, estuda o espectro da matriz de adjacência, ou a matriz laplaciana de um gráfico (essa parte da teoria algébrica dos grafos também é chamada de teoria espectral dos grafos). Para o gráfico de Petersen, por exemplo, o espectro da matriz de adjacência é (−2,   -2,   -2,   -2,   1   1   1   1   1   3) Vários teoremas relacionam propriedades do espectro a outras propriedades gráficas . Como um exemplo simples, um gráfico conectado com diâmetro D terá pelo menos D +1 valores distintos em seu espectro. Aspectos dos espectros de gráficos têm sido utilizados na análise da sincronização das redes de internet.

Usando teoria de grupos

O segundo ramo da teoria algébrica de grafos envolve o estudo de gráficos em conexão com a teoria de grupos, particularmente grupos de automorfismo e teoria de grupos geométricos. O foco é colocado em várias famílias de gráficos baseados em simetria (como gráficos simétricos, gráficos transitivos em vértices, gráficos transitivos em arestas, gráficos transitivos a distância, gráficos transitivos a distância, gráficos regulares a distância e gráficos fortemente regulares) e nas relações de inclusão entre essas famílias. Algumas dessas categorias de gráficos são escassas o suficiente para que listas de gráficos possam ser elaboradas. Pelo teorema de Frucht, todos os grupos podem ser representados como o grupo automorfismo de um gráfico conectado (de fato, de um gráfico cúbico). Outra conexão com a teoria de grupos é que, a partir de qualquer grupo, podem ser gerados grafos simétricos conhecidos como grafo de Cayley, os quais possuem propriedades relacionadas à estrutura do grupo.

Um gráfico de Cayley para o grupo alternativo A ₄, formando um tetraedro truncado em três dimensões. Todos os gráficos Cayley são transitivos por vértices, mas alguns gráficos transitivos por vértices (como o gráfico de Petersen ) não são gráficos de Cayley.

Uma coloração de vértice adequada do gráfico de Petersen com 3 cores, o número mínimo possível. De acordo com o polinômio cromático, existem 120 desses coloridos com 3 cores.

Este segundo ramo da teoria algébrica dos grafos está relacionado ao primeiro, uma vez que as propriedades de simetria de um gráfico são refletidas em seu espectro. Em particular, o espectro de um gráfico altamente simétrico, como o gráfico de Petersen, possui poucos valores distintos (o gráfico de Petersen possui 3, que é o mínimo possível, dado seu diâmetro). Para grafos de Cayley, o espectro pode ser relacionado diretamente à estrutura do grupo, em particular aos seus caracteres irredutíveis.

Estudando invariantes em gráficos

Finalmente, o terceiro ramo da teoria algébrica dos grafos diz respeito às propriedades algébricas dos invariantes de grafos e, especialmente, do polinômio cromático, do polinômio de Tutte e dos invariantes de nó. O polinômio cromático de um grafo, por exemplo, conta o número de suas cores de vértice apropriadas. Para o gráfico de Petersen, esse polinômio é $t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)$ . Em particular, isso significa que o gráfico Petersen não pode ser adequadamente colorido com uma ou duas cores, mas pode ser colorido de 120 maneiras diferentes com três cores. Muito trabalho nessa área da teoria dos grafos algébricos foi motivado por tentativas de provar o teorema das quatro cores . No entanto, ainda existem muitos problemas em aberto, como caracterizar gráficos que possuem o mesmo polinômio cromático e determinar quais polinômios são cromáticos.

Ver também

• Teoria dos grafos espectrais
• Combinatória algébrica
• Conectividade algébrica
• Decomposição de Dulmage-Mendelsohn
• Propriedade do grafo
• Matriz de adjacência

Ligações externas

• Media relacionados com Teoria algébrica dos grafos no Wikimedia Commons