Определить, является ли данный граф: планарным или плоским графом (обосновать ответ и выполнить обратное преобразование); двудольным графом (обосновать ответ и, если необходимо, то достроить до двудольного графа);

25 июля 2024
Высшая математика

Условие:

Определить, является ли данный граф:

планарным или плоским графом (обосновать ответ и выполнить обратное преобразование);
двудольным графом (обосновать ответ и, если необходимо, то достроить до двудольного графа);
деревом (обосновать ответ и, в случае циклического графа, привести один из вариантов основного дерева);
псевдографом или мультиграфом, или простым графом (обосновать ответ и выполнить необходимые преобразования).

Решение:

Данный граф является плоским, поскольку все его связи пересекаются только в вершинах. Преобразуем данный граф в планарный граф:

Данный граф не является двудольным, потому что содержит циклы нечетной длины (например, 𝑥₄𝑥₅𝑥₇𝑥₄) и множество его вершин нельзя разбить на два подмножества так, чтобы никакое ребро не соединяло вершины одного и того же подмножества, то есть, чтобы не существовало ребер между вершинами одной и той же части.

Преобразуем в двудольный граф. Для этого добавим еще одну вершину 𝑥5 и заменим ребро 𝑉8 на 𝑉81 и V82. В результате д...