ЛУЧШАЯ теорема - BEST theorem

В теория графов, часть дискретная математика, то ЛУЧШАЯ теорема дает формулу продукта для количества Схемы Эйлера в направленный (ориентированный) графики. Название является аббревиатурой от имен людей, которые его открыли: де BRuijn, ван АарденнEхренфест, SМиф и Тпроизносить.

Точное заявление

Позволять грамм = (V, E) - ориентированный граф. Схема Эйлера - это направленный замкнутый путь, который посещает каждое ребро ровно один раз. В 1736 г. Эйлер показало, что грамм имеет эйлеров контур тогда и только тогда, когда грамм является связаны и степень равно превосходить в каждой вершине. В этом случае грамм называется эйлеровым. Обозначим степень вершины v по deg (v).

Теорема BEST утверждает, что число ec (грамм) эйлеровых схем в связном эйлеровом графе грамм дается формулой

${\displaystyle \operatorname {ec} (G)=t_{w}(G)\prod _{v\in V}{\bigl (}\deg(v)-1{\bigr )}!.}$

Здесь т_ш(грамм) - количество древесные растения, которые деревья направлен к корню в фиксированной вершине ш в грамм. Номер т_ш(ГРАММ) можно вычислить как детерминант, по версии теорема о матричном дереве для ориентированных графов. Свойство эйлеровых графов состоит в том, что т_v(грамм) = т_ш(грамм) для каждых двух вершин v и ш в связном эйлеровом графе грамм.

Приложения

Теорема BEST показывает, что количество эйлеровых схем в ориентированных графах может быть вычислено за полиномиальное время, проблема, которая # P-complete для неориентированных графов.^[1] Он также используется в асимптотическом перечислении эйлеровых схем полный и полные двудольные графы.^[2][3]

История

Теорема BEST была впервые сформулирована в такой форме в «примечании, добавленном в доказательство» к статье ван Аарденна-Эренфеста и де Брюйна (1951). Первоначальное доказательство было биективный и обобщил последовательности де Брейна. Это вариант более раннего результата Смита и Тутте (1941).

Примечания

1. Брайтвелл и Винклер, "Замечание о счёте эйлеровых схем ", Отчет об исследовании CDAM LSE-CDAM-2004-12, 2004.
2. Брендан МакКей и Роберт В. Робинсон, Асимптотическое перечисление эйлеровых схем в полном графе, Комбинаторика, 10 (1995), нет. 4, 367–377.
3. М.И. Исаев, Асимптотическое число эйлеровых схем в полных двудольных графах В архиве 2010-04-15 на Wayback Machine (в русский ), Proc. 52-я конференция МФТИ (2009), Москва.

Рекомендации

• Эйлер, Л. (1736), "Solutio problematis ad geometriam situs pertinentis", Commentarii Academiae Scientiarum Petropolitanae (на латыни), 8: 128–140.
• Тутте, В. Т.; Смит, К.А.Б. (1941), «Об уникурсальных путях в сети 4 степени», Американский математический ежемесячный журнал, 48: 233–237, Дои:10.2307/2302716, JSTOR  2302716.
• ван Аарденне-Эренфест, Т.; де Брёйн, Н.Г. (1951), «Схемы и деревья в ориентированных линейных графах», Саймон Стевин, 28: 203–217.
• Тутте, В. Т. (1984), Теория графов, Ридинг, Массачусетс: Эддисон-Уэсли.
• Стэнли, Ричард П. (1999), Перечислительная комбинаторика, Vol. 2, Издательство Кембриджского университета, ISBN  0-521-56069-1.
• Айгнер, Мартин (2007), Курс перечисления, Тексты для выпускников по математике, 238, Спрингер, ISBN  3-540-39032-4.