WikiDer > ЕҢ ҮЗДІК теорема

BEST theorem

Жылы графтар теориясы, бөлігі дискретті математика, ЕҢ ҮЗДІК теорема санына көбейтінді формуласын береді Эйлерия тізбектері жылы бағытталған (бағдарланған) графиктер. Бұл атау оны ашқан адамдар атауларының қысқартылған атауы: де Bruijn, ван Аарденне-Ehrenfest, Sмит және Тutte.

Дәл мәлімдеме

Келіңіздер G = (V, E) бағытталған график болуы керек. Эйлерия тізбегі дегеніміз - әр шетіне дәл бір рет келетін бағытталған тұйық жол. 1736 жылы, Эйлер деп көрсетті G егер бар болса, онда Эйлерия тізбегі бар G болып табылады байланысты және дәреже тең жоғары дәреже әр шыңда. Бұл жағдайда G Эйлериан деп аталады. Біз шыңның дәрежесін белгілейміз v градус бойынша (v).

ЕҢ ҮЗДІК теоремада ec (G) Эйлер графикасындағы Эйлер тізбектерінің G формула бойынша берілген

Мұнда тw(G) саны болып табылады ағаш отырғызу, олар ағаштар бекітілген шыңда тамырға бағытталған w жылы G. Нөмір тw(G) ретінде есептелуі мүмкін анықтауышнұсқасы бойынша матрица ағашының теоремасы бағытталған графиктер үшін. Бұл Эйлериандық графиктердің қасиеті тv(G) = тw(G) әрбір екі шың үшін v және w қосылған эвлер графикасында G.

Қолданбалар

ЕҢ жақсы теорема бағытталған графиктердегі Эйлериан тізбектерінің санын есептеуге болатындығын көрсетеді көпмүшелік уақыт, проблема # P-аяқталды бағытталмаған графиктер үшін.[1] Ол сондай-ақ Эйлериан тізбектерін асимптотикалық санауда қолданылады толық және толық екі жақты графиктер.[2][3]

Тарих

ЕҢ ҮЗДІК теорема алғаш рет осы формада ван Аарденн-Эренфест пен де Бруйеннің (1951) қағазына «дәлелдемемен толықтырылған жазбада» айтылды. Бастапқы дәлел болды биективті және жалпылама де Брюйнен тізбегі. Бұл Смит пен Тьюттің (1941) бұрынғы нәтижесінің вариациясы.

Ескертулер

  1. ^ Брайтвелл және Винклер, "Эйлериялық тізбектерді санау туралы ескерту«, CDAM зерттеу есебі LSE-CDAM-2004-12, 2004 ж.
  2. ^ Брендан Маккей және Роберт В. Робинсон, Толық графикте эвлерия тізбектерін асимптотикалық санау, Комбинаторика, 10 (1995), жоқ. 4, 367–377.
  3. ^ М.И. Исаев, Толық екі жақты графиктегі Эйлериан тізбектерінің асимптотикалық саны Мұрағатталды 2010-04-15 сағ Wayback Machine (in.) Орыс), Proc. MFTI 52-ші конференциясы (2009 ж.), Мәскеу.

Әдебиеттер тізімі

  • Эйлер, Л. (1736), «Geometriam situs pertinentis проблемалары», Commentarii Academiae Scientiarum Petropolitanae (латын тілінде), 8: 128–140.
  • Тутте, В. Т.; Смит, C. A. B. (1941), «4 дәрежелі желідегі бір жолды жолдарда», Американдық математикалық айлық, 48: 233–237, дои:10.2307/2302716, JSTOR 2302716.
  • ван Аарденн-Эренфест, Т.; де Брюйн, Н.Г. (1951), «Бағдарланған сызықтық графиктердегі тізбектер мен ағаштар», Саймон Стевин, 28: 203–217.
  • Тутте, В. Т. (1984), Графикалық теория, Рединг, Массачусетс: Аддисон-Уэсли.
  • Стэнли, Ричард П. (1999), Санақтық комбинаторика, Т. 2, Кембридж университетінің баспасы, ISBN 0-521-56069-1.
  • Айгер, Мартин (2007), Санақ курсы, Математика бойынша магистратура мәтіндері, 238, Springer, ISBN 3-540-39032-4.