Question

В посёлке 3 дома и 3 колодца. Можно ли протоптать от каждого дома к каждому колодцу тропинку так, чтобы никакие две тропинки не пересекались? Иными словами, является ли граф К3,3 пленарным?

Answer 1

Дано:

Количество домов (вершин A) = 3.

Количество колодцев (вершин B) = 3.

Количество рёбер E = 3 * 3 = 9 (от каждого дома к каждому колодцу).

Найти:

Является ли граф K3,3 пленарным (можно ли его нарисовать так, чтобы тропинки не пересекались)?

Решение:

1. Граф K3,3 — двудольный полный граф, состоящий из двух множеств по 3 вершины.

2. Согласно теореме о плоских графах, граф K3,3 является пленарным, если E ≤ 3V - 6.

3. Для графа K3,3:

   - V = 3 + 3 = 6 (всего вершин).
   - E = 9.

4. Подставим в неравенство:

9 ≤ 3 * 6 - 6.

5. Упрощаем:

9 ≤ 18 - 6.

6. Получаем:

9 ≤ 12 (верно).

Ответ:
Граф K3,3 является пленарным.