Пример решения типовой задачи

Пример 1. Пусть граф типа дерева – G ₇ на рис. 20. Сколько вершин максимального типа имеется в данном графе? Каково цикломатическое число графа? Чему равно цикломатическое число графа G ', являющегося лесом и пред­ставленного двумя одинаковыми деревьями G ₇. Построить ориентированное дерево с корнем v ₀, являющимся вершиной максимального типа.

Типы вершин графа G ₇ отмечены на рис.22, а, граф содержит две вершины максимального (4-го) типа.

Цикломатическое число любого дерева V (G) = V _c+ V _e- V_V = 0.

Рис. 22

Действительно, число вершин V_V в дереве на единицу больше числа ребер V _e, т.е. V_e-V_V= -1, а число связных компонент графа типа дерева V _с= 1. Таким обра­зом, цикломатическое число любого дерева, в том числе графа G ₇, V = 0.

Цикломатическое число леса равно сумме цикломатических чисел своих связных компонент - деревьев, т.е. также равно нулю; такимобразом,

,

где G '-граф, представленный двумя одинаковыми деревьями G.

Упражнения

1. Выполнить задание примера 1 для графов, изображенных на рис. 23.

Рис. 23

2. Определить цикломатическое число и максимальный тип вершин.

3. Найти остов минимального веса.

4. Найдите количество остовных подграфов, являющихся деревьями, в полных подграфах с 3-мя, 4-мя, 5-ю, 6-ю вершинами.

5. Нарисовать все попарно неизоморфные деревья восьмого порядка.

6. Доказать, что центр дерева состоит из 1 вершины в случае, когда диаметр этого дерева четное число, и из 2-х смежный вершин, если диаметр – нечетное число.

7. Нарисовать все попарно неизоморфные деревья седьмого порядка.

8. Докажите, что если из каждой вершины графа выходит более одного ребра, то граф не является деревом.

9. Докажите, что у дерева всегда найдется вершина, из которой выходит ровно одно ребро (такая вершина называется висячей).

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

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

12. В некоторой стране любые два города соединены либо авиалинией, либо железной дорогой. Докажите, что:

a) можно выбрать вид транспорта так, чтобы от любого города можно было добраться до любого другого, пользуясь только этим видом транспорта;

b) из некоторого города, выбрав один из видов транспорта, можно добраться до любого другого города не более, чем с одной пересадкой (пользоваться можно только выбранным видом транспорта);

c) можно выбрать вид транспорта так, чтобы пользуясь только им, можно было добраться из любого города до любого другого не более, чем с двумя пересадками.

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

14. В некоторой стране есть столица и еще 100 городов. Некоторые города (в том числе и столица) соединены дорогами с односторонним движением. Из каждого нестоличного города выходит 20 дорог, и в каждый город входит 21 дорога. Докажите, что в столицу нельзя проехать ни из одного города.

15. В некотором городе каждый город соединен с каждым дорогой. Сумасшедший король хочет ввести на дорогах одностороннее движение так, чтобы выехав из любого города, в него нельзя было вернуться. Можно ли так сделать?

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

17. В связном графе степени всех вершин четны. Докажите, что на ребрах этого графа можно расставить стрелки так, чтобы выполнялись следующие условия: а) двигаясь по стрелкам, можно добраться от любой вершины до любой другой; б) для каждой вершины числа входящих и исходящих ребер равны.

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

Раскраска графов

Раскраской графа называется такое приписывание цветов (натуральных чисел) его вершинам, что никакие две смежные вершины не получают одинаковый цвет.

Наименьшее возможное число цветов в раскраске называется хроматическим числом.

Формула Эйлера: в связном планарном графе справедливо

p-q+R=2,

где p - число вершин, q – число ребер, R – число граней плоского графа.

Следствие: если G – связный планарный граф (p>3), то .

Следствие: граф планарен тогда и только тогда, когда он не содержит вкачестве подграфов ни G ₁, ни G ₂.

G 1

G 2

Следствие: в любом планарном графе существует вершина, степень которой не больше 5.

Теорема о пяти красках: всякий планарный граф можно раскрасить пятью красками.

Связный плоский мультиграф без мостов называется картой.

Мостом называется ребро, при удалении которого увеличивается число компонент графа.

Карта называется к-раскрашиваемой, если для неё существует к-раскраска.

Задания

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

2. Докажите, что для любого дерева хроматическое число не превосходит 2.

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

4. Можно ли расположить на плоскости четыре точки и соединить их попарно шестью отрезками так, чтобы эти отрезки либо не пересекались, либо пересекались в данных точках?

5. Можно ли построить три дома, вырыть три колодца и соединить их тропинками так, чтобы тропинки не пересекались?

6. В стране Озерная 7 озер, соединенных между собой 10-ю каналами, причем от любого озера можно доплыть до любого другого. Сколько в этой стране островов?

7. Покажите, что добавление ребра к графу (при условии, что граф остаётся плоским) либо увеличивает число граней на 1, либо сокращает число связных компонент на 1.

8. Существует ли многогранник, у которого все грани семиугольные?