Kromatikus polinom

A matematika , különösen a gráfelmélet , a kromatikus polinomja egy gráf egy polinomiális függvény , amely a számos különböző colorations egy gráf, mint számának függvényében az engedélyezett színekben. Ezt először 1912-ben síkgráfok , a George David Birkhoff , aki igyekezett bebizonyítani a négy szín tétel .

Ennek a polinomnak a gyökerei esetében az összes pozitív vagy nulla egész szám szigorúan kisebb, mint a grafikon kromatikus száma , és bizonyos fokig a grafikon sorrendje .

A gráf kromatikus polinomja invariáns, vagyis csak a szerkezetétől függő és a jelölésétől független tulajdonság. Más szavakkal, két izomorf gráfnak ugyanaz a kromatikus polinomja lesz.

A kromatikailag ekvivalens kifejezést ugyanazon kromatikus polinommal rendelkező gráfok jelölésére használjuk. Ezzel szemben a kromatikusan egyedi gráfot annak kromatikus polinomja határozza meg.

Meghatározás

Legyen G egy olyan gráf, amelynek n csúcsa van. Kiválasztása száma colorations csúcsok G a k színek (különálló), kromatikus polinomja G , úgy definiáljuk, mint az egyedüli interpoláló polinom foka n olyan, hogy az összes K a , van . Különösen minden olyan gráf esetében, amelynek egynél több éle van, pontosabban a g kromatikus száma a legkisebb egész szám, amelynek nem gyöke van . ${\ displaystyle c_ {G} (k)}$ ${\ displaystyle P_ {G}}$ ${\ displaystyle 0 \ leq k \ leq n}$ ${\ displaystyle P_ {G} (k) = c_ {G} (k)}$ ${\ displaystyle P_ {G} (0) = P_ {G} (1) = 0}$ ${\ displaystyle P_ {G}}$

A tétel az érdeklődés: minden éle e a grafikon G , ahol Ge a gráf G nélkül szélén e , és Ge a grafikon kapott szerződő szélén e a G . ${\ displaystyle P_ {G} (k) = P_ {Ge} (k) -P_ {Ge} (k)}$

Ennek a tételnek a következményét állította George David Birkhoff 1912-ben: Az n csomópontú G gráf esetében n fokú monikus polinom (azaz polinom, ezért az n fokú tag együtthatója egyenlő 1), állandó nulla kifejezés, és amelynek együtthatói előjelenként váltakoznak. ${\ displaystyle P_ {G} (k)}$

Példák

Példák kromatikus polinomokra

Háromszög $K_ {3}$	${\ displaystyle t (t-1) (t-2)}$
Teljes grafikon $K_n$	${\ displaystyle t (t-1) (t-2) \ pontok (t- (n-1))}$
Fa és felsők $nem$	${\ displaystyle t (t-1) ^ {n-1}}$
Ciklusdiagram $C_ {n}$	${\ displaystyle (t-1) ^ {n} + (- 1) ^ {n} (t-1)}$
Petersen grafikon	${\ displaystyle t (t-1) (t-2) (t ^ {7} -12t ^ {6} + 67t ^ {5} -230t ^ {4} + 529t ^ {3} -814t ^ {2} + 775t-352)}$
Singleton grafikon	$t$

A gyémántgráf kromatikusan egyedülálló: ez az egyetlen gráf , amelynek kromatikus polinomja van. ${\ displaystyle (x-2) ^ {2} (x-1) x}$
Két olyan grafikon van, amely kromatikusan egyenértékű a bika gráfjával . Az egyik a sáska gráf .

Értékelés és referencia

(in) GD Birkhoff , " Meghatározó képlet a térkép színezésének módjaihoz " , Ann. Math. , vol. 14,1912, P. 42-46

Külső linkek

(en) Eric W. Weisstein , „ Kromatikus polinom ” a MathWorld- on
en) " Kromatikus polinom " , a PlanetMath- on
(en) A Tutte, a Chromatic és az Flow polinomok kiszámításának kódja : Gary Haggard, David J. Pearce és Gordon Royle
( fr ) A Lemma hallgatólagosan a Will Hunting című filmben szerepel