Решение задач по комбинаторике
В некотором ориентированном графе без изолированных вершин нашёлся эйлеров цикл. Выберите все условия, которые заведомо не могут выполняться в этом графе. В графе 17 вершин и 16 рёбер. В графе 15 вершин и 16 рёбер. В графе 20 вершин, между каждыми двумя проведено одно ребро. В графе 25 вершин, между каждыми двумя проведено одно ребро. Из одной вершины выходит 10 рёбер, а в другую входит 20 рёбер. Из одной вершины выходит 20 рёбер и в неё входит 20 рёбер. Из какой-то вершины нельзя попасть в другую, двигаясь по рёбрам. В графе 3 компоненты сильной связности. Буду очень благодарна
Всего 15 вершин и 16 ребер. Это невозможно, поскольку эйлеров цикл требует, чтобы граф имел четное количество вершин и ребер.
Всего вершин 20, и между каждой парой вершин есть только одно ребро. Это невозможно, поскольку эйлеров цикл требует, чтобы граф имел как минимум два ребра между каждой парой вершин.
Всего вершин 25, и между каждой парой вершин есть только одно ребро. Это невозможно, поскольку эйлеров цикл требует, чтобы граф имел как минимум два ребра между каждой парой вершин.
Имеется вершина, у которой 10 входящих и 20 исходящих ребер. Это невозможно, поскольку эйлеров цикл требует, чтобы вершина имела четную степень.
Имеется вершина, у которой 20 входящих и 20 исходящих ребер. Это невозможно, поскольку эйлеров цикл требует, чтобы вершина имела четную степень.
Невозможно достичь другой вершины, следуя по ребрам из данной вершины. Это нарушает определение эйлерова цикла, которое требует, чтобы каждую вершину можно было посетить ровно один раз.
Следовательно, единственное возможное условие, которому может удовлетворять граф с эйлеровым циклом, это:
Всего 17 вершин и 16 ребер. Это возможно, и примером такого графа является цикл на 17 вершинах.