NEJLEPŠÍ věta - BEST theorem

v teorie grafů, část diskrétní matematika, NEJLEPŠÍ věta dává produktový vzorec pro počet Euleriánské obvody v režie (orientované) grafy. Jméno je zkratkou jmen lidí, kteří jej objevili: de Bruijn, van Aardenne-Ehrenfest, Sblázen a Tutte.

Přesné prohlášení

Nechat G = (PROTI, E) být směrovaný graf. Euleriánský obvod je směrovaná uzavřená cesta, která navštíví každou hranu přesně jednou. V roce 1736 Euler to ukázal G má Eulerianův obvod právě tehdy G je připojeno a nezávislý je rovný překonat na každém vrcholu. V tomto případě G se nazývá Eulerian. Označíme indegree vrcholu proti podle stupně (proti).

NEJLEPŠÍ věta uvádí, že číslo ec (G) Eulerianových obvodů v připojeném Eulerianově grafu G je dáno vzorcem

Tady tw(G) je počet stromové scény, což jsou stromy směřující ke kořenu v pevném vrcholu w v G. Číslo tw(G) lze vypočítat jako a určující, ve verzi věta o maticovém stromu pro směrované grafy. Je to vlastnost euleriánských grafů tproti(G) = tw(G) pro každé dva vrcholy proti a w v připojeném euleriánském grafu G.

Aplikace

NEJLEPŠÍ věta ukazuje, že lze vypočítat počet Eulerianových obvodů v směrovaných grafech polynomiální čas, což je problém # P-kompletní pro neorientované grafy.[1] Používá se také při asymptotickém výčtu Eulerianových obvodů kompletní a kompletní bipartitní grafy.[2][3]

Dějiny

NEJLEPŠÍ věta byla poprvé uvedena v této formě v „poznámce přidané jako důkaz“ k článku van Aardenne-Ehrenfest a de Bruijn (1951). Původní důkaz byl bijektivní a zobecnil de Bruijn sekvence. Jedná se o variaci na dřívější výsledek Smitha a Tutté (1941).

Poznámky

  1. ^ Brightwell a Winkler, "Poznámka k počítání Eulerianových obvodů ", Výzkumná zpráva CDAM LSE-CDAM-2004-12, 2004.
  2. ^ Brendan McKay a Robert W. Robinson, Asymptotický výčet euleriánských obvodů v úplném grafu, Combinatorica, 10 (1995), č. 5. 4, 367–377.
  3. ^ M.I. Isaev, Asymptotický počet euleriánských obvodů v kompletních bipartitních grafech Archivováno 2010-04-15 na Wayback Machine (v ruština ), Proc. 52. konference MFTI (2009), Moskva.

Reference

  • Euler, L. (1736), „Solutio problematis ad geometriam situs pertinentis“, Commentarii Academiae Scientiarum Petropolitanae (v latině), 8: 128–140.
  • Tutte, W. T.; Smith, C. A. B. (1941), „Na unicurálních cestách v síti stupně 4“, Americký matematický měsíčník, 48: 233–237, doi:10.2307/2302716, JSTOR  2302716.
  • van Aardenne-Ehrenfest, T.; de Bruijn, N. G. (1951), "Obvody a stromy v orientovaných lineárních grafech", Simon Stevin, 28: 203–217.
  • Tutte, W. T. (1984), Teorie grafů„Reading, Mass .: Addison-Wesley.
  • Stanley, Richard P. (1999), Enumerativní kombinatorika, Sv. 2, Cambridge University Press, ISBN  0-521-56069-1.
  • Aigner, Martin (2007), Kurz výčtu, Postgraduální texty z matematiky, 238Springer, ISBN  3-540-39032-4.