Mostrar código-fonte de Teoria algébrica dos grafos

[[Imagem:Petersen1_tiny.svg|miniaturadaimagem|200x200px| Um gráfico altamente simétrico, o [[Grafo de Petersen|gráfico de Petersen]], que é [[Grafo vértice-transitivo|transitivo em vértices]], [[Grafo simétrico|simétrico]], [[Grafo distância-transitivo|transitivo a]] [[Grafo distância-regular|distância e regular a distância]] . Possui [[diâmetro]] 2. Seu [[Automorfismo de grafos|grupo de automorfismo]] possui 120 elementos e é de fato o grupo simétrico <math>S_5</math> .]]
'''A [[Teoria dos grafos|teoria algébrica dos grafos]]''' é um ramo da [[matemática]] em que os métodos [[Álgebra|algébricos]] são aplicados a problemas sobre [[Grafo|grafos.]] Isso contrasta com as abordagens [[teoria geométrica de grafos|geométricas]], [[Combinatória|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 dos grupos|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 [[autodecomposição de uma matriz|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 de grafos|teoria espectral dos grafos]]). Para o [[Grafo de Petersen|gráfico de Petersen]], por exemplo, o espectro da matriz de adjacência é (−2, &nbsp; -2, &nbsp; -2, &nbsp; -2, &nbsp; 1 &nbsp; 1 &nbsp; 1 &nbsp; 1 &nbsp; 1 &nbsp; 3) Vários teoremas relacionam propriedades do espectro a outras [[propriedade de um grafo|propriedades gráficas]] . Como um exemplo simples, um gráfico [[Conectividade (teoria dos grafos)|conectado]] com [[Distância (teoria dos grafos)|diâmetro]] ''D'' terá pelo menos ''D'' +1 valores distintos em seu espectro. <ref name="biggs">{{Citation|last=Biggs, Norman|title=Algebraic Graph Theory|edition=2nd|place=Cambridge|publisher=Cambridge University Press|year=1993|isbn=0-521-45897-8|postscript=<!--none-->}}</ref> [[Conectividade algébrica|Aspectos]] dos espectros de gráficos têm sido utilizados na análise da [[sincronização]] das [[Análise de rede|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 dos grupos|teoria de grupos]], particularmente [[Automorfismo de grafos|grupos de automorfismo]] e [[Teoria geométrica de grupos|teoria de]] grupos geométricos. O foco é colocado em várias famílias de gráficos baseados em [[simetria]] (como [[Grafo simétrico|gráficos simétricos]], gráficos [[Grafo vértice-transitivo|transitivos em vértices, gráficos transitivos em]] [[Grafo aresta-transitivo|arestas, gráficos transitivos a]] [[Grafo distância-transitivo|distância, gráficos transitivos a]] [[Grafo distância-regular|distância, gráficos regulares a distância e gráficos]] [[Grafo fortemente regular|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 [[Grupo (matemática)|grupos]] podem ser representados como o grupo automorfismo de um gráfico conectado (de fato, de um [[Grafo cúbico|gráfico cúbico]]). <ref>[[R. Frucht]]. Graphs of Degree 3 with given abstract group, Can. J. Math. 3 1949.</ref> 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. <ref name="biggs">{{Citation|last=Biggs, Norman|title=Algebraic Graph Theory|edition=2nd|place=Cambridge|publisher=Cambridge University Press|year=1993|isbn=0-521-45897-8|postscript=<!--none-->}}</ref>
[[Imagem:TruncatedTetrahedron.gif|esquerda|miniaturadaimagem|220x220px| Um [[Grafo de Cayley|gráfico de Cayley]] para o [[Grupo alternante|grupo alternativo]] ''A'' <sub>4</sub>, formando um [[tetraedro truncado]] em três dimensões. Todos os gráficos Cayley são [[Grafo vértice-transitivo|transitivos por vértices]], mas alguns gráficos transitivos por vértices (como o [[Grafo de Petersen|gráfico de Petersen]] ) não são gráficos de Cayley.]]
[[Imagem:Petersen_graph_3-coloring.svg|direita|miniaturadaimagem|200x200px| Uma coloração de vértice adequada do [[Grafo de Petersen|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 <ref name="biggs">{{Citation|last=Biggs, Norman|title=Algebraic Graph Theory|edition=2nd|place=Cambridge|publisher=Cambridge University Press|year=1993|isbn=0-521-45897-8|postscript=<!--none-->}}</ref> (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 [[Teoria do caráter|caracteres irredutíveis]].  <ref name="babai">{{Citation|first1=L|last=Babai|editor-last=Graham|editor-first=R|editor2-last=Grötschel|editor2-first=M|editor2-link=Martin Grötschel|editor3-last=Lovász|editor3-first=L|title=Handbook of Combinatorics|contribution=Automorphism groups, isomorphism, reconstruction|contribution-url=http://www.cs.uchicago.edu/files/tr_authentic/TR-94-10.ps|year=1996|publisher=Elsevier|postscript=<!--none-->}}</ref>

=== Estudando invariantes em gráficos ===
Finalmente, o terceiro ramo da teoria algébrica dos grafos diz respeito às propriedades algébricas dos [[propriedade de um grafo|invariantes]] de grafos e, especialmente, do [[polinômio cromático]], do [[ Tutte polinomial |polinômio de Tutte]] e dos [[Nó invariante|invariantes de nó]]. O polinômio cromático de um grafo, por exemplo, conta o número de suas [[Coloração de grafos|cores de vértice]] apropriadas. Para o gráfico de Petersen, esse polinômio é <math>t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)</math> . <ref name="biggs">{{Citation|last=Biggs, Norman|title=Algebraic Graph Theory|edition=2nd|place=Cambridge|publisher=Cambridge University Press|year=1993|isbn=0-521-45897-8|postscript=<!--none-->}}</ref> 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|teorema]] das quatro cores . No entanto, ainda existem muitos [[Coloração de grafos|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 espectral de grafos|Teoria dos grafos espectrais]]
* [[Combinatória algébrica]]
* [[Conectividade algébrica]]
* [[Decomposição de Dulmage-Mendelsohn]]
* [[propriedade de um grafo|Propriedade do grafo]]
* [[Matriz de adjacência]]

== Referências ==
{{Referências}}{{refbegin}}
*{{citation|first1=Chris|last1=Godsil|authorlink1=Chris Godsil|first2=Gordon|last2=Royle|authorlink2=Gordon Royle|title=Algebraic Graph Theory|series=Graduate Texts in Mathematics|volume=207|publisher=Springer-Verlag|location=New York|year=2001|postscript=<!--none-->}}.
{{refend}}

== Ligações externas ==
* {{Commonscat-inline}}

[[Categoria:Teoria dos grafos]]
[[Categoria:Álgebra]]