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

UptoLike

ВУЗ: 

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

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

Рубрика: 

116
FО, отметим жирной линией FH, HK, и КО (рис.
5.3). Найдем единственно возможный при данном
условии маршрут.
Рис. 5.3.
Подведем первый итог: задача решена в ходе
преобразования картинки. С рисунка остается счи-
тать ответ: имение Е принадлежит Манилову, D –
Коробочке, С – Ноздреву, А – Собакевичу, В –
Плюшкину, М – Тентетникову, F – Бетрищеву, Н –
Петуху, К – Констанжогло, О – Кошкареву.
Задача 5.2.
Лист бумаги Плюшкин разрезает на три час-
ти. Некоторые из этих полученных листов он так-
же разрезает на три части. Несколько новых лис-
тов он вновь разрезает на три более мелкие и т.д.
Сколько Плюшкин получает листов бумаги, если
разрезает k листов?
Решение.
Листы бумаги обозначим на рисунке
круж-
ками. Кружки, соответствующие листам, которые
61
Определение 1.56. Оставшиеся т – п + с ребер и
i
,
..., u
m – n + c
, не входящие в Т, называются хордами
остова Т.
Если к лесу Т добавить произвольную хорду
v
i
, то в полученном графе найдется ровно один
цикл, который обозначим через C
i
. Цикл C
i
состо-
ит из хорды v
i
и некоторых ветвей остова Т, кото-
рые принадлежат единственной простой цепи, со-
единяющей вершины хорды v
i
.
Определение 1.57. Цикл C
i
называется фундамен-
тальным циклом графа G относительно хорды v
i
остова Т.
Определение 1.58. Множество {C
i
, ..., C
m – n + с
}
всех фундаментальных циклов относительно хорд
остова Т называется фундаментальным множест-
вом циклов графа G относительно остова Т.
Отметим, что мощность фундаментального
множества циклов равна цикломатическому числу
v (G) = т – п + с.
Обозначим через (w
i
, ..., w
m
) последователь-
ность (v
1
, v
2
, ..., v
m–n+c
, и
1
, и
2
,..., u
n–c
) всех ребер гра-
фа G. Тогда фундаментальному циклу C
i
соответ-
ствует вектор а =(a
i1
, a
i2
, …, a
im
), определенный
по следующему правилу:
1, если
0, если
j
i
ij
j
i
wC
a
wC
∈
⎧
⎪
=
⎨
∉
⎪
⎩
FО, отметим жирной линией FH, HK, и КО (рис.        Определение 1.56. Оставшиеся т – п + с ребер иi,
5.3). Найдем единственно возможный при данном       ..., um – n + c, не входящие в Т, называются хордами
условии маршрут.                                    остова Т.
                                                            Если к лесу Т добавить произвольную хорду
                                                    vi, то в полученном графе найдется ровно один
                                                    цикл, который обозначим через Ci. Цикл Ci состо-
                                                    ит из хорды vi и некоторых ветвей остова Т, кото-
                                                    рые принадлежат единственной простой цепи, со-
                                                    единяющей вершины хорды vi.
                     Рис. 5.3.                      Определение 1.57. Цикл Ci называется фундамен-
      Подведем первый итог: задача решена в ходе    тальным циклом графа G относительно хорды vi
преобразования картинки. С рисунка остается счи-    остова Т.
тать ответ: имение Е принадлежит Манилову, D –      Определение 1.58. Множество {Ci, ..., Cm – n + с}
Коробочке, С – Ноздреву, А – Собакевичу, В –        всех фундаментальных циклов относительно хорд
Плюшкину, М – Тентетникову, F – Бетрищеву, Н –      остова Т называется фундаментальным множест-
Петуху, К – Констанжогло, О – Кошкареву.            вом циклов графа G относительно остова Т.
                                                            Отметим, что мощность фундаментального
                    Задача 5.2.
      Лист бумаги Плюшкин разрезает на три час-     множества циклов равна цикломатическому числу
ти. Некоторые из этих полученных листов он так-     v (G) = т – п + с.
же разрезает на три части. Несколько новых лис-             Обозначим через (wi, ..., wm) последователь-
тов он вновь разрезает на три более мелкие и т.д.   ность (v1, v2, ..., vm–n+c, и1, и2,..., un–c) всех ребер гра-
Сколько Плюшкин получает листов бумаги, если        фа G. Тогда фундаментальному циклу Ci соответ-
разрезает k листов?                                 ствует вектор а =(ai1, ai2, …, aim), определенный
                                                    по следующему правилу:
                     Решение.
      Листы бумаги обозначим на рисунке круж-                                ⎧⎪1, если w j ∈ Ci
ками. Кружки, соответствующие листам, которые                         aij = ⎨
                                                                            ⎪⎩0, если w j ∉ Ci


                           116                                                       61

Страницы