Pappusův graf - Pappus graph - Wikipedia

Pappusův graf
Pappusův graf.
Pojmenoval podle	Pappus Alexandrijský
Vrcholy	18
Hrany	27
Poloměr	4
Průměr	4
Obvod	6
Automorfismy	216
Chromatické číslo	2
Chromatický index	3
Tloušťka knihy	3
Číslo fronty	2
Vlastnosti	Bipartitní Symetrický Přechodná vzdálenost Vzdálenost-pravidelná Krychlový Hamiltonian
Tabulka grafů a parametrů

V matematický pole teorie grafů, Pappusův graf je bipartitní 3-pravidelný neorientovaný graf s 18 vrcholy a 27 hranami, vytvořenými jako Leviho graf z Konfigurace Pappus.^[1] Je pojmenován po Pappus Alexandrijský, starověký Řecký matematik o kterém se předpokládá, že objevil „šestihrannou větu“ popisující konfiguraci Pappusu. Všechny krychlový vzdálenost-pravidelné grafy jsou známy; Pappusův graf je jedním ze 13 takových grafů.^[2]

Graf Pappus má přímé číslo křížení 5 a je nejmenší kubický graf s tímto křížením (sekvence A110507 v OEIS ). Má to obvod 6, průměr 4, poloměr 4, chromatické číslo 2, chromatický index 3 a oba jsou 3připojen k vrcholu a 3-připojeno k okraji. Má to tloušťka knihy 3 a číslo fronty 2.^[3]

Graf Pappus má a chromatický polynom rovná: ${ displaystyle (x-1) x (x ^ {16} -26x ^ ​​{15} + 325x ^ {14} -2600x ^ {13} + 14950x ^ {12} -65762x ^ {11} +}$${ displaystyle 229852x ^ {10} -653966x ^ {9} + 1537363x ^ {8} -3008720x ^ {7} + 4904386x ^ {6} -}$${ displaystyle 6609926x ^ ​​{5} + 7238770x ^ {4} -6236975x ^ {3} + 3989074x ^ {2} -1690406x + 356509)}$.

Název „Pappusův graf“ se také používá k označení souvisejícího grafu devíti vrcholů,^[4] s vrcholem pro každý bod konfigurace Pappus a hranou pro každou dvojici bodů na stejné linii; tento graf devíti vrcholů je 6 pravidelný, je doplňkový graf spojení tří disjunktních trojúhelníkové grafy, a je kompletní trojstranný graf K_3,3,3. První Pappusův graf lze vložit do torusu a vytvořit tak vlastníPetrie dual běžná mapa s devíti šestihrannými plochami; druhý, aby vytvořil pravidelnou mapu s 18 trojúhelníkovými plochami. Dvě pravidelné toroidní mapy jsou navzájem dvojí.

Algebraické vlastnosti

Skupina automorfismu Pappusova grafu je skupina řádu 216. Působí přechodně na vrcholy, na okraje a na oblouky grafu. Graf Pappus je tedy a symetrický graf. Má automatorfismy, které berou jakýkoli vrchol na jakýkoli jiný vrchol a jakoukoli hranu na jakoukoli jinou hranu. Podle Podporovat sčítání lidu, Pappusův graf, označovaný jako F018A, je jediný kubický symetrický graf na 18 vrcholech.^[5][6]

The charakteristický polynom grafu Pappus je ${ displaystyle (x-3) x ^ {4} (x + 3) (x ^ {2} -3) ^ {6}}$. Je to jediný graf s tímto charakteristickým polynomem, což z něj dělá graf určený svým spektrem.

Galerie

• 

  Pappusův graf barevně zvýrazňuje různé cykly.

• 

  The chromatický index grafu Pappus je 3.

• 

  The chromatické číslo grafu Pappus je 2.

• 

  Pappusův graf vložený do torusu jako běžná mapa s devíti šestiúhelníkovými plochami.

Reference