Задание 3.

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

- планарным или плоским графом (обосновать ответ и выполнить обратное преобразование);

- двудольным графом (обосновать ответ и, если необходимо, то достроить до двудольного графа);

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

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

Решение:

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

Х2 V4 Х3

V2 V3 V5 V6

X1V1 X4V7 X5

Данный граф не является двудольным, поскольку содержит циклы нечетной длины (например, х4-х3-х5-х4), и поэтому множество его вершин нельзя разделить на две части.

Для того, чтобы преобразовать граф в двудольный, необходимо, например, заменить ребро V3 на два ребра V3-1 и V3-2 с добавлением вершины Х2_4 и ребро V6 – на V6-1 и V6-2 с добавлением вершины Х3_5. В результате данного преобразования исходного графа все циклы в графе будут иметь четную длину, тогда множество вершин можно следующим образом разделить на две доли (1 и 2 – это номер доли):

2 1 2

Х3_5

1

Х2_4

1 2 1

Данный граф не является деревом, поскольку он содержит циклы. Приведем пример остова данного графа:

Х2 Х3

V4

V2 V3 V6