Пусть - граф с множеством вершин, состоящим из всевозможных упорядоченных пар , где . Вершины ( ) и ( ) смежны в , если и . Применив критерий Вагнера, доказать, что граф непланарен.

Добавлена: 28.04.2026
Обновлена: 28.04.2026
Предмет: Геометрия
Автор: Кэмп

#Дискретная математика
#Теория графов

Пусть - граф с множеством вершин, состоящим из всевозможных упорядоченных пар , где . Вершины ( ) и ( ) смежны в , если и . Применив критерий Вагнера, доказать, что граф непланарен.

Условие:

Пусть $G$ - граф с множеством вершин, состоящим из всевозможных упорядоченных пар $(i, j)$ , где $i, j \in\{0,1,2\}$ . Вершины ( $i_{1}, j_{1}$ ) и ( $i_{2}, j_{2}$ ) смежны в $G$ , если $i_{1} \neq i_{2}$ и $j_{1} \neq j_{2}$ . Применив критерий Вагнера, доказать, что граф $G$ непланарен.

Решение:

Ниже приведено пошаговое рассуждение, приводящее к выводу, что граф G непланарен (то есть не может быть изображён на плоскости без пересечений рёбер). Мы будем применять критерий Вагнера, который утверждает, что если граф содержит в качестве минора граф K₃,₃ или K₅, то он непланарен.

Определим граф G. Его вершинами являются все упорядоченные пары (i, j), где i, j ∈ {0, 1, 2} (всего 9 вершин). Две вершины (i₁, j₁) и (i₂, j₂) смежны тогда и только тогда, когда i₁ ≠ i₂ и j₁ ≠ j₂.
Обратите внимание, что условие смежности означает: если две вершины “принадлежат” о...