Tutte-Grothendieck invariantní - Tutte–Grothendieck invariant - Wikipedia

tento článek potřebuje další citace pro ověření. Prosím pomozte vylepšit tento článek podle přidávání citací ke spolehlivým zdrojům. Zdroj bez zdroje může být napaden a odstraněn. Najít zdroje: „Tutte – Grothendieck invariant“  – zprávy  · noviny  · knihy  · učenec  · JSTOR (Srpna 2019) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v matematika, a Tutte-Grothendieck (TG) neměnný je typ graf neměnný který uspokojí generalizované vzorec vypuštění – kontrakce. Jakékoli hodnocení Tutteův polynom by byl příkladem invariantu TG.^[1][2]

Definice

Funkce grafu F je neměnný TG, pokud:^[2]

${ displaystyle f (G) = { begin {cases} c ^ {| V (G) |} & { text {if null}} xf (G / e) & { text {if}} e { text {je smyčka}} yf (G zpětné lomítko e) & { text {if}} e { text {je kolonka nebo můstek}} af (G / e) + bf (G zpětné lomítko e) a { text {else}} end {případy}}}$

Výše G / E označuje kontrakce hran zatímco G \ E označuje smazání. Čísla C, X, y, A, b jsou parametry.

Zobecnění na matroidy

The matroid funkce F je TG, pokud:^[1]

${ displaystyle { begin {aligned} & f (M_ {1} oplus M_ {2}) = f (M_ {1}) f (M_ {2}) & f (M) = af (M / e) + bf (M zpětné lomítko e) { text {if}} e { text {není coloop nebo bridge}} end {zarovnáno}}}$

To lze ukázat F darováno:

${ displaystyle f (M) = a ^ {| E | -r (E)} b ^ {r (E)} T (M; x / a, y / b)}$

kde E je sada hran M; r je hodnostní funkce; a

${ displaystyle T (M; x, y) = součet _ {A podmnožina E (M)} (x-1) ^ {r (E) -r (A)} (y-1) ^ {| A | -r (A)}}$

je zobecnění Tutteova polynomu na matroidy.

Grothendieckova skupina

Invariant je pojmenován po Alexander Grothendieck z důvodu podobné konstrukce Grothendieckova skupina použitý v Riemann – Rochova věta. Více podrobností viz:

• Tutte, W. T. (2008). "Prsten v teorii grafů". Mathematical Proceedings of the Cambridge Philosophical Society. 43 (1): 26–40. doi:10.1017 / S0305004100023173. ISSN  0305-0041. PAN  0018406.
• Brylawski, T. H. (1972). „Tutte-Grothendieckův prsten“. Algebra Universalis. 2 (1): 375–388. doi:10.1007 / BF02945050. ISSN  0002-5240. PAN  0330004.

Reference