Основные понятия теории графов. Гладких О.Б - 77 стр.

UptoLike

ВУЗ: 

ЕГУ им. Бунина | Елец

Составители: 

Рубрика: 

100
шинам v
1
,…,v
p
графа G добавить вершины u
1
,…,u
p
и множество ребер {(v
i
, u
i
)}[pic]{(u
i
, v
i+1
)}.
Степенью вершины v называется число ре-
бер d(v), инцидентных ей, при этом петля учиты-
вается дважды. В случае ориентированного графа
различают степень do(v) по выходящим дугам и
di(v) – по входящим.
Указанные названия цепей и циклов связаны
с именем Уильяма Гамильтона (Hamilton W.), ко-
торый в 1859 году предложил следующую игру-
головоломку:
требуется, переходя по очереди от
одной вершины додекаэдра к другой вершине по
его ребру, обойти все 20 вершин по одному разу и
вернуться в начальную вершину (рис. 4.1).
Рис. 4.1.
77
() min
T Ф
GT
β
⊆
=
При подсчете числа внешней устойчивости
следует начинать с максимального числа вершин
графа, затем уменьшать его, проверяя, образуют
ли выбранные вершины внешне устойчивое мно-
жество.
Пример 1.38.
Определим число внешней устойчивости для
графов, изображенных на рис. 1.33. Любая пара
вершин графа G
1
образует внешне устойчивое
множество, но любая его вершина не является
внешне устойчивым множеством, следовательно,
I
.(G
1
) = 2. Граф G
2
содержит два внешне устой-
чивых множества T
1
= {x
1
, x
3
}, T
2
= {x
2
, x
4
} с мини-
мальным числом элементов, т.е.
I
(G
2
) = 2. Для
графа G
3
внешне устойчивым множеством мини-
мальной мощности является T = {x
2
, x
5
}, т.е.
I
(G
3
)
= 2.
К определению числа внешней устойчивости
графа сводится задача о часовых. На посту рас-
ставлены часовые, охраняющие n объектов, при-
чем один и тот же часовой может наблюдать за не-
сколькими объектами. Нужно выяснить, каково
минимальное число часовых, необходимых для
наблюдения за всеми объектами. Граф, изобра-
женный на рис. 1.34, соответствует следующей
за-
даче: 9 вершин графа – охраняемые объекты 
шинам v1,…,vp графа G добавить вершины u1,…,up                        β (G ) = min T
                                                                              T ⊆Ф
и множество ребер {(vi, ui)}[pic]{(ui, vi+1)}.
       Степенью вершины v называется число ре-          При подсчете числа внешней устойчивости
бер d(v), инцидентных ей, при этом петля учиты-    следует начинать с максимального числа вершин
вается дважды. В случае ориентированного графа     графа, затем уменьшать его, проверяя, образуют
различают степень do(v) по выходящим дугам и       ли выбранные вершины внешне устойчивое мно-
di(v) – по входящим.                               жество.
       Указанные названия цепей и циклов связаны                    Пример 1.38.
с именем Уильяма Гамильтона (Hamilton W.), ко-           Определим число внешней устойчивости для
торый в 1859 году предложил следующую игру-        графов, изображенных на рис. 1.33. Любая пара
головоломку: требуется, переходя по очереди от     вершин графа G1 образует внешне устойчивое
одной вершины додекаэдра к другой вершине по       множество, но любая его вершина не является
его ребру, обойти все 20 вершин по одному разу и   внешне устойчивым множеством, следовательно,
вернуться в начальную вершину (рис. 4.1).          I.(G1) = 2. Граф G2 содержит два внешне устой-
                                                   чивых множества T1 = {x1, x3}, T2 = {x2, x4} с мини-
                                                   мальным числом элементов, т.е. I (G2) = 2. Для
                                                   графа G3 внешне устойчивым множеством мини-
                                                   мальной мощности является T = {x2, x5}, т.е. I (G3)
                                                   = 2.
                                                         К определению числа внешней устойчивости
                                                   графа сводится задача о часовых. На посту рас-
                                                   ставлены часовые, охраняющие n объектов, при-
                                                   чем один и тот же часовой может наблюдать за не-
                                                   сколькими объектами. Нужно выяснить, каково
                                                   минимальное число часовых, необходимых для
                    Рис. 4.1.                      наблюдения за всеми объектами. Граф, изобра-
                                                   женный на рис. 1.34, соответствует следующей за-
                                                   даче: 9 вершин графа – охраняемые объекты

                          100                                                  77

Страницы