Gráfpolinom

A matematika, azon belül a gráfelmélet területén egy gráfpolinom olyan gráfinvariáns, melynek értékei polinomok. Az ilyen jellegű invariánsokkal az algebrai gráfelmélet foglalkozik. A fontosabb gráfpolinomok közé tartoznak:

• A kromatikus polinom, melynek egész helyen vett értékei megadják a gráf adott számú színnel történő csúcsszínezéseinek számát.
• A dikromatikus polinom, a kromatikus polinom kétváltozós általánosítása
• A folyampolinom (flow polynomial), melynek egész helyen vett értékei megadják a sehol sem nulla folyamok számát egész folyamértékek modulo az argumentum mentén.
• Az Ihara-féle zéta-függvény (inverze), ami a gráf egyes zárt sétáinak megfelelő binomiális értékek szorzata
• A Martin-polinom, amit Pierre Martin vezetett be az Euler-séták tanulmányozására
• A párosítási polinomok (matching polynomials), melyek több, egy gráf párosítását generátorként használó, de különbözően definiált polinomot jelentenek.
• A megbízhatósági polinom (reliability polynomial), ami leírja annak valószínűségét, hogy a gráf független élhibák után összefüggő marad
• A Tutte-polinom egy kétváltozós polinom, ami (a változók apró módosítása után) adott gráf feszített részgráfjai független komponenseinek száma generátorfüggvényeként használható, melynek paramétere a részgráf csúcsainak száma.

Kapcsolódó szócikkek

• Csomópolinom

Fordítás

• Ez a szócikk részben vagy egészben a Graph polynomial című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.