Условие задачи
Определить, является ли данный граф:
- планарным или плоским графом (обосновать ответ и выполнить обратное преобразование);
- двудольным графом (обосновать ответ и, если необходимо, то достроить до двудольного графа);
- деревом (обосновать ответ и, в случае циклического графа, привести один из вариантов основного дерева);
- псевдографом или мультиграфом, или простым графом (обосновать ответ и выполнить необходимые преобразования).
Ответ
Данный граф является плоским, поскольку все его связи пересекаются только в вершинах. Преобразуем данный граф в планарный граф:
Данный граф не является двудольным, потому что содержит циклы нечетной длины (например, 𝑥4𝑥5𝑥7𝑥4) и множество его вершин нельзя разбить на два подмножества так, чтобы никакое ребро не соединяло вершины одного и того же подмножества, то есть, чтобы не существовало ребер между вершинами одной и той же части.
Преобразуем в двудольный граф. Для этого добавим еще одну вершину 𝑥5 и заменим ребро 𝑉8 на 𝑉81 и V82. В результате д...
Потяни
