Frucht graf - Frucht graph

Frucht graf
Fruchtův graf
Pojmenoval podle	Robert Frucht
Vrcholy	12
Hrany	18
Poloměr	3
Průměr	4
Obvod	3
Automorfismy	1 ({id})
Chromatické číslo	3
Chromatický index	3
Vlastnosti	Krychlový Halin Pancyklický
Tabulka grafů a parametrů

V matematický pole teorie grafů, Frucht graf je 3-běžný graf s 12 vrcholy, 18 hranami a bez netriviálnosti symetrie.^[1] Poprvé to popsal Robert Frucht v roce 1939.^[2]

Fruchtův graf je a pancyklický Halinův graf s chromatické číslo 3, chromatický index 3, poloměr 3 a průměr 4. Stejně jako u každého Halinova grafu je i Fruchtův graf mnohostěnný (rovinný a 3-vrchol připojený ) a Hamiltonian, s obvod 3. Jeho číslo nezávislosti je 5.

Fruchtův graf lze sestrojit z LCF notace: [−5,−2,−4,2,5,−2,2,5,−2,−5,4,2].

Algebraické vlastnosti

Fruchtův graf je jedním z pěti nejmenších kubické grafy vlastnit pouze jednu automatický graf, identita^[3] (to znamená, že každý vrchol lze topologicky odlišit od všech ostatních vrcholů). Takové grafy se nazývají asymetrický (nebo identita) grafy. Fruchtova věta uvádí, že jakýkoli skupina lze realizovat jako skupinu symetrií grafu,^[2] a posílení této věty také kvůli Frucht uvádí, že kteroukoli skupinu lze realizovat jako symetrie 3-regulárního grafu;^[4] Fruchtův graf poskytuje příklad této realizace pro triviální skupina.

The charakteristický polynom Fruchtova grafu je ${displaystyle (x-3) (x-2) x (x + 1) (x + 2) (x ^ {3} + x ^ {2} -2x-1) (x ^ {4} + x ^ { 3} -6x ^ {2} -5x + 4)}$.

Galerie

• 

  The chromatické číslo Fruchtova grafu je 3.

• 

  Fruchtův graf je Hamiltonian.

Viz také

Reference