Сколько существует различных графов на 5 вершинах, у которых есть эйлеров цикл?
«Сколько существует различных графов на 5 вершинах, у которых есть эйлеров цикл?»
- Информатика
Условие:
Сколько существует различных графов на 5 вершинах, у которых есть эйлеров цикл?
Решение:
Граф эйлеров он связный и все степени четны.
В нашем случае из этого следует, что степень каждой вершины будет либо 2 либо 4 (0 быть не может, т.к. нет изолированных вершин).
Если двух графах разное количество вершин степени 4, то они не могут быть изоморфны, поэтому можно отдельно посчитать количество графов для каждого количества.
Если в графе нет вершин степени 4, то все степени равны 2. Существует единственный связный граф на 5 вершинах с таким свойством.
Рассмотрим эйлеров цикл в этом графе. Поскольку степени всех вершин равны 2, этот цикл автоматически будет простым (иначе степень вершины, ...
Похожие задачи
Не нашел нужную задачу?
Воспользуйся поиском
AI помощники
Выбери предмет
S
А
Б
В
Г
И
К
М
П
- Правоохранительные органы
- Пожарная безопасность
- Парикмахерское искусство
- Природообустройство и водопользование
- Почвоведение
- Приборостроение и оптотехника
- Промышленный маркетинг и менеджмент
- Производственный маркетинг и менеджмент
- Процессы и аппараты
- Программирование
- Право и юриспруденция
- Психология
- Политология
- Педагогика
С
Т
- Трудовое право
- Теория государства и права (ТГП)
- Таможенное право
- Теория игр
- Теория вероятностей
- Теоретическая механика
- Теория управления
- Технология продовольственных продуктов и товаров
- Технологические машины и оборудование
- Теплоэнергетика и теплотехника
- Туризм
- Товароведение
- Таможенное дело
- Торговое дело
- Теория машин и механизмов
- Транспортные средства
Ф
Э