Grafo de Frucht
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]
Grafo de Frucht | |
---|---|
![]() | |
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 |
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
editarO 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 .
Galeria
editar-
O grafo de Frucht é planar.
-
O número cromático do grafo de Frucht é 3.
-
O grafo de Frucht é Hamiltoniano.
- ↑ Weisstein, Eric W. «Frucht Graph». MathWorld (em inglês)
- ↑ a b Frucht, R. (1939), «Herstellung von Graphen mit vorgegebener abstrakter Gruppe.», Compositio Mathematica, ISSN 0010-437X (em German), 6: 239–250
- ↑ Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, 1990
- ↑ FRUCHT, R. (1949). «Graphs of degree three with a given abstract group». Canadian Journal of Mathematics. 1. pp. 365–378. ISSN 0008-414X