Для некоторого графа построено BFS-дерево с корнем . Ребро графа дереву не принадлежит. Какие из следующих соотношений могут выполняться ( обозначает расстояние между вершинами в графе)?

Правильный ответ:

• # Сколько имеется абстрактных обыкновенных графов с 5 вершинами и 3 ребрами?
• # Сколько имеется абстрактных обыкновенных графов с набором степеней (2, 2, 4, 4, 5, 5)?
• # В полном графе с множеством вершин {1, 2, 3, 4, 5, 6} каждое ребро ориентировано от вершины с меньшим номером к вершине с большим. Ребро , , имеет пропускную способность i . Какова наибольшая величина потока от вершины 1 к вершине 6?
• # Какие из следующих утверждений верны?
• # Какое наименьшее число ребер нужно добавить к графу K3,5, чтобы получился граф, в котором есть эйлеров цикл?