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
Jegyzetek
Kategória:Polinomok Kategória:Gráfinvariánsok