Grafpolynom

I matematik är ett grafpolynom en grafinvariant vars värden är polynom . Invarianter av denna typ studeras i algebraisk grafteori . Viktiga grafpolynom inkluderar:

• Det karakteristiska polynomet , baserat på grafens närliggande matris .
• Det kromatiska polynomet , ett polynom vars värden vid heltalsargument ger antalet färger i grafen med så många färger.
• Det dikromatiska polynomet , en 2-variabel generalisering av det kromatiska polynomet
• Flödespolynomet , ett polynom vars värden vid heltalsargument ger antalet nollflöden med heltalsflöden modulo argumentet .
• (inversen av) Ihara zeta-funktionen , definierad som en produkt av binomiska termer som motsvarar vissa slutna promenader i en graf.
• Martin-polynomet, som används av Pierre Martin för att studera Euler-turer
• De matchande polynomen , flera olika polynom definierade som genereringsfunktionen för matchningarna av en graf.
• Tillförlitlighetspolynomet , ett polynom som beskriver sannolikheten att förbli ansluten efter oberoende kantfel
• Tutte -polynomet , ett polynom i två variabler som kan definieras (efter en liten förändring av variabler) som den genererande funktionen av antalet anslutna komponenter av inducerade subgrafer i den givna grafen, parametriserad av antalet hörn i subgrafen.

Se även

• Knutpolynom