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

UptoLike

ВУЗ: 

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

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

Рубрика: 

108
Рис. 4.6.
Теорема 4.3. (Кенига-Холла (Konig D., Hall P.)) Паро-
сочетание, отображающие V в U, существует тогда
и только тогда, когда | EW | ≥ | W | для любого мно-
жества W . V.
Следствие: Пусть (V, U, E) – простой граф, a
m = max {| Ev |, | E
−1
u |: v . V, u . U),
тогда всегда существует паросочетание, исполь-
зующее все те вершины v, для которых | Ev | = m, и
все те вершины u, для которых | E
−1
u | = m.
Теорема 4.4. Необходимое и достаточное условие
существования фактора у графа (V, E) состоит в
том, чтобы | EW | ≥ | W | при всех W
⊂ V.
Следствие: Если граф (V, E) таков, что
| Ev | = | E
−1
v | = m
для любой вершины v, то дуги этого графа можно
распределить по m непересекающимся множест-
вам W
1
, W
2
, …, W
m
, каждое из которых образует
фактор.
Отыскание фактора является несложным де-
лом, поскольку это есть задача о наибольшем по-
токе. Метод нахождения гамильтонова контура со-
стоит в нахождении всех факторов графа и сохра-
нении только тех из них, которые состоят из един-
ственного контура.
69
Рис. 1.26.
Рассмотрим некоторые основные операции,
производимые над графами.
Определение 1.66. Операцией добавления к графу
G = (М, R) вершины а образуется граф {M
® {a},
R).
Определение 1.67. Операция добавления дуги
(а,.b) к графу G состоит в образовании графа
(М
® {a, b}, R ® {(a, b)}).
Определение 1.68. Под операцией удаления дуги
(а, b) из графа G понимается операция, заклю-
чающаяся в удалении пары (а, b) из множества дуг
R в результате получается граф {M, R \ {(a, b)}).
Определение 1.69. Операция удаления вершины а
из графа G заключается в удалении вершины а
вместе с инцидентными ей дугами:
(М \ {a}, R \ {(b, c) | b = а или с = а}).
Определение 1.70. Операция отождествления
вершин а и b графа G = (М, R) состоит в удалении
из графа G вершин а и b и присоединении новой
вершины а', дуг (а', с), если (а, с)
´ R или (b, с) ´
R, и дуг (с, а'), если (с, а)
´ R, или (c, b) ´ R: 
                      Рис. 4.6.

Теорема 4.3. (Кенига-Холла (Konig D., Hall P.)) Паро-
сочетание, отображающие V в U, существует тогда
и только тогда, когда | EW | ≥ | W | для любого мно-
                                                                              Рис. 1.26.
жества W . V.
Следствие: Пусть (V, U, E) – простой граф, a                 Рассмотрим некоторые основные операции,
         m = max {| Ev |, | E −1u |: v . V, u . U),     производимые над графами.
тогда всегда существует паросочетание, исполь-          Определение 1.66. Операцией добавления к графу
зующее все те вершины v, для которых | Ev | = m, и      G = (М, R) вершины а образуется граф {M ® {a},
все те вершины u, для которых | E −1u | = m.            R).
Теорема 4.4. Необходимое и достаточное условие          Определение 1.67. Операция добавления дуги
существования фактора у графа (V, E) состоит в          (а,.b) к графу G состоит в образовании графа
том, чтобы | EW | ≥ | W | при всех W ⊂ V.                             (М ® {a, b}, R ® {(a, b)}).
                                                        Определение 1.68. Под операцией удаления дуги
Следствие: Если граф (V, E) таков, что                  (а, b) из графа G понимается операция, заклю-
                | Ev | = | E −1v | = m                  чающаяся в удалении пары (а, b) из множества дуг
для любой вершины v, то дуги этого графа можно          R в результате получается граф {M, R \ {(a, b)}).
распределить по m непересекающимся множест-             Определение 1.69. Операция удаления вершины а
вам W1, W2, …, Wm, каждое из которых образует           из графа G заключается в удалении вершины а
фактор.                                                 вместе с инцидентными ей дугами:
      Отыскание фактора является несложным де-                  (М \ {a}, R \ {(b, c) | b = а или с = а}).
лом, поскольку это есть задача о наибольшем по-         Определение 1.70. Операция отождествления
токе. Метод нахождения гамильтонова контура со-         вершин а и b графа G = (М, R) состоит в удалении
стоит в нахождении всех факторов графа и сохра-         из графа G вершин а и b и присоединении новой
нении только тех из них, которые состоят из един-       вершины а', дуг (а', с), если (а, с) ´ R или (b, с) ´
ственного контура.                                      R, и дуг (с, а'), если (с, а) ´ R, или (c, b) ´ R:


                            108                                                      69

Страницы