Question

Задание:
1. Постройте планарный граф с а) 6; б) 7; в) 8; г) 9; вершинами так, чтобы некоторые его ребра пересекались.
2. Постройте плоский граф, соответствующий графу из предыдущего задания.
3. Постройте геометрически двойственный граф к графу из задания 2.
4. Покажите, что К5 не обладает абстрактно двойственными графами.

Answer 1

Привет! Я рад выступить в роли твоего школьного учителя и помочь тебе с этим заданием.

1. Построим планарный граф с разным количеством вершин, чтобы некоторые его ребра пересекались:
- Для а) 6 вершин можно нарисовать следующий граф:
A --- B
| /|
| / |
| / |
| / |
C --- D
|/ |
E --- F
Здесь ребро AC пересекается с ребром BE.

- Для б) 7 вершин:
A --- B
| / |
| / |
| / |
|/ |
C --- D
|\ /|
| \ / |
| X |
| |
E --- F
Здесь ребро AC пересекается с ребром EF.

- Для в) 8 вершин:
A --- B
| / |
| / |
| / |
|/ |
C --- D
|\ /|
| \ / |
| X |
| / \ |
|/ \|
E --- F
Здесь ребро AC пересекается с ребром DF.

- Для г) 9 вершин:
A --- B --- C
\ | / |
\ | / |
\ | / |
\|/ |
D --- E
/ \ |
/ \ |
/ \ |
F -------- G
Здесь ребро AC пересекается с ребром EG.

2. Теперь построим плоский граф, соответствующий графу из предыдущего задания. Плоский граф - это граф, у которого нет пересекающихся ребер на плоскости. Для этого мы должны перерисовать предыдущий граф так, чтобы все его ребра не пересекались.
- Для графа из а) 6 вершин, воспользуемся перечеркнутым ребром для изображения ребер, которые пересекались:
A B
|\ /|
| X |
|/ \|
C---D
| |
E---F

- Для графа из б) 7 вершин:
A---B
| /|
| X |
|/ |
C---D
|\ /|
| X |
| \|
E---F

- Для графа из в) 8 вершин:
A---B
| /|
| X |
|/ |
C---D
|\ /|
| X |
| \|
E---F

- Для графа из г) 9 вершин:
A---B---C
|\ / \ /|
| X X |
|/ \ / \|
D---E---F
\ |
G------

3. Теперь построим геометрически двойственный граф к графу из задания 2. Геометрически двойственный граф получается из плоского графа путем соединения ребер, их середин, и таким образом, что получаемые ребра не пересекаются.
- Для графа из а) 6 вершин, геометрический двойственный граф будет выглядеть следующим образом:
A---B
/| /|
/ | / |
D--C--F

- Для графа из б) 7 вершин:
A---B---C
|\ / \ /|
| D E |
|/ \ / \|
F---G---H

- Для графа из в) 8 вершин:
A---B---C---D
|\ / \ / \ |
| E F G |
|/ \ / \ / \|
H---I---J---K

- Для графа из г) 9 вершин:
A---B---C
|\ / \ /|
| D E |
|/ \ / \|
F---G---H
|\ |
I ----J

4. Чтобы показать, что К5 (полный граф с 5 вершинами) не обладает абстрактно двойственными графами, нам нужно понять, что нет способа нарисовать К5 так, чтобы его геометрический двойственный граф не имел пересекающихся ребер. К5 имеет 10 ребер, что делает его геометрического двойственного графа сложным для рисования без пересечений. Можно провести простой эксперимент и попытаться самостоятельно нарисовать К5 и его геометрический двойственный граф с непересекающимися ребрами, и увидеть, что это не возможно.

Надеюсь, это решение помогло! Если у тебя возникнут вопросы, не стесняйся задавать их. Я всегда готов помочь!