Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
hM; Ri вершины a образуется граф hM ∪ {a}; Ri. Операция добавления дуги (a, b) к графу G состоит в образо- вании графа hM ∪ {a, b}; R ∪ {(a, b)}i. Под операцией удаления дуги (a, b) из графа G понимается операция, заключающаяся в удалении пары (a, b) из множества дуг R, в результате получается граф hM; R \ {(a, b)}i. Опера- ция удаления вершины a из графа G заключается в удалении вершины a вместе с инцидентными ей дугами: hM \ {a}; R \ {(b, c) | b = a или c = a}i. Операция отождествления вершин a и b графа G = hM; Ri состоит в удале- нии из графа G вершин a и b и присоединении новой вершины a 0 , дуг (a 0 , c), если (a, c) ∈ R или (b, c) ∈ R, и дуг (c, a 0 ), если (c, a) ∈ R или (c, b) ∈ R: h(M \ {a, b}) ∪ {a 0 }; (R \ {(c, d) | c = a, или d = a, или c = b, или d = b})∪ ∪{(a 0 , c) | (a, c) ∈ R или (b, c) ∈ R, c / ∈ {a, b}} ∪ {(c, a 0 ) | (c, a) ∈ R или (c, b) ∈ R, c / ∈ {a, b}} ∪ {(a 0 , a 0 ) | найдутся c, d ∈ {a, b}, где (c, d) ∈ R}i. Говорят, что построенный граф получается из графа G отождествлением вершин a и b. В случае, когда a и b соединены дугой, операцию отождеств- ления вершин a и b называют стягиванием дуги (a, b). Пример 4.2.2. Из графа G, показанного на рис. 4.10, добавлением вер- шины 5 образуется граф G 1 , добавлением дуги (3, 1) — граф G 2 , удалением дуги (3, 2) — граф G 3 , удалением вершины 2 — граф G 4 , отождествлением вершин 1 и 4 — граф G 5 , стягиванием дуги (2, 3) — граф G 6 . ¤ 126 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ • • • • • • • • • • • • • • • • • • • • • • ? ? ? ? ? • • • • C C C C CC ¤ ¤ ¤ ¤ ¤¤ ±° ²¯ ¢ ¢ ¢ ¢ ¢ ¢® - ¢ ¢ ¢ ¢ ¢ ¢® 1 1 1 1 1 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 5 1 0 2 1 4 2 0 G G 1 G 2 G 3 G 4 G 5 G 6 Рис. 4.10 Дополнением графа без петель G = hM; Ri называется граф G hM; M 2 \ (R ∪ id M )i. Пример 4.2.3. Дополнением графа G, изображенного на рис. 4.10, яв- ляется граф G, показанный на рис. 4.11. ¤ Пусть G 1 = hM 1 ; R 1 i, G 2 = hM 2 ; R 2 i — графы. Объедине- • • • • ¡ ¡ ¡ ¡ ¡ ¡ @ @ @ @ @ @ 6 1 4 2 3 Рис. 4.11 нием G 1 ∪ G 2 графов G 1 и G 2 называется граф hM 1 ∪ M 2 ; R 1 ∪ R 2 i. Если M 1 ∩ M 2 6= ∅, то пересечением G 1 ∩ G 2 графов G 1 и G 2 называется граф hM 1 ∩M 2 ; R 1 ∩R 2 i. Кольцевой суммой G 1 ⊕ G 2 графов G 1 и G 2 называется граф hM 1 ∪ M 2 ; R 1 ⊕ R 2 i, где R 1 ⊕ R 2 = (R 1 \ R 2 ) ∪ (R 2 \ R 1 ). Пример 4.2.4. Для графов G 1 = h{a 1 , a 2 , a 3 }; [a 1 , a 2 ]∪ ∪{(a 2 , a 3 )}i и G 2 = h{a 1 , a 2 , a 4 }; {(a 1 , a 2 ), (a 4 , a 1 )}i (рис. 4.12) найдем G 1 ∪G 2 , G 1 ∩G 2 , G 1 ⊕G 2 . По определению имеем G 1 ∪G 2 = h{a 1 , a 2 , a 3 , a 4 }; [a 1 , a 2 ]∪ ∪{(a 2 , a 3 ), (a 4 , a 1 )}i, G 1 ∩ G 2 = h{a 1 , a 2 }; {(a 1 , a 2 )}i, G 1 ⊕ G 2 = h{a 1 , a 2 , a 3 , a 4 }; {(a 2 , a 1 ), (a 2 , a 3 ), (a 4 , a 1 )}i. ¤ Соединением G 1 + G 2 графов G 1 и G 2 называется граф hM 1 ∪ M 2 ; R 1 ∪ ∪R 2 ∪ ∪{[a, b] | a ∈ M 1 , b ∈ M 2 , a 6= b}i. Пример 4.2.5. Для графов G 1 и G 2 , показанных на рис. 4.13а, соедине- нием G 1 + G 2 является граф, представленный на рис. 4.13б. ¤ Часто при рассмотрении операции соединения графов предполагается, что M 1 ∩ M 2 = ∅. Произведением G 1 × G 2 графов G 1 и G 2 называется граф hM 1 × M 2 ; Ri, в котором ((a 1 , b 1 ), (a 2 , b 2 )) ∈ R тогда и только тогда, когда a 1 = a 2 и (b 1 , b 2 ) ∈ R 2 , или b 1 = b 2 и (a 1 , a 2 ) ∈ R 1 Пример 4.2.6. На рис. 4.14 изображено произведение G 1 × G 2 графов G 1 = h{1, 2}; {(1, 1), (2, 1)}i и G 2 = h{a, b, c}; [a, b] ∪ {(b, c)}i. ¤ 4.2. ПОДГРАФЫ И ЧАСТИ ГРАФА. ОПЕРАЦИИ НАД ГРАФАМИ 127 • • • ¡ ¡ ¡@ @@ R a 1 a 2 a 3 G 1 • • • X X X X X X y »»» »» » : a 1 a 4 a 2 G 2 • • • • @ @ @ I ¡ ¡ ¡@ @@ R a 1 a 2 a 3 a 4 G 1 ∪ G 2 • • 6 a 1 a 2 G 1 ∩ G 2 • • • • @ @ @ I ¡ ¡ ¡ ª @ @@ R a 1 a 2 a 3 a 4 G 1 ⊕ G 2 Рис. 4.12 • • • ¢ ¢ ¢ ¢ ¢¢AA A A AAU ¾ a 1 a 3 a 2 • • • ¢ ¢ ¢ ¢ ¢ ¢ A A A A A AK a 2 a 4 a 5 а • • • • • ´ ´ ´ ´ ´ ´ ´ ´ ´ Q Q Q Q Q Q Q Q Q ¾ a 1 a 3 a 4 a 5 a 2 б Рис. 4.13 • • 6 j 2 1 G 1 × • • • - a b c G 2 = • • • • • • 6 6 6 n n n - - (2, a) (2, b) (2, c) (1, a) (1, b) (1, c) G 1 × G 2 Рис. 4.14 128 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ • • • • (0, 0) (1, 0) (0, 1) (1, 1) • • • • • • • • ©© ©© © ©© ©© © HH HHH HH HHH (0, 0, 0) (0, 1, 0) (0, 0, 1) (0, 1, 1) (1, 0, 0) (1, 1, 0) (1, 0, 1) (1, 1, 1) Рис. 4.15 Неорграф без петель называется полным, если его любые две различ- ные вершины смежны. Полный граф, имеющий n вершин, обозначается че- рез K n С помощью операции произведения определим по индукции важ- ный класс графов, называемых n-мерными кубами (n-кубами). Рассмотрим граф K 2 , вершины которого обозначим 0 и 1. n-Мерный куб, или n-куб Q n , определяется по следующим правилам: Q 0 — граф без петель, состоящий из одной вершины, Q 1 K 2 , Q n K 2 × Q n−1 , n > 1. Вершинами n-мерного куба Q n являются всевозможные n-ки, состоящие из нулей и единиц (все- го таких наборов 2 n ), а ребра задаются по следующему правилу: вершины смежны тогда и только тогда, когда соответствующие кортежи различаются ровно одной координатой. На рис. 4.15 показаны двумерный Q 2 и трехмер- ный Q 3 кубы. Композицией G 1 [G 2 ] графов G 1 и G 2 называется граф hM 1 ×M 2 ; Ri, в ко- тором ((a 1 , b 1 ), (a 2 , b 2 )) ∈ R тогда и только тогда, когда выполняется одно из следующих условий: 1) (a 1 , a 2 ) ∈ R 1 ; 2) a 1 = a 2 и (b 1 , b 2 ) ∈ R 2 Пример 4.2.7. Композицией G 1 [G 2 ] графов G 1 и G 2 , рассмотренных в примере 4.2.6, является граф, изображенный на рис. 4.16, а композицией G 2 [G 1 ] — граф, представленный на рис. 4.17. ¤ 4.3. МАРШРУТЫ. ДОСТИЖИМОСТЬ. СВЯЗНОСТЬ 129 • • • • • • 6 6 6 - ±° ²¯ ±° ²¯ ±° ²¯ ¡ ¡ ¡ ¡ ¡ ¡ µ ¡ ¡ ¡ ¡ ¡ ¡ µ @ @ @ @ @ @ I @ @ @ @ @ @ I ©© ©© ©© ©© ©© © © * H H H H H H H H H H H H Y (2, a) (2, b) (2, c) (1, a) (1, c) (1, b) • • • • • • 6 6 6 - - ±° ²¯ ±° ²¯ ±° ²¯ ¡ ¡ ¡ ¡ ¡ ¡ @ @ @ @ @ @¡ ¡ ¡ ¡ ¡ ¡ µ @ @ @ @ @ @ R (a, 2) (b, 2) (c, 2) (a, 1) (c, 1) (b, 1) Рис. 4.16 Рис. 4.17 Неформально композиция G 1 [G 2 ] означает, что каждая вершина a графа G 1 заменяется на изоморфную копию G a графа G 2 , а затем, если (a 1 , a 2 ) ∈ R 1 , то между любыми вершинами b 1 из G a 1 и b 2 из G a 2 проводится дуга (b 1 , b 2 ). § 4.3. Маршруты. Достижимость. Связность Пусть G = hM; Ri — граф. Последовательность a 1 , u 1 , a 2 , u 2 , . . . , u n , a n+1 , (4.1) где a 1 , a 2 , . . . , a n+1 ∈ M, u 1 , u 2 , . . . , u n ∈ R, называется маршрутом, соеди- няющим вершины a 1 и a n+1 ((a 1 , a n+1 )-маршрутом), если u i = (a i , a i+1 ), i = 1, 2, . . . , n (рис. 4.18). Очевидно, что маршрут (4.1) можно задать последовательностью a 1 , . . . , a n+1 его вершин, а также последовательностью u 1 , . . . , u n дуг. Число n дуг в маршруте (4.1) на- • • • • • ¡ ¡ ¡ µ@ @ @ R ¡ ¡ ¡ µ a 1 a 3 a n a 2 a n+1 u 1 u 2 u n · · · Рис. 4.18 зывается его длиной. Пусть G — неорграф. Маршрут (4.1) называ- ется цепью, если все ребра [a 1 , a 2 ], . . . , [a n , a n+1 ] различны, и простой цепью, если все его вер- шины, кроме, возможно, первой и последней, различны. Маршрут (4.1) называется цикличе- ским, если a 1 = a n+1 . Циклическая цепь называется циклом, а циклическая простая цепь — простым циклом. Неорграф без циклов называется ацикли- ческим. Минимальная из длин циклов неорграфа называется его обхватом. 130 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Пример 4.3.1. Рассмотрим граф, изображенный на рис. 4.19. В нем на- боры (1, 2), (1, 2, 4, 7), (3, 4, 5, 6) являются простыми цепями; (1, 2, 4, 7, 8, 4) — цепь, не являющаяся простой; (1, 2, 4, 7, 8, 4, 2) — маршрут, не являющийся цепью; (1, 2, 4, 7, 8, 4, 1) — цикл, не являющийся простым; (1, 2, 4, 1) — про- стой цикл. Обхват этого графа равен 3. ¤ Пусть G — граф, возможно, ориентированный. Маршрут (4.1) называется путем, если все его дуги различны. Путь (4.1) называется контуром, если a 1 = a n+1 . Граф, не имеющий контуров, называется бесконтурным. Вершина b называется достижимой из вершины a, если существует (a, b)-путь. Пример 4.3.2. Граф, изображенный на рис. 4.20, • • • • • • • • ¢ ¢ ¢ ¢ ¢ ¢ A A A A A A 1 2 3 4 5 6 7 8 Рис. 4.19 имеет контур (1, 2, 3). Вершина 5 достижима из любой другой вершины, а из вершины 5 не достижима ни одна из вершин. ¤ Неорграф называется связным, если любые две его несовпадающие вершины соединены маршрутом. Орграф G называется связным, если связным является соответствующий ему неорграф F (G). Граф G называ- ется сильно связным, если для каждой пары различных вершин a и b суще- ствуют (a, b)-маршрут и (b, a)-маршрут. Аналогично определяются понятия связности и сильной связности для мультиграфов. Пример 4.3.3. Граф, показанный на рис. 4.19, • • • • • ¾ ¡ ¡ ¡ µ @ @ @ R - - 2 4 5 1 3 Рис. 4.20 является связным, орграф, представленный на рис. 4.20, — связным, но не сильно связным, а граф, изоб- раженный на рис. 4.21, не является связным. ¤ Заметим, что любой связный неорграф является сильно связным. Всякий максимальный по включению (сильно) связный подграф данного графа называется его (сильной) связной компонентой или (сильной) ком- понентой связности. Граф, показанный на рис. 4.21, имеет две компоненты связности с мно- жеством вершин {1, 2, 3, 4} и {5, 6, 7}. Граф, представленный на рис. 4.20, имеет три сильные компоненты, задаваемые множествами вершин {1, 2, 3}, {4} и {5}. 4.3. МАРШРУТЫ. ДОСТИЖИМОСТЬ. СВЯЗНОСТЬ 131 • • • • ©© ©© ©© HH HH HH 1 3 2 4 • • • ¢ ¢ ¢ ¢ ¢ ¢A A A A A A 5 7 6 Рис. 4.21 Теорема 4.3.1. Любой граф представляется в виде объединения непере- секающихся связных (сильных) компонент (с возможным добавлением дуг с концами из разных сильных компонент). Разложение графа на связные (сильные) компоненты определяется однозначно. ¤ Таким образом, множества вершин связных компонент, а также силь- ных компонент образуют разбиение множества вершин графа, а число |