Аннотация:
Эйлеровым циклом графа называется замкнутый путь по ребрам графа, использующей все ребра ровно один раз. BEST-теорема (названная согласно инициалам авторов*B*ruijn, Aardenne-*E*hhrenfest, *S*mith, *T*utte) позволяет связать число различный эйлеровых циклов с количеством помеченных остовных деревьев. Согласно матричной теореме о деревьях перечисление остовных деревьев сводится к подсчету минора специальной матрицы, ассоциированной с графом. В докладе планируется подробно обсудить этот подход для случаев ориентированного и неориентированного графа, а также доказать вышеупомянутые теоремы (и вариации). Доклад основан на работах [1] и [2].
|
