Полная версия

Главная arrow Математика, химия, физика

  • Увеличить шрифт
  • Уменьшить шрифт


<<   СОДЕРЖАНИЕ   >>

Построение графов на основе их характеристик

Теоретические сведения

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

Важно помнить, что в любом графе сумма степеней всех его вершин — число четное, равное удвоенному числу ребер графа, так как каждое ребро участвует в этой сумме ровно два раза. Этот результат, известный еще 200 лет назад Эйлеру, часто называют леммой о рукопожатиях. Из нее следует, что если несколько человек обменялись рукопожатиями, то общее число пожатых рук обязательно четно, ибо в каждом рукопожатии участвуют две руки (при этом каждая рука считается столько раз, сколько она участвовала в рукопожатиях). Отсюда следует, что:

  • • число вершин с нечетной степенью у любого графа четно;
  • • во всяком графе с п вершинами, где п > 2, всегда найдутся по меньшей мере две вершины с одинаковыми степенями;
  • • если в графе с вершинами п > 2 в точности две вершины имеют одинаковую степень, то в этом графе всегда найдется либо в точности одна вершина степени 0, либо в точности одна вершина степени (п - 1).

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

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

Х5(у/) =

где т — количество вершин, а суммирование ведется по всем вершинам от 1 до п.

Задачи

Задача 2.42. Построить граф на восьми вершинах, имеющий следующее распределение степеней вершин: две вершины степени 4; три вершины степени 3; две вершины степени 2; одна вершина степени 1.

Решение.

Суммарная степень всех вершин равна 2-4 + 3- 3 + 2- 2+1 • 1=22, отсюда следует, что всего 11 ребер. Строить графы на основании вектора степеней проще, начиная с вершин больших степеней. Вер-

Таблица 2.9

Соответствие между описанием графа и его свойствами

Прилагательное

Числительное

Что это значит

Связный

к = 1

В графе ровно одна компонента связности

Несвязный

к> 2

В графе более одной компоненты, его диаметр точно равен бесконечности

Регулярный

5(У;) = СОШІ

Степени всех вершин равны

Регулярный степени у

з(Уі)=У

Степени всех вершин равны у. Если известно п (число вершин), то можно сразу рассчитать т (число ребер): т-п ? у/2 (п или у должно быть числом четным)

Ациклический

у= т-п + к = 0

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

Дерево(или ациклический связный граф)

у= т- п + 1 =0, откуда т- п - 1

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

Бихроматиче-

ский

И = 2

Хроматическое число графа равно двум, такие графы всегда можно раскрасить в два цвета, это — двудольные графы, графически это или ациклические графы, или графы, у которых все циклы имеют четную длину

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

Задача 2.43. Построить граф на шести вершинах, имеющий следующее распределение степеней вершин: две вершины степени 3;

Решение задачи 2.42

Рис. 2.8. Решение задачи 2.42

две вершины степени 2; одна вершина степени 1; одна вершина имеет произвольную степень.

Решение.

Суммарная степень вершин равна 11, следовательно, оставшаяся вершина должна иметь нечетную степень, т.е. 1,3 или 5. Таким образом, возможно построить три разных графа (рис. 2.9).

Решение задачи 2.43

Рис. 2.9. Решение задачи 2.43

Задача 2.44. Построить граф, имеющий следующий вектор степеней вершин: 5 = {1, 2, 2, 3, 4, 4, 5}.

Решение.

Суммарная степень равна 5 + 8 + 3 + 4+1=21. Так как это нечетное число, что противоречит теореме (количество ребер в два раза меньше этого числа, но 21 нацело на 2 не делится).

Ответ. Такого графа не существует.

Задача 2.45. Построить граф, имеющий следующий вектор степеней вершин: 5 = {1, 1,2, 2, 2, 4, 4, 4, 4}.

Задача 2.46. Построить граф, имеющий следующий вектор степеней вершин: 5 = {5, 5, 6, 6, 6, 6, 6}.

Задача 2.47. Построить граф, имеющий следующий вектор степеней вершин: 5 = {1, 1, 1,2, 3, 3, 3, 3, 5, 5, 5}.

Задача 2.48. Построить граф, имеющий следующий вектор степеней вершин: 5 = {3, 3, 3, 3, 3, 3, 3, 7}.

Задача 2.49. Построить граф на шести вершинах, имеющий следующее распределение степеней вершин: три вершины степени 5, а другие три вершины — неизвестной степени.

Задача 2.50. Построить граф на десяти вершинах, имеющий ребер в два раза больше, чем вершин, и следующее распределение степеней вершин: две вершины степени 6; четыре вершины степени 5; две вершины степени 4; две вершины произвольной степени — или обосновать невозможность построения такого графа.

Задача 2.51. Построить граф на десяти вершинах, имеющий следующее распределение степеней вершин: одна вершина степени 7; две вершины степени 6; две вершины степени 5; две вершины степени 4; две вершины степени 3; одна вершина степени 2 — или обосновать невозможность построения такого графа.

Задача 2.52. Построить граф на 11 вершинах, имеющий следующее распределение степеней вершин: одна вершина степени 7; две вершины степени 6; две вершины степени 5; две вершины степени 4; две вершины степени 3; одна вершина степени 2 — или обосновать невозможность построения такого графа.

 
<<   СОДЕРЖАНИЕ   >>