Примеры решения похожих задач в прикрепленном файле. Оформить также как файле.
- 1)Постройте граф, двойственный по отношению к заданному, представленному множеством (набором) ребер. В фигурных скобках указаны пары чисел. Это номера вершин, соединенных ребрами. Для двойственного графа определите число ребер, число вершин и число граней.
{{1,2}, {1,8}, {2,3}, {2,4}, {3,4}, {3,7}, {4,5}, {5,6}, {6,7}, {6,8}, {7,8}}.
- 2)Найдите все простые цепи, соединяющие вершины 1 и 6 графа. В фигурных скобках указаны пары чисел. Это номера вершин, соединенных ребрами. Для самоконтроля укажите число простых цепей, содержащих два ребра; три ребра; четыре ребра; пять ребер.
{{1,2}, {1,3}, {1,5}, {2,3}, {2,4}, {2,6}, {3,4}, {3,5}, {4,6}, {5,6}}.
- 3)По заданному коду дерева постройте его графическое изображение методом Пруфера. Для самоконтроля укажите номера вершин простой цепи, соединяющей вершины 3 и 4. Вершину 3 считать началом простой цепи, вершину 4 – ее концом. В устройство вводите всю простую цепь, начиная с номера 3 и кончая номером 4. Кроме того, укажите число ребер, соединяющих вершины 1 и 9.
(3, 3, 6, 8, 7, 7, 7, 7)