Graficul cu prisme

În teoria grafurilor, un grafic prism este un grafic care are una dintre prisme ca schelet.

Exemple

Graficele individuale pot fi denumite în funcție de corpurile asociate:


Y 3 = GP(3,1)
Y 4 \ u003d Q 3 \u003d GP (4,1)
Y 5 = GP(5,1)
Y 6 = GP(6,1)
Y 7 = GP(7,1)
Y8 = GP (8,1)

Deși poligoanele stelate geometric servesc și ca fețe ale unei alte secvențe de politopi prismatici (auto-intersectați și neconvexe), graficele acestor prisme stelate sunt izomorfe cu graficele prismatice și nu formează o secvență separată de grafice.

Clădire

Graficele prisme sunt exemple de grafice Petersen generalizate cu parametrii GP( n ,1). Graficele pot fi, de asemenea, formate ca un produs direct al unui ciclu și al unei muchii unitare [1] .

La fel ca multe grafuri tranzitive de vârf, grafurile prismatice pot fi construite ca grafuri Cayley . Grupul diedric de ordinul n este grupul de simetrie al unui n -gon regulat în plan. Acționează asupra n - gonului prin rotații și reflexii. Un grup poate fi generat de două elemente, o rotație printr-un unghi și o reflexie, iar graficul Cayley al acestui grup cu acest grup generator este un grafic prismă. În mod abstract, grupul are o sarcină (unde r este o rotație și f este o reflexie) iar graficul Cayley are r și f (sau r , r -1 și f ) ca generatori [1]

Graficul unei prisme n -gonale cu n impar poate fi construit ca un grafic circular , dar această construcție nu funcționează pentru valorile pare ale lui n [1] .

Proprietăți

Graficul unei prisme n -gonale are 2n vârfuri și 3n muchii. Graficele sunt grafice cubice obișnuite . Deoarece o prismă are simetrii care duc orice vârf la oricare altul, graficele prisme sunt grafice tranzitive la vârf . Fiind grafuri poliedrice , aceste grafuri sunt, de asemenea, grafuri plane legate de vârfuri 3 . Orice grafic prismă are un ciclu hamiltonian [2] .

Dintre toate graficele cubice dublu conectate , graficele cu prismă au, până la un factor constant, cel mai mare număr posibil de 1-descompuneri ale graficului . O descompunere 1 este o partiție a muchiei graficului setată în trei potriviri perfecte sau, echivalent, o colorare a muchiei în trei culori a graficului. Orice graf cubic bi-conectat cu n vârfuri are O (2 n /2 ) 1-descompuneri, iar un graf cu prismă are Ω (2 n /2 ) 1-descompoziții [3] .

Numărul de arbori de întindere a graficului unei prisme n -gonale este dat de formula [4] .

Pentru n = 3, 4, 5, ... aceste numere sunt egale

78, 388, 1810, 8106, 35294, ...

Graficele de prisme n -gonale pentru n par sunt cuburi parțiale . Ele formează una dintre puținele familii infinite cunoscute de grafice cubice parțiale cubice și sunt (cu patru excepții) singurele cuburi parțiale cubice tranzitive la vârf [5] .

Graficul cu prismă pentagonală este unul dintre minorele interzise pentru graficele cu lățimea arborelui trei [6] . Prismele triunghiulare și graficele cubului au lățimea copacului exact trei, dar toate prismele mai mari au lățimea copacului patru.

Grafice înrudite

Alte familii infinite de grafice poliedrice bazate în mod similar pe poliedre de bază obișnuite includ grafice antiprismă și roți grafice piramidale ). Alte grafice poliedrice vertex-tranzitive sunt graficele arhimediene .

Dacă două cicluri ale unui grafic prismatic sunt rupte prin eliminarea unei muchii în același loc în ambele cicluri, obținem o scară . Dacă două muchii îndepărtate sunt înlocuite cu două muchii care se încrucișează, obținem un grafic neplanar „ Scara Möbius ” [7] .

Note

  1. ↑ 1 2 3 Weisstein, Eric W. Prism graph  (engleză) pe site-ul Wolfram MathWorld .
  2. ↑ Read, Wilson, 2004 , p. 261, 270.
  3. ↑ Eppstein, 2013 . Eppstein îi atribuie lui Greg Kuperberg , care a făcut această observație în mod privat, observația conform căreia graficele prisme au un număr aproape maxim de 1-descompunere.
  4. ↑ Jagers, 1988 , p. 151–154.
  5. ↑ Mark, 2015 .
  6. ↑ Arnborg, Proskurowski, Corneil, 1990 , p. 1–19.
  7. ↑ Guy, Harary, 1967 , p. 493–496.

Literatură