В графе K₅ все ребра некоторого гамильтонова цикла имеют вес 2, а все остальные ребра - вес 3. Каков будет радиус дерева, построенного для этого графа с помощью алгоритма Дейкстры?

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

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