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

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

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

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