Frucht'un grafiği

meyve grafiği
Frucht'un grafiği

köşe sayısı	12
Kenar sayısı	18
Derece dağılımı	3- düzenli
Işın	3
Çap	4
ağ	3
otomorfizmler	1 ({ kimlik })
kromatik sayı	3
kromatik indeks	3
Özellikleri	Kübik Hamiltonian Düzlemsel Asimetrik

Frucht grafik olarak, bir grafik teorisi , bir 3-normal grafik 12 köşe ve 18 kenarları ile. Bu en küçük küp grafiği olan otomorfizm grubu yalnızca nötr bir madde içerir. Başka bir deyişle, asimetrik bir grafik olan üçüncü derecenin en küçük düzenli grafiğidir . İlk olarak 1939'da Robert Frucht tarafından tanımlanmıştır , dolayısıyla adı.

Özellikleri

Genel Özellikler

Frucht grafiği düzlemsel ve Hamiltonyendir . Aynı zamanda Halin grafiğinin bir durumudur .

Çapı Frucht grafik olarak, köşelerin azami eksantrisite, 4, onun bir yarıçapı , kendi noktaların en az eksantrikliği 3'tür ve örgü , En kısa uzunluğu döngüsü , bir 3- ait 3'tür tepe -bağlı graf ve 3 -kenar bağlantılı graf , yani bağlantılıdır ve bağlantısının kesilebilmesi için en az 3 köşeden veya 3 kenardan yoksun olması gerekir.

Boyama

Renk sayısı Frucht grafiğin bir kenarı ile bağlı iki köşe her zaman farklı renklerde böylece 3 renk ile renk mümkün olduğunu söylemek 3'tür, ancak bu sayı çok az. Grafiğin geçerli bir 2 renklendirmesi yok.

Renk indeksi Frucht grafiğin 3. duyulmaktadır bir 3-boyama, aynı vertices iki kenarı gelen farklı renklerin her zaman olduğu gibi, grafiğin kenarlarının. Bu sayı minimumdur.

Bir grafiğin farklı renklerini saymak mümkündür. Bu, izin verilen renk sayısına bağlı olarak bir işlev verir. Bu fonksiyon polinomdur ve grafiğin kromatik polinomu olarak nitelendirilir . Bu polinomun tüm pozitif tam sayıların veya sıfırın kesinlikle 3 derece ve 12'den küçük kökleri vardır. Şuna eşittir: . ${\ displaystyle (x-2) (x-1) x (x ^ {9} -15x ^ {8} + 103x ^ {7} -428x ^ {6} + 1196x ^ {5} -2355x ^ {4} + 3311x ^ {3} -3259x ^ {2} + 2077x-663)}$

cebirsel özellikler

Otomorfizm grubu Frucht grafiğin yalnızca nötr bir madde içerir. Bu nedenle 1. derecedendir. Bu, Frucht grafiğini asimetrik bir grafik yapar .

Karakteristik polinomu ve bitişiklik matrisi Frucht grafik sahiptir: . ${\ displaystyle (x-3) (x-2) x (x + 1) (x + 2) (x ^ {3} + x ^ {2} -2x-1) (x ^ {4} + x ^ {3} -6x ^ {2} -5x + 4)}$

Galeri

Frucht grafiği düzlemseldir
Frucht grafiği Hamiltonyendir
Frucht grafiği 3 renklendirmeyi kabul ediyor

Şuna da bakın:

Dahili bağlantılar

Grafik teorisi

Referanslar

(tr) Weisstein, Eric W "Frucht Graph." MathWorld'den - Bir Wolfram Web Kaynağı
(içinde) Skiena S. Ayrık Matematik Uygulaması: Mathematica ile Kombinatorik ve Grafik Teorisi. Okuma, MA: Addison-Wesley, 1990
(de) "Herstellung von Graphen mit vorgegebener soyut Gruppe." Komp. Matematik. 6, 239-250, 1939