Polynom grafu - Graph polynomial - Wikipedia

V matematice, a polynom grafu je graf neměnný jejichž hodnoty jsou polynomy. Invarianty tohoto typu jsou studovány v algebraická teorie grafů.^[1]Mezi důležité polynomy grafů patří:

• The charakteristický polynom, na základě grafů matice sousedství.
• The chromatický polynom, polynom, jehož hodnoty u celočíselných argumentů udávají počet vybarvení grafu s tolika barvami.
• The dichromatický polynom, 2-proměnná generalizace chromatického polynomu
• The tok polynomu, polynom, jehož hodnoty u celočíselných argumentů udávají počet nikde nula teče s množstvím celočíselného toku modulo argument.
• (Inverzní) Funkce Ihara zeta, definovaný jako produkt binomických výrazů odpovídajících určitým uzavřeným krokům v grafu.
• The Martinův polynom, který používal Pierre Martin ke studiu Eulerovy zájezdy
• The odpovídající polynomy, několik různých polynomů definovaných jako generující funkce z párování grafu.
• The spolehlivostní polynom, polynom, který popisuje pravděpodobnost, že zůstane připojen po selhání nezávislé hrany
• The Tutteův polynom, polynom ve dvou proměnných, které lze definovat (po malé změně proměnných) jako generující funkci počtu připojených komponent indukované podgrafy daného grafu, parametrizovaný počtem vrcholů v podgrafu.

Viz také

• Uzlový polynom

Reference

Rejstřík článků spojených se stejným názvem Tento článek obsahuje seznam souvisejících položek, které mají stejný název (nebo podobné názvy). Pokud interní odkaz nesprávně vás sem přivedl, možná budete chtít změnit odkaz tak, aby odkazoval přímo na zamýšlený článek.