Narvon grafigi - Ladder graph

Narvon grafigi
L8.svg narvon grafigi
Narvon grafigi L8.
Vertices2n
Qirralar3n-2
Xromatik raqam2
Xromatik indeks3 uchun n> 2
2 uchun n = 2
1 uchun n = 1
XususiyatlariBirlik masofasi
Hamiltoniyalik
Planar
Ikki tomonlama
NotationLn
Grafiklar va parametrlar jadvali

In matematik maydoni grafik nazariyasi, narvon grafigi Ln a planar yo'naltirilmagan grafik bilan 2n tepaliklar va 3n-2 qirralar.[1]

Narvon grafigini quyidagicha olish mumkin Dekart mahsuloti ikkitadan yo'l grafikalari, ulardan bittasi faqat bitta chekkaga ega: Ln,1 = Pn × P2.[2][3]

Xususiyatlari

Qurilish bo'yicha L narvon grafigin uchun izomorfik panjara grafigi G2,n va bilan narvonga o'xshaydi n zinapoyalar. Bu Hamiltoniyalik atrofi 4 bilan (agar n> 1) va kromatik indeks 3 (agar n> 2).

The xromatik raqam narvon grafigi 2 va uning xromatik polinom bu .

Narvon grafikalari L1, L2, L3, L4 va L5.

Narvon narvon grafigi

Ba'zan "narvon grafigi" atamasi n × P2 zinapoyalar grafigi, bu grafik birlashmasi n yo'l grafasining nusxalari P2.

Narvon grafigi LR1, LR2, LR3, LR4va LR5.

Dairesel narvon grafigi

Asosiy maqola: Prizma grafigi

The dairesel narvon grafigi CLn a-da to'rtta 2 darajali tepaliklarni bog'lash orqali konstruktivdir To'g'riga yo'l yoki uzunlik tsiklining dekart ko'paytmasi bo'yicha n≥3 va chekka.[4]Ramzlarda, CLn = Cn × P2. Unda bor 2n tugunlari va 3n narvon grafasi singari, shunday bo'ladi ulangan, planar va Hamiltoniyalik, lekin shunday ikki tomonlama agar va faqat agar n hatto.

Dairesel narvon grafigi quyidagilar ko'p qirrali grafikalar prizmalaridan iborat, shuning uchun ular ko'proq nomlanadi prizma grafikalar.

Dairesel narvon grafikalari:

Uchburchak prizmatik grafik.png
CL3		Kubik grafik.png
CL4		Besh burchakli prizmatik grafik.png
CL5		Olti burchakli prizmatik grafik.png
CL6		Geptagonal prizmatik grafik.png
CL7		Sakkizburchak prizmatik grafik.png
CL8

Mobius narvoni

Asosiy maqola: Mobius narvoni

To'rtta 2 darajali tepaliklarni ulash o'zaro faoliyat yaratadi kubik grafik Mobius zinapoyasi deb nomlangan.

Mobius narvonining ikki ko'rinishi M16 .

Adabiyotlar

  1. ^ Vayshteyn, Erik V. "Narvon grafigi". MathWorld.
  2. ^ Xosoya, H. va Xarari, F. "Uch devor grafikasining mos keladigan xususiyatlari to'g'risida". J. Matematik. Kimyoviy. 12, 211-218, 1993 yil.
  3. ^ Noy, M. va Ribo, A. "Graflarning rekursiv konstruktiv oilalari". Adv. Qo'llash. Matematika. 32, 350-363, 2004 yil.
  4. ^ Chen, Yichao; Gross, Jonathan L.; Mansur, Toufik (2013 yil sentyabr). "Dairesel narvonlarning umumiy joylashtirilishi". Grafika nazariyasi jurnali. 74 (1): 32–57. CiteSeerX  10.1.1.297.2183. doi:10.1002 / jgt.21690.