Gráfpolinom

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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.[1] 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[szerkesztés]

Fordítás[szerkeszté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.

Jegyzetek[szerkesztés]

  1. Shi, Yongtang; Dehmer, Matthias & Li, Xueliang et al. (2016), Graph Polynomials, Discrete Mathematics and Its Applications, CRC Press, ISBN 9781498755917