Grafo de Frucht

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
Grafo de Frucht
Frucht graph.neato.svg
Nomeado em honra a Robert Frucht
vértices 12
arestas 18
Raio 3
Diâmetro 4
Cintura 3
Automorfismos 1 ({id})
Número cromático 3
Índice cromático 3
Propriedades Cúbico
Planar
Hamiltoniano

No campo da matemática da teoria dos grafos, o Grafo de Frucht é um grafo 3-regular com 12 vértices e 18 arestas e nenhuma simetria não-trivial.[1] Foi descrito pela primeira vez por Robert Frucht em 1939.[2]

O grafo de Frucht é um grafo Halin com número cromático 3, índice cromático 3, raio 3, diâmetro 4, e cintura 3. Como em todos os grafos Halin, o grafo de Frucht é planar, 3-vértice-conectado, e poliédrico. É também um grafo 3-aresta-conectado.

O grafo de Frucht é hamiltoniano e pode ser construído a partir da notação LCF: [−5,−2,−4,2,5,−2,2,5,−2,−5,4,2].

Propriedades algébricas[editar | editar código-fonte]

O grafo de Frucht é o menor grafo cúbico possuindo somente um único automorfismo de grafos, a identidade[3] (ou seja, cada vértice pode ser distinguido topologicamente de todos os outros vértices). Tais grafos são chamados assimétricos (ou identidade). O teorema de Frucht diz que qualquer grupo pode ser compreendido como o grupo de simetrias de um grafo,[2] e um reforço deste teorema também devido à Frucht afirma que qualquer grupo pode ser percebido como as simetrias de um grafo 3-regular;[4] o grafo de Frucht fornece um exemplo desta realização para o grupo trivial.

O polinômio característico do grafo de Frucht é igual a (x-3) (x-2) x (x+1) (x+2) (x^3+x^2-2 x-1) (x^4+x^3-6 x^2-5 x+4).

Galeria[editar | editar código-fonte]

Referências

  1. Eric W. Weisstein, Frucht Graph em MathWorld
  2. a b Frucht, R. (1939), "Herstellung von Graphen mit vorgegebener abstrakter Gruppe." (em German), Compositio Mathematica 6: 239–250, ISSN 0010-437X, http://www.numdam.org/item?id=CM_1939__6__239_0 
  3. Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990
  4. FRUCHT, R.. (1949). "Graphs of degree three with a given abstract group". Canadian Journal of Mathematics 1: 365–378. ISSN 0008-414X.