Математическое моделирование на графах. Часть 1. Берцун В.Н. - 22 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

22 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1
Пусть b наиболее удаленная от a
1
общая вершина рассматриваемых
цепей, тогда расстояние
|(b, p)| + |(b, q)| = |(a
1
, p)| + |(a
1,
q)| – 2|(a
1
, b)|
оценивается четным числом ребер. Поэтому у графа есть простой
цикл (b,..., p, q,...,b) нечетной длины, что противоречит условию. Та-
ким образом, никакие две вершины множества B не соединены реб-
ром. Это утверждение имеет место и для вершин во множестве A. ■
Паросочетанием (независимым множеством ребер) называется
множество М попарно не смежных ребер графа G(V, E). На рис. 1.24
для графа K
5,5
приведен пример паросочетания и максимального па-
росочетания [11, 16, 17], для которого β
1
= 5.
12345 12345
Рис. 1.24
Если каждая вершина множества U⊆V инцидентна какому-либо
ребру паросочетания М, то говорят, что М покрывает множество U.
Известно [11], что максимальная мощность паросочетания в дву-
дольном графе равна минимальной мощности его вершинного по-
крытия а
0
.
Для полного двудольного графа
α
0
(K
n, m
) = min(n,m), α
1
(K
n, m
) = max(n,m),
β
0
(K
n, m
) = max(n,m), β
1
(K
n, m
) = min(n,m).
К необходимости нахождения паросочетания в графе приводят
различные практические задачи. Например, пусть имеется группа из
n рабочих, каждый из которых может выполнить один или несколь-
ко из m необходимых видов работ, но каждый рабочий должен вы-

Страницы