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

В теории графов , части дискретной математики , теорема BEST для количества эйлеровых цепей в ориентированных графах дает формулу произведения . Название является аббревиатурой имен людей, его открывших: Н.Г. де Брейна , Татьяны Эренфест , Седрика Смита и В.Т. Тутте .

Точное утверждение

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

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

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

Здесь t _w ( G ) — количество древообразий , представляющих собой деревья, к корню в фиксированной вершине w в G. направленные Число t _w (G) можно вычислить как определитель по версии теоремы о матричном дереве для ориентированных графов. Свойством эйлеровых графов является то, что v ₍ G ) = t _w ( G ) для каждых двух вершин v и w в связном эйлеровом графе G. t

Приложения

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

История

Теорема BEST принадлежит Аарденне-Эренфесту и де Брёйну.(1951), §6, Теорема 6.Их доказательство биективно и обобщает последовательности де Брейна . В «примечании, добавленном в доказательство», они ссылаются на более ранний результат Смита и Тутта (1941), который доказывает формулу для графов с deg(v)=2 в каждой вершине.

Ссылки

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