Аннотация:
Получены явные формулы и асимптотика для ряда классов помеченных графов без мостов: кактусов, графов блоков, полноблочно-кактусных графов и последовательно-параллельных графов. Доказано, что при равномерном распределении вероятностей почти все графы из рассматриваемых классов имеют мосты.
Ключевые слова:перечисление, помеченный граф, $k$-циклический граф, блок, мост, граф без мостов, эйлеров граф, последовательно-параллельный граф, асимптотика, случайный граф.
Полный текст:
PDF файл (223 kB)