close

Вход

Забыли?

вход по аккаунту

код для вставкиСкачать
Плоские графы и теорема Рамсея
Определение 1. Граф, который можно нарисовать так, чтобы его ребра не пересекались
нигде, кроме вершин, называется плоским или планарным.
Теорема Эйлера. Для правильно нарисованного связного плоского графа имеет место
равенство V-E+F=2.
Правильно нарисованный плоский граф разбивает плоскость на куски. Обозначим число
этих кусков через F, число вершин графа через V, число ребер через E.
(Для доказательства вспомните про волейбольную сетку)
1. В квадрате отметили 20 точек и соединили их непересекающимися отрезками друг с
другом и с вершинами квадрата так, что квадрат разбился на треугольники. Сколько
получилось треугольников?
2. Докажите, что для плоского графа верно неравенство 2E  3F.
3. Доказать, что граф на рисунке неплоский.
Определение 2. Граф, каждая вершина которого соединена с любой другой вершиной,
называется полным.
4. Каждые 2 из 6 компьютеров соединены проводом. Можно ли все эти провода
раскрасить в пять цветов так, чтобы из каждого компьютера выходили 5 проводов одного
цвета?
5. Нарисовать плоский граф, имеющий 6 вершина, степень каждой из которых равна а) 3;
б) 4.
6. Нарисовать плоский граф, имеющий 8 вершин, степень каждой из которых равна 4.
7. Докажите, что граф, имеющий 10 вершин, степень каждой из которых равна 5,
неплоский.
8. Докажите, что в любом плоском графе есть вершина, степень которой не превосходит
5.
9. Каждое ребро полного графа с 11 вершинами покрашено в один из двух цветов:
красный или синий. Докажите, что либо «красный», либо «синий» граф не является
плоским.
Теорема (Вагнер, Фари, Штейн). Плоский граф можно изобразить так, чтобы все его
ребра были отрезками.
1/--страниц
Пожаловаться на содержимое документа