Тема 10. Плоские графы

Задание 1. Изобразите, если это возможно, графы без самопересечений ребер; изобразите без самопересечений ребер графы ,

Задание 2. Покажите, что подграф плоского графа является плоским.

Задание 3. Изобразите все плоские полные двудольные графы; все плоские графы коктельной партии.

Задание 4. Пользуясь теорией Жордановых кривых, докажите, что графы и не являются плоскими.

Доказательство (для графа ). Предположим, что граф на вершинах 1,2,…,5 – плоский, и рассмотрим его плоское представление. Рассмотрим цикл как Жорданову кривую. Вершина 4 лежит или внутри, или вне этой кривой. Предложим, что внутри, и соединим вершину 4 со всеми вершинами 1, 2, 3. Тогда вершина 5 лежит либо внутри одного из «малых» треугольников, либо вне «большого». В первом случае (например, 5 попадает в треугольник с вершинами 2, 3, 4) вершину 5 нельзя соединить с одной из вершин 1, 2, 3 (в нашем случае с вершиной 1). Во втором случае вершину 5 нельзя соединить с вершиной 4, противоречие. Случай, когда вершина 4 лежит за пределами соответствующего цикла, рас­сматривается аналогично.

Задание 5. Докажите, что графы и являются «плоскими» на торе.

Задание

c

6. Проверьте формулу Эйлера для графов, изображенных на рисунках.

a

Задание 7. Для трех графов, изображенных на рисунках, постройте дуальные им графы.

Задание 8. Изобразите плоские графы тел Платона; проверьте форму­лу Эйлера для каждого из этих графов; изобразите дуальные графы для графов тел Платона и докажите, что существует ров­но 5 тел Платона.

Доказательство. На рисунке

изображены требуемые плоские графы. Все полученные графы регулярны. Найдем число таких графов. Пусть d ≥ 3 - степень вершины, a h ≥ 3 - степень грани. Пусть n - число вершин, m - число ребер, а f - число граней. Тогда dn = 2m = pf. По формуле Эйлера, n - m + f = 2. Домножив на pd, получим, что pdn - pdm+pdf = 2pd, или, так как 2m = dn, 2m = pf, что 2pm - pdm + 2dm = 2pd, откуда . Таким образом, 2р - pd + 2d│2pd. Так как 2p-pd + 2d , то pd - 2р -2d<0, или (р - 2)(d - 2)< 4. Это дает возможные значения скобок (1, 1),

(1, 2), (1, 3), (2,1), (3,1). Отсюда следует, что все возможные значения введенных выше величин представлены в следующей таблице:

p	d	n	m	f

Таким образом, мы получили не только доказательство су­ществования ровно пяти тел Платона, но и основные характе­ристики этих тел.

Задание 9. На 10 вершинах изобразите: плоский граф; 2 неизоморф­ных плоских графа; неплоский граф; 2 неизоморфных неплос­ких графа.

Задание 10. Докажите, что граф, гомеоморфный плоскому графу, является плоским.

Задание 11. Докажите, что любой плоский граф можно изобразить с помощью ребер – прямолинейных отрезков.

Задание 12. Изобразите графы, приведенные на рисунках, с помощью ребер – прямолинейных отрезков.

Задание 13. Докажите, что любой граф можно уложить в пространстве так, что его ребра будут отрезками прямых.

Задание 14. Сколько ребер можно добавить к графу G (в каждом из двух приведенных примеров), чтобы он остался плоским?

		G
	G

Задание 15. Плоский граф называется триангулированным, если он «максимально плоский», то есть к нему нельзя добавить ни од­ного ребра, не потеряв свойство «быть плоским». Существу­ют ли триангулированные графы на 1, 2 ,...,n,... вершинах? Сколько граней имеют триангулированные графы на n вер­шинах? Сколько ребер имеют триангулированные графы на n вершинах?

Ответ: 2(n -2); З n.

Задание 16. Существуют ли неизоморфные триангулированные графы на n вершинах?

Задание 17. Приведите пример 2-, 3-, 4-раскрашиваемого графа. Являются ли графы тел Платона 2-(3-, 4-, 5-) раскрашиваемыми?

Задание 18. Медиальным для плоского графа G называется граф M (G), вершинами которого являются ребра G, и две вершины в M (G) соединены ребром, если соответствующие ребра графа G имели общую вершину и принадлежали одной и той же грани. Изоб­разите медиальные графы для следующих графов:

Задание 19. Хроматическим числом графа G (не обязательно плос­кого) называется наименьшее число цветов, необходимых для раскраски вершин графа так, чтобы соседние вершины были окрашены в разные цвета. Приведите пример графа, хромати­ческое число которого равно 2 (3, 4, 5). Докажите, что любое натуральное n является хроматическим числом некоторого графа. Укажите хроматические числа графов .

Задание 20. Как связаны хроматические числа графа и его подграфа? Как связаны хроматические числа графов и с хроматиче­скими числами их объединения и соединения ?

Задание 21. Укажите наименьшее хроматическое число для графа, со­держащего простой цикл длины 3.