ВУЗ: Томский государственный университет систем управления и радиоэлектроники
Категория: Учебное пособие
Дисциплина: Дискретная математика
Добавлен: 28.11.2018
Просмотров: 16659
Скачиваний: 202
56
Если из графа G удалить все вершины, то получим граф, не содержащий
ни вершин, ни рёбер. Согласно [51, с. 57], «граф, который не имеет ни одной
вершины и ни одного ребра, называется пустым». Очевидно, что пустой граф
является подграфом любого графа.
Если n – число вершин графа G, то всего существует
n
2 подграфов. Что-
бы убедиться в этом, каждой вершине графа поставим в соответствие опреде-
лённый двоичный разряд и условимся считать, что нуль обозначает удаление
вершины, а единица – вершина из графа не удаляется. Тогда все подграфы ока-
жутся пронумерованными в двоичной системе, и по двоичному числу всегда
можно найти соответствующий подграф. Между множеством подграфов и
множеством n-разрядных двоичных чисел существует взаимно однозначное со-
ответствие. Следовательно, если n – число вершин графа, то подграфов суще-
ствует столько же, сколько и n-разрядных двоичных чисел, то есть
n
2 .
Пусть задан граф G, содержащий n пронумерованных вершин. Добавим к
ним ещё одну вершину и соединим ее с некоторыми вершинами графа G. Полу-
чим надграф графа G. Рассуждая, как и в предыдущем случае, приходим к вы-
воду, что при одной добавленной вершине возможно
n
2 надграфов.
Если из простого графа G удалить одно или несколько ребер, оставив все
вершины на прежних местах, то получим частичный граф. Формально частич-
ный граф определяется следующим образом.
Пусть V и E – множества вершин и ребер исходного графа G. Граф G
′
называется частичным графом графа G, если V
′ = V и E′ ⊆ E [14]. Отсюда сле-
дует, что всякий граф является частичным по отношению к самому себе.
Если из простого графа G удалить все ребра, то останется граф, состоя-
щий только из изолированных вершин. Такой граф, в котором нет ни одного
ребра, называется нуль-графом.
Для всякого простого графа, содержащего m рёбер, можно построить
m
2 частичных графов. Убедиться в этом можно, если воспользоваться тем же
приёмом их кодирования, как и в случае подграфов. Но в данном случае двоич-
ные разряды ставятся в соответствие не вершинам графа, а его рёбрам с анало-
гичной интерпретацией нулей и единиц (единицы могут обозначать удаление
соответствующих рёбер).
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1.
К линейному графу, содержащему 5 вершин, добавили ещё
одну вершину. Сколько существует линейных надграфов?
57
2.
В линейном графе G 8 рёбер. Сколько частичных графов
можно построить из графа G путём удаления из него тех или иных
рёбер?
3.
Дан помеченный граф G, содержащий 7 вершин. Сколько
подграфов, содержащих по 5 вершин, можно построить из графа G?
4.
Сколько существует линейных помеченных графов, в каж-
дом из которых содержится:
1) три вершины?
2) четыре вершины?
3) пять вершин?
5.
В графе G 20 вершин. Каждые две его вершины соединены
точно одним ребром.
а. Сколько рёбер в графе G?
б. Из графа G удалили две вершины. Сколько рёбер осталось?
в. Из графа G удалили n вершин. Осталось 91 ребро.
Найдите n.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
3.2 Смежность. Инцидентность. Степень вершины
Две вершины v
∈ V и w ∈ V, где V – множество вершин графа G, называ-
ются смежными, если они соединены ребром. Например, на рисунке 3.1 смеж-
ными являются вершины 1 и 2, 1 и 3, 4 и 6 и др. Два ребра называются смеж-
ными, если они имеют общую вершину. На рисунке 3.1 смежными являются
ребра {1,2} и {1,3}, {2,4} и {4,6} и др. Если вершина является концом ребра, то
вершина и ребро называются инцидентными. На рисунке 3.1 ребро {3,4} инци-
дентно вершине 3. Оно инцидентно также и вершине 4. Число
( )
ρ v
ребер, ин-
цидентных вершине
v
, называется её степенью. Например, степень вершины 1
(рис. 3.1) равна 3, степень вершины 5 равна 2, т. е.
ρ (1) = 3, ρ (5) = 2. Степень
изолированной вершины равна нулю. Степень изолированной вершины, содер-
жащей одну петлю, равна 2. Вершина, степень которой равна 1, называется ви-
сячей, или концевой. На рисунке 3.3 это вершина 4:
ρ (4) = 1.
Граф можно задать упорядоченным набором степеней его вершин.
Например, набор степеней вершин графа, изображённого на рисунке 3.1, имеет
вид 333322.
Сумма степеней всех вершин всякого графа (не только простого, но и
мультиграфа, а также псевдографа) есть четное число. Половина суммы степе-
58
ней всех вершин равна числу всех ребер графа. Этим свойством можно пользо-
ваться для определения числа K ребер графа:
(1)
(2)
(3) ...
( )
.
2
ρ
+ ρ
+ ρ
+ + ρ
=
n
K
(3.1)
Например, сумма степеней вершин графа, приведенного на рисунке 3.2,
равна:
ρ (1) + ρ (2) + ρ (3) + ρ (4) = 6 + 6 + 4 + 2 = 18,
откуда следует, что в графе девять ребер.
Вершина называется четной, если ее степень есть четное число. Вершина
называется нечетной, если ее степень есть нечетное число.
В любом графе число нечетных вершин четно. Например, в графе, приве-
дённом на рисунке 3.3, четыре вершины, и все они являются нечётными. Число
четных вершин в графе может быть как четным, так и нечетным. Например, в
графе на рисунке 3.1 число чётных вершин чётно, а на рисунке 3.4 – нечётно.
Рис. 3.4
Граф, в котором нет нечётных вершин, называется эйлеровым. Главная
особенность эйлеровых графов состоит в том, что в каждом из них существует
замкнутая уникурсальная линия [49, с. 91], то есть такая линия, которую можно
провести, не отрывая карандаша от бумаги, пройдя при этом по каждому ребру
точно один раз. Примером эйлерового графа является граф, изображенный на
рисунке 3.2. В нём все вершины чётны. На рисунке 3.1 приведён граф, в кото-
ром четыре нечётные вершины. Их номера 1, 2, 3, 4. В класс эйлеровых этот
граф не входит.
Граф, в котором содержится точно две нечётные вершины, называется
полуэйлеровым [47, с. 45]. В полуэйлеровом графе существует разомкнутая
уникурсальная линия. Её началом и концом являются нечётные вершины.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1.
Граф задан множеством рёбер:
G = {{1,2}, {1,4}, {1,6}, {2,5}, {3,7}, {5,6}}.
1
2
3
4
5
59
а. Укажите номера чётных вершин.
б. Укажите номера висячих вершин.
в. Укажите номера нечётных вершин, не являющихся висячи-
ми.
г. Укажите номера вершин, смежных по отношению к вер-
шине 1.
д. Приведите набор степеней всех вершин графа.
2.
Если задан набор степеней вершин, то можно построить со-
ответствующий граф, но не во всех случаях: для некоторых наборов
графы не существуют. В нижеприведённых списках укажите номе-
ра тех наборов, для которых граф построить невозможно.
1) а) 0 1 1 0 2 3 2
2) а) 1 1 3 4 5 7 6
3) а) 1 0 1 4 5 6 7
б) 1 1 1 0 1 3 3
б) 2 2 0 1 0 1 7
б) 1 2 3 4 1 2 3
в) 2 1 3 3 4 4 4
в) 6 9 9 4 1 3 2
в) 0 0 1 0 0 0 0
г) 0 0 1 1 0 1 5
г) 5 6 7 3 3 4 5
г) 2 2 2 1 2 2 2
д) 2 3 3 2 1 3 3
д) 2 6 7 3 3 3 0
д) 0 7 0 7 1 0 7
е) 4 2 1 0 7 3 0
е) 3 0 0 3 0 0 3
е) 2 3 5 6 7 4 2
ж) 2 5 5 1 1 1 0
ж) 0 0 1 1 0 1 7
ж) 3 4 5 4 3 2 1
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
3.3 Однородный граф. Полный граф. Дополнение графа
Граф называется однородным, если степени всех его вершин равны меж-
ду собой. Некоторые авторы пользуются другой терминологией. Например:
«Если все вершины графа имеют одинаковую степень, то такой граф называет-
ся регулярным» [1, с. 271]. Этого же термина придерживаются в [38, с. 193].
Примеры однородных графов приведены на рисунке 3.5.
Рис. 3.5
Если в формуле (3.1) принять:
ρ (1) = ρ (2) = … = ρ (n) = ρ ,
а
б
в
1
2
3
4
3
1
2
1
2
3
4
60
где n – число вершин графа;
ρ (i) – степень i-й вершины графа (i = 1, 2, … , n),
то формула для числа рёбер однородного графа примет вид:
.
2
ρ
=
n
K
(3.2)
Простой граф (без петель и кратных рёбер) называется полным, если каж-
дая пара его вершин соединена точно одним ребром. Примеры полных графов
приведены на рисунках 3.5, а и 3.5, б.
Степень каждой из вершин полного графа равна n – 1. Следовательно, со-
гласно формуле (3.2), число K ребер полного графа равно:
(
1)
.
2
−
=
n n
K
Пусть дан неполный граф G. Дополним его новыми рёбрами так, чтобы
получился полный граф. Все добавленные рёбра и все вершины исходного гра-
фа G образуют новый граф G
′. Построенный таким образом граф G′ называют
дополнением заданного графа до полного.
На рисунке 3.6 пунктирными линиями показано дополнение графа G. На
рисунке 3.4 дополнение представлено отдельным графом.
Рис. 3.6
Очевидно, что дополнением полного графа, построенного на п вершинах,
является нуль-граф (состоящий из п изолированных вершин), а дополнением
нуль-графа является полный граф.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Упражнения
1.
В однородном графе семь вершин, и степень каждой вер-
шины равна 6. Сколько в этом графе ребер?
2.
Укажите номера вопросов, на которые Вы ответите «да».
Возможен ли однородный граф, в котором:
1) семь вершин и степень каждой вершины равна 3?
2) восемь вершин и степень каждой из них равна 4?
3) четыре вершины и шесть ребер?
1
2
3
4
5