17αℵ. Плоские графы
Листок девятого класса
·
Граф называют плоским, если он нарисован на плоскости так, что разные вершины не совпадают, а рёбра пересекаются только в концах. Если граф можно нарисовать на плоскости без самопересечений, но не выбран конкретный способ это сделать, граф называют планарным. Гранями плоского графа называются куски, на которые его рёбра разбивают плоскость. Формула Эйлера. Если в связном плоском графе В вершин, Р рёбер и Г граней, то В-Р+Г=2
·
Двойственный граф G' к планарному графу G — это граф, в котором вершины соответствуют граням графа G; две вершины соединены ребром если и только если соответствующие им грани графа G имеют общее ребро.
1
Проверьте формулу Эйлера для всех правильных многогранников: тетраэдра, куба, октаэдра, икосаэдра и додекаэдра (на картинке в этом порядке).
2
Докажите формулу Эйлера,для а) дерева; б) произвольного связного плоского графа
3
Докажите формулу Эйлера для графов на сфере.
4
Докажите формулу Эйлера для выпуклых многогранников.
5
Нарисуйте для правильных многогранников двойственные графы. Каким многогранникам они соответствуют?
6
Докажите для простых плоских графов: а) 2Р ≥ 3Г при Г ≥ 2; б) Р ≤ 3В − 6 при В ≥ 3.
7
Докажите, что а) полный граф с пятью вершинами; б) полный двудольный граф с тремя вершинами в каждой доле непланарны.
8
Докажите, что в любом простом плоском графе есть вершина, степень которой меньше 6.
9
Докажите, что плоскую карту можно покрасить в 6 цветов так, что страны, имеющие общий участок границы, были разного цвета.
10
То же, но в 5 цветов
11
Как дефомировать эластичную поверхность чашки в поверхность бублика? Нельзя рвать и склеивать, но можно растягивать и сжимать
12
а) Нарисуйте на торе (поверхности бублика или, что то же самое, чашески) граф, у которого каждую грань можно распрямить и получится плоская фигура без дырок. Чему равно В-Р +Г? б) Докажите, что для остальных таких графов на торе В-Р+Г равно тому же. Подсказка: .огещбо од хи етичьлемзи и ерот мондо ан афарг авд етйусираН .)морбер с унишрев юувон или( орбер еовон инарг иртунв итсеворп или унишрев юувон ербер ан ьтиватсоп илсе ,ястеянем ен Г + Р − В отч ,етьреворП
13
Можно ли нарисовать на торе полный граф с а) 5; б) 6; в)7; г) 8 вершинами без самопересечений?
14
Придумайте и докажите аналог формулы Эйлера для графов на кренделе --- сфере с двумя ручками.
15
Слева даны две фигуры. Как деформировать поверхность одной из них в поверхность другой?
16
А на сфере с g ручками?