Лекции 14. Основные понятия теории графов. Некоторые виды графов (4 часа)

4. Раскраска графов
Раскраской графа называется такое приписывание цветов (натуральных чисел) его вершинам, что никакие две смежные вершины не получают одинаковый цвет.
Наименьшее возможное число цветов в раскраске называется хроматическим числом.
Множество вершин одного цвета называется одноцветным классом.
Граф укладывается на некоторой поверхности, если его можно нарисовать на этой поверхности так, чтобы его ребра не пересекались.
Граф называется планарным, если его можно уложить на плоскости.
Эйлерова характеристика – это соотношения между числом вершин, ребер и граней.
Формула Эйлера: в связном планарном графе справедливо p-q+r=2, где
p - число вершин, q – число ребер, r – число граней плоского графа.
Следствие: если G – связный планарный граф (p>3), то q<=3p – 6.
Следствие: граф планарен тогда и только тогда, когда он не содержит в качестве подграфов ни G1, ни G2.

G1 G2
Следствие: в любом планарном графе существует вершина, степень которой не больше 5.
Теорема о пяти красках: всякий планарный граф можно раскрасить пятью красками.
Связный плоский мультиграф без мостов называется картой.
Мостом называется ребро, при удалении которого увеличивается число компонент графа.
Карта называется к-раскрашиваемой, если для неё существует к-раскраска.


Контрольные вопросы.

1. 
   Найдите хроматические числа графа:
   

2. 
   Докажите, что для любого дерева хроматическое число не превосходит 2.
   
3. 
   Пусть планарный граф с В вершинами и Р ребрами разбивает плоскость на Г частей (которые будем называть гранями). Доказать, что справедлива следующая формула Эйлера: В-Р+Г=2
   
4. 
   Можно ли расположить на плоскости четыре точки и соединить их попарно шестью отрезками так, чтобы эти отрезки либо не пересекались, либо пересекались в данных точках?
   
5. 
   Можно ли построить три дома, вырыть три колодца и соединить их тропинками так, чтобы тропинки не пересекались?