Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
w ik i из каждой строки, получим матрицу W ∨ = ∞ 11 5 3 0 7 4 ∞ 0 3 1 ∞ 6 2 ∞ 1 4 0 5 8 1 ∞ 0 1 ∞ 5 0 3 ∞ 8 10 0 ∞ 3 7 ∞ . После нахождения наименьших значений по столбцам (4, 0, 0, 1, 0, 0) и вы- читания из каждого столбца матрицы W ∨ соответствующего числа w l i j об- разуется матрица W ∗ = ∞ 11 5 2 0 7 0 ∞ 0 2 1 ∞ 2 2 ∞ 0 4 0 1 8 1 ∞ 0 1 ∞ 5 0 2 ∞ 8 6 0 ∞ 2 7 ∞ . Суммируя элементы w ik i и w i j j , получаем нижнюю оценку h = 14. Так как w 15 = min{w 1i | i = 1, . . . , n}, то множество гамильтоновых циклов разобьем на два множества (1, 5)∅ и (1){5} (рис. 4.40). При рассмотрении множества (1, 5)∅ получаем матрицу весов W 0 = x 2 3 4 6 x 2 3 4 6 ∞ 5 0 2 8 0 ∞ 0 2 ∞ 2 2 ∞ 0 0 1 8 1 ∞ 1 6 0 8 2 ∞ графа G 0 , образованного отождествлением вершин 1 и 5 графа G. Мини- мальные элементы строк матрицы W 0 образуют столбец 0 0 0 1 0 , поэтому (W 0 ) ∨ = ∞ 5 0 2 ∞ 0 ∞ 0 2 ∞ 2 2 ∞ 0 0 0 7 0 ∞ 0 6 0 8 2 ∞ , 4.9. ОБХОДЫ ГРАФА ПО ГЛУБИНЕ И ШИРИНЕ 151 H (1, 5)∅ (1, 5, 3)∅ (1, 5, 3, 4)∅ (1, 5, 3, 4, 6)∅ (1){5} (1, 5){3} (1, 5, 3){4} (1, 5, 3, 4){6} ¡ ¡ ¡ @ @ @ ¡ ¡ ¡ HH HH HH ¡ ¡ ¡ PPP PPP PPPP ¡ ¡ ¡ XXXX XXXX XXXX X 14 ±° ²¯ 15 ±° ²¯ 15 ±° ²¯ 15 ±° ²¯ 15 ±° ²¯ 16 ±° ²¯ 17 ±° ²¯ 17 ±° ²¯ ∞ ±° ²¯ Рис. 4.40 а минимальные элементы столбцов матрицы (W 0 ) ∨ образуют нулевую стро- ку, и значит, (W 0 ) ∗ = (W 0 ) ∨ . Таким образом, оценка h 1 будет равна h + h 0 = = 14 + 1 = 15. Рассматривая множество (1){5}, мы должны в матрице W ∗ заменить эле- мент w ∗ 15 = 0 на ∞. Тогда оценка h 2 будет h + h 0 = 14 + 2 = 16. Поскольку h 1 < h 2 , выбираем множество (1, 5)∅ и соответствующую мат- рицу весов (W 0 ) ∗ . Теперь в силу того, что (w ∗ ) x3 = 0, разобьем множе- ство гамильтоновых циклов из множества (1, 5)∅ на множества (1, 5, 3)∅ и (1, 5){3} (рис. 4.40). Рассматривая случай (1, 5, 3)∅, получаем матрицу ве- сов W 00 = x 2 4 6 x 2 4 6 ∞ 2 0 0 0 ∞ 2 ∞ 0 7 ∞ 0 6 0 2 ∞ графа G 00 , образованного отождествлением вершин x и 3 графа G 0 . Оценка h 11 равна 15, а (W 00 ) ∗ = W 00 . При рассмотрении множества (1, 5){3} в матрице (W 0 ) ∗ заменяем элемент (w 0 ) ∗ 23 = 0 на ∞ и получаем оценку h 12 = h 1 +2 = 17. 152 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Так как h 11 < h 12 , выберем множество (1, 5, 3)∅ с матрицей ве- сов (W 00 ) ∗ = W 00 . Поскольку (W 00 ) ∗ x4 = 0, рассмотрим множества циклов (1, 5, 3, 4)∅ и (1, 5, 3){4}. Для оценивания весов в множестве (1, 5, 3, 4)∅ отож- дествим вершины x и 4 в графе G 00 и получим граф G 000 с матрицей весов W 000 = x 2 6 x 2 6 ∞ 7 0 0 ∞ ∞ 6 0 ∞ . Очевидно, что h 111 = h 11 = 15, а (W 000 ) ∗ = W 000 . Рассматривая случай (1, 5, 3){4}, заменяем в матрице (W 00 ) ∗ элемент (w 00 ) ∗ x4 = 0 на ∞ и получаем оценку h 112 = h 11 + 2 = 17. Так как h 111 < h 112 , то переходим к рассмотрению множества (1, 5, 3, 4)∅, состоящего из двух гамильтоновых циклов (1, 5, 3, 4, 2, 6, 1) и (1, 5, 3, 4, 6, 2, 1). Первый из этих циклов будет иметь вес ∞, поскольку (W 000 ) 26 = ∞, а вес второго цикла 15, что соответствует оценке h 111 = 15. Поскольку оценки h 2 , h 12 и h 112 больше h 111 , соответствующие множества не содержат гамиль- тонова цикла веса, меньшего 15, и поэтому цикл (1, 5, 3, 4, 6, 2, 1) является гамильтоновым циклом минимального веса. § 4.10. Упорядоченные и бинарные деревья Определим по индукции понятие упорядоченного дерева: 1) пустое множество и список (a), где a — некоторый элемент, является упорядоченным деревом; 2) если T 1 , T 2 , . . . , T n — непустые упорядоченные деревья, a — некоторый новый элемент, то список T = (a, T 1 , T 2 , . . . , T n ) есть упорядоченное дерево. При этом элемент a называется корнем упорядоченного дерева T ; 3) любое упорядоченное дерево строится в соответствии с пп. 1 и 2. Если T 1 , T 2 , . . . , T n — упорядоченные деревья, то список (T 1 , T 2 , . . . , T n ) называется упорядоченным лесом. Для заданного упорядоченного дерева T определим множество S(T ) его упорядоченных поддеревьев: • если T = ∅, то S(T ) = ∅; • если T = (a), то S(T ) = {(a)}; • если T = (a, T 1 , T 2 , . . . , T n ), то S(T ) = S(T 1 ) ∪ . . . ∪ S(T n ) ∪ {T }. 4.10. УПОРЯДОЧЕННЫЕ И БИНАРНЫЕ ДЕРЕВЬЯ 153 ' & $ % 1 ' & $ % 2 ' & $ % 3 µ´ ¶³ 4 µ´ ¶³ 5 ¶ µ ³ ´ 6 µ´ ¶³ 7 ±° ²¯ 8 ±° ²¯ 9 1 2 4 5 3 6 8 9 7 Рис. 4.41 Рис. 4.42 Непустое упорядоченное дерево T может интерпретироваться в виде си- стемы пронумерованных непустых множеств, каждое из которых взаимно однозначно соответствует упорядоченному поддереву из S(T ) так, что: 1) если T 0 — поддерево упорядоченного дерева T 00 , T 0 , T 00 ∈ S(T ), то для соответствующих множеств X 0 и X 00 выполняется включение X 0 ⊆ X 00 ; 2) если T 0 не является поддеревом упорядоченного дерева T 00 и T 00 не яв- ляется поддеревом упорядоченного дерева T 0 (где T 0 , T 00 ∈ S(T )), то соответ- ствующие множества не пересекаются. Пример 4.10.1. Упорядоченному дереву (1, (2, (4), (5)), (3, (6, (8), (9)), (7))) соответствует система множеств, изображенная на рис. 4.41. ¤ Упорядоченное дерево может также интерпретироваться в виде так называемого уступчатого списка, который используется в оглавлениях. На рис. 4.42 представлен уступчатый список, соответствующий упорядочен- ному списку из примера 4.10.1. Согласно следующему тезису любая схема, в которой заданы определен- ные приоритеты между элементами, может рассматриваться как некоторое упорядоченное дерево. Тезис. Любая иерархическая классификационная схема интерпретиру- ется некоторым упорядоченным деревом. 154 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Например, в виде упорядоченного дерева представляется любой терм. На рис. 4.43 изображено упорядоченное дерево, соответствующее терму t = a − b · (c : d + e : f ). Частным случаем упорядоченного дерева является бинарное дерево. дерево. Определение бинарного дерева повторяет k − k a k × k b k + k : k : k c k d k e k f ¡ ¡ @ @ ¡ ¡ @ @ @ @ @ @ @ @ ¡ ¡ ¡ ¡ © © © © Рис. 4.43 определение для упорядоченного дерева с ограни- чением n ∈ {0, 1, 2} в п. 2. При этом для бинарного дерева T = ((a), T 1 , T 2 ), бинарное под- дерево T 1 называется левым поддеревом, а T 2 — правым поддеревом. Бинарные деревья имеют более простое устрой- ство, чем упорядоченные, и вместе с тем любой упорядоченный лес взаимно однозначно соответ- ствует некоторому бинарному дереву. Опишем алгоритм преобразования упорядоченного леса T = (T 1 , T 2 , . . . , T n ) в бинарное дерево B(T ). 1. Если n = 0, B(T ) ∅. 2. Если n > 0, то корнем бинарного дерева B(T ) является корень a 1 упорядоченного дерева T 1 , левое поддерево дерева B(T ) — бинарное дерево B(T 11 , T 12 , . . ., T 1m ), где T 1 = (a 1 , T 11 , T 12 , . . . , T 1m ), правое поддерево дере- ва B(T ) — бинарное дерево B(T 2 , . . . , T n ). На рис 4.44б представлено бинарное дерево, соответствующее упорядо- ченному лесу (T 1 , T 2 ), изображенному на рис 4.44а. A µ´ ¶³ B µ´ ¶³ C µ´ ¶³ H µ´ ¶³ ¡ ¡ ¡ @ @ @ D µ´ ¶³ E µ´ ¶³ I µ´ ¶³ F µ´ ¶³ J µ´ ¶³ G µ´ ¶³ ¡ ¡ ¡ @ @ @ A µ´ ¶³ B µ´ ¶³ C µ´ ¶³ H µ´ ¶³ E µ´ ¶³ I µ´ ¶³ D µ´ ¶³ F µ´ ¶³ J µ´ ¶³ G µ´ ¶³ ¡ ¡ ¡ ª - ? - ¡ ¡ ¡ ª ? - ? - а б Рис. 4.44 4.11. ФУНДАМЕНТАЛЬНЫЕ ЦИКЛЫ 155 § 4.11. Фундаментальные циклы Пусть G = hM; Ri — неорграф, имеющий n вершин, m ребер и c ком- понент связности, T — остов графа G. В § 4.8 отмечалось, что T имеет ν ∗ (G) = n − c ребер u 1 , . . . , u n−c , которые будем называть ветвями остова T . Оставшиеся m − n + c ребер v 1 , v 2 , . . . , v m−n+c , не входящие в T , будем называть хордами остова T . Согласно теореме 4.8.1, п. 5, если к лесу T до- бавить произвольную хорду v i , то в полученном графе найдется ровно один цикл, который обозначим через C i . Цикл C i состоит из хорды v i и некоторых ветвей остова T , которые принадлежат единственной простой цепи, соеди- няющей вершины хорды v i . Цикл C i называется фундаментальным циклом графа G относительно хорды v i остова T . Множество {C 1 , . . . , C m−n+c } всех фундаментальных циклов относительно хорд остова T называется фун- даментальным множеством циклов графа G относительно остова T . От- метим, что мощность фундаментального множества циклов равна циклома- тическому числу ν(G) = m − n + c. Обозначим через (w 1 , w 2 , . . . , w m ) последовательность (v 1 , v 2 , . . . , v m−n+c , u 1 , u 2 , . . . , u n−c ) всех ребер графа G. Тогда фундаментальному циклу C i соответствует вектор a = (a i1 , . . . , a im ), определенный по следующему правилу: a ij = ( 1, если w j ∈ C i , 0, если w j / ∈ C i . Теперь фундаментальное множество циклов можно задать с помо- щью матрицы фундаментальных циклов, строки которой являются векторами a 1 , a 2 , . . . , a ν(G) : C a 11 a 12 . . . a 1m a 21 a 22 . . . a 2m . . . . . . . . . . . . . . . . . . . a ν(G),1 a ν(G),2 . . . a ν(G),m . 156 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ Так как каждый фундаментальный цикл C i содержит ровно одну хорду, а именно v i , то матрица C имеет вид C = 1 0 1 0 1 ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ a 1,ν(G)+1 . . . a 1m a 2,ν(G)+1 . . . a 2m . . . . . . . . . . . . . . . . . a ν(G),ν(G)+1 . . . a ν(G)m . Таким образом, C = (C 0 1 |C 0 2 ), где C 0 1 — единичная матрица порядка ν(G). Пример 4.11.1. Найдем матрицу фундаментальных циклов графа G, изображенного на рис. 4.45. Так как ν(G) = 8− • • • • • • @ @ @ @ @ @ 1 2 3 4 5 6 7 8 Рис. 4.45 − 6 + 1 = 3, то для получения остова удаляем из графа три ребра. Сопоставим этим ребрам номера 1, 2, 3. Ребрам, входящим в остов, поставим в со- ответствие номера 4, 5, 6, 7, 8. Легко видеть, что фундаментальный цикл C 1 , соответствую- щий хорде 1, состоит из ребер 1, 4, 6, цикл C 2 — из ребер 2, 6, 7, цикл C 3 — из ребер 3, 6, 7, 8. Поэтому матрица фундаментальных циклов C имеет вид C = 1 2 3 4 5 6 7 8 C 1 C 2 C 3 1 0 0 0 1 0 0 0 1 ¯ ¯ ¯ ¯ ¯ ¯ 1 0 1 0 0 0 0 1 1 0 0 0 1 1 1 . ¤ § 4.12. Разрезы Понятие разреза играет важную роль при изучении вопросов, связанных с отделением одного множества вершин графа от другого. Такие задачи воз- никают, например, при изучении потоков в сетях (сетью называется связ- ный орграф G = hM; Ri без петель; потоком в сети G называется функция ϕ: R → Z, которая ставит в соответствие дуге некоторое число — вес ду- ги). В этих задачах фундаментальную роль играют изучение поперечных сечений сети (т. е. множеств дуг, которые соединяют вершины двух непе- ресекающихся множеств вершин) и нахождение ограниченного поперечного |