Herschelův graf - Herschel graph

Herschelův graf
Herschelův graf LS.svg
Herschelův graf.
Pojmenoval podleAlexander Stewart Herschel
Vrcholy11
Hrany18
Poloměr3
Průměr4
Obvod4
Automorfismy12 (D6)
Chromatické číslo2
Chromatický index4
VlastnostiPolyhedrální
Rovinný
Bipartitní
Perfektní
Tabulka grafů a parametrů

v teorie grafů, pobočka matematika, Herschelův graf je bipartitní neorientovaný graf s 11 vrcholy a 18 hranami, nejmenší non-Hamiltonian mnohostěnný graf. Je pojmenována po britském astronomovi Alexander Stewart Herschel.

Vlastnosti

Herschelův graf je a rovinný graf: lze ho nakreslit v rovině, aniž by se protínal žádný z jeho okrajů. Je to také 3-vrchol připojený: odstranění jakýchkoli dvou z jeho vrcholů ponechává spojené podgraf. Je to bipartitní graf: jeho vrcholy lze rozdělit do dvou podskupin po pěti a šesti vrcholů, takže každá hrana má v každé podskupině koncový bod (červená a modrá podskupina na obrázku). Stejně jako u každého bipartitního grafu je Herschelův graf perfektní graf : chromatické číslo ze všech indukovaný podgraf se rovná velikosti největšího klika toho podgrafu. Má také chromatický index 4, obvod 4, poloměr 3 a průměr 4.

Mnohostěn

Herschelův graf jako mnohostěn.[1] Kliknutím sem zobrazíte animovanou verzi.

Herschelův graf je rovinný a propojený se 3 vrcholy, takže následuje Steinitzova věta že je to polyedrický graf: existuje konvexní mnohostěn (an enneahedron ), který má Herschelův graf jako svůj kostra.[2]Tento mnohostěn má devět čtyřúhelníků pro tváře, které lze zvolit tak, aby tvořily tři kosočtverec a šest draci.[1]

Své duální mnohostěn je opraveno trojúhelníkový hranol, vytvořený jako konvexní obal středů okrajů a trojúhelníkový hranol.Tento mnohostěn má vlastnost, že jeho tváře nelze číslovat takovým způsobem, že se na sousedních plochách objevují po sobě jdoucí čísla a že první a poslední číslo jsou také na sousedních plochách. Protože mnohostěnné číslování tváří tohoto typu se používá jako „spindown počítadla života "ve hře Magic: The Gathering, Constantinides & Constantinides (2018) pojmenujte kanonický mnohostěn realizace tohoto dvojitého mnohostěnu jako „Lichova nemesis“.[3]

Hamiltonicita

Hamiltonova cesta (ale ne cyklus) v Herschel grafu

Jako bipartitní graf, který má lichý počet vrcholů, Herschelův graf neobsahuje a Hamiltonovský cyklus (cyklus hran, který prochází každým vrcholem přesně jednou). V jakémkoli bipartitním grafu musí jakýkoli cyklus střídat vrcholy na obou stranách bipartice, a proto musí obsahovat stejný počet obou typů vrcholů a musí mít sudou délku. Cyklus procházející jednou každým z jedenácti vrcholů tedy nemůže v Herschelově grafu existovat. Jedná se o nejmenší nehamiltonovský polyedrický graf, ať už se velikost grafu měří z hlediska počtu vrcholů, hran nebo ploch.[4] Existují další mnohostěnné grafy s 11 vrcholy a bez hamiltonovských cyklů (zejména Goldner – Hararyův graf[5]), ale žádný s méně hranami.[2]

Všichni až na tři vrcholy Herschelova grafu mají stupeň tři. Taitova domněnka[6] uvádí, že mnohostěnný graf, ve kterém každý vrchol má stupeň tři musí být Hamiltonian, ale to bylo vyvráceno, když W. T. Tutte poskytl protiklad, mnohem větší Tutte graph.[7] Vylepšení Taitova domněnky, Barnettina domněnka že každý bipartitní 3-pravidelný polyedrický graf je hamiltoniánský, zůstává otevřený.[8]

Každý maximální rovinný graf který nemá hamiltonovský cyklus, má Herschelův graf jako a Méně důležitý. Herschelův graf je považován za jeden ze tří menších-minimálních ne-hamiltonovských grafů spojených se 3 vrcholy. Další dva jsou kompletní bipartitní graf a graf vytvořený rozdělením Herschelova grafu a do dvou symetrických polovin pomocí třívertexových oddělovačů a poté kombinováním jedné poloviny z každého grafu.[9]

The mediální graf grafu Herschel je 4-pravidelný rovinný graf bez č Hamiltoniánský rozklad. Stínované oblasti odpovídají vrcholům podkladového Herschelova grafu.

Herschelův graf také poskytuje příklad polyedrického grafu, pro který mediální graf nelze rozložit na dva Hamiltonovské cykly s disjunktními hranami. Mediální graf Herschelova grafu je 4běžný graf s 18 vrcholy, jeden pro každý okraj Herschel grafu; dva vrcholy sousedí v mediálním grafu, kdykoli jsou odpovídající okraje Herschelova grafu po sobě jdoucí na jedné z jeho ploch.[10]to je 4-vrchol připojený a v podstatě spojeno se 6 okraji, což znamená, že pro každý oddíl vrcholů do dvou podmnožin alespoň dvou vrcholů existuje nejméně šest hran protínajících oddíl.[11]

Dějiny

Herschelův graf je pojmenován po britském astronomovi Alexander Stewart Herschel, který napsal ranou práci týkající se William Rowan Hamilton je icosian hra: Herschelův graf popisuje nejmenší konvexní mnohostěn pro které tato hra nemá řešení. Nicméně, Herschel papír popsal řešení pro Icosian hry pouze na grafech pravidelný čtyřstěn a pravidelný dvacetistěn; nepopisoval Herschelův graf.[12]Název „Herschelův graf“ se v učebnici teorie grafů od raného věku objevil John Adrian Bondy a U. S. R. Murty, publikovaná v roce 1976.[13] Samotný graf však byl popsán dříve, například H. S. M. Coxeter.[2]

Reference

  1. ^ A b Lawson-Perfect, Christian (13. října 2013), „Enneahedron for Herschel“, Aperiodikum, vyvoláno 7. prosince 2016
  2. ^ A b C Coxeter, H. S. M. (1973), Pravidelné Polytopes, Dover, s. 8.
  3. ^ Constantinides, Anthony F .; Constantinides, George A. (říjen 2018), „Spindown Polyhedra“, Matematický věstník, 102 (555): 447–453, doi:10.1017 / mag.2018.111
  4. ^ Barnette, David; Jucovič, Ernest (1970), „Hamiltonovské okruhy na 3-polytopech“, Journal of Combinatorial Theory, 9 (1): 54–59, doi:10.1016 / S0021-9800 (70) 80054-0.
  5. ^ Weisstein, Eric W., „Goldner-Harary Graph“, MathWorld.
  6. ^ Tait, P. G. (1884), „Výpis Topologie", Filozofický časopis, 5. série, 17: 30–46. Přetištěno Vědecké práce, Sv. II, s. 85–98.
  7. ^ Tutte, W. T. (1946), „Na Hamiltonových okruzích“ (PDF), Journal of the London Mathematical Society, 21 (2): 98–101, doi:10.1112 / jlms / s1-21.2.98.
  8. ^ Samal, Robert (11. června 2007), Barnettina domněnka Zahrada otevřeného problému, vyvoláno 24. února 2011
  9. ^ Ding, Guoli; Marshall, Emily (2018), „Minimal -připojené nehailtonovské grafy ", Grafy a kombinatorika, 34 (2): 289–312, doi:10.1007 / s00373-018-1874-z, PAN  3774453
  10. ^ Bondy, J. A .; Häggkvist, R. (1981), „Edge-disjoint Hamiltonovy cykly ve 4-pravidelných rovinných grafech“, Aequationes Mathematicae, 22 (1): 42–45, doi:10.1007 / BF02190157.
  11. ^ Király, Csaba; Péterfalvi, Ferenc (2012), „Vyvážené generické obvody bez dlouhých cest“, Diskrétní matematika, 312 (15): 2262–2271, doi:10.1016 / j.disc.2012.03.031, PAN  2926099
  12. ^ Herschel, A. S. (1862), „Sir Wm. Hamiltonova ikonická hra“, Čtvrtletní deník čisté a aplikované matematiky, 5: 305.
  13. ^ Bondy, J. A.; Murty, USA (1976), Teorie grafů s aplikacemi, Severní Holandsko, s. 53, PAN  0411988

externí odkazy