Судопланов. Судоплатов С.В., Овчинникова Е.В. Дискретная математика 2016. Редакционная коллегия серии учебники нгту
 Скачать 2.01 Mb.
|
|
Разрезом графа G (по разбиению M) называется множество всех ребер, соединяющих вершины из M 1 с ¾ ½ » ¼ ¾ ½ » ¼ • • • • • • 6 6 6 Разрез M 1 M 2 Рис. 4.46 вершинами из M 2 (рис. 4.46). Отметим, что в связном графе любой разрез непуст. Непустой разрез K неорграфа G называется про- стым разрезом или коциклом, если любое непустое собственное подмножество K 0 $ K не является разре- зом ни по какому разбиению. Другими словами, из K нельзя удалить ни одно ребро с тем, чтобы полученное множество было непустым разрезом. Теорема 4.12.1. В конечном неорграфе G = hM; Ri, имеющем c ком- понент связности, множество ребер K тогда и только тогда является коциклом, когда граф hM; R \ Ki имеет (c + 1) компонент связности. ¤ Понятия остова и коцикла являются противоположными в том смысле, что остову соответствует минимальное множество ребер, которые связыва- ют посредством маршрутов все вершины связного графа, а коцикл состоит из минимального множества ребер, отделяющего некоторые вершины связ- ного графа от остальных. Следующие две почти очевидные теоремы дают информацию о связи остовов с разрезами, а также циклов с разрезами. Теорема 4.12.2. В связном неорграфе остовное дерево имеет по край- ней мере одно общее ребро с любым из разрезов графа. ¤ Теорема 4.12.3. В связном неорграфе любой цикл имеет с любым раз- резом четное число общих ребер. ¤ В условиях, указанных в предыдущем параграфе, рассмотрим неор- граф G с остовом T . Снова пусть u 1 , u 2 , . . ., u n−c — ветви остова T . Удаляя из остова T произвольную ветвь u i , получаем лес с (c + 1) компонентами связности, т. е. каждое ребро u i является разрезом остова T по некоторому разбиению {M 1 , M 2 } (рис. 4.47). В графе G могут найтись еще какие-то ребра v i 1 , v i 2 , . . ., v i j (являю- щиеся хордами T ), которые соединяют вершины из M 1 и M 2 . Множество 158 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ K i = {u i , v i 1 , . . . , v i j } образует простой разрез, который называется фунда- ментальным разрезом графа G относительно ветви u i остова T . Множе- ство {K 1 , K 2 , . . . , K n−c } всех фундаментальных разрезов графа G называет- ся фундаментальным множеством коциклов графа G относительно осто- ва T . Отметим, что мощность фундаментального множества коциклов не за- висит от выбора остова T и равна корангу ν ∗ (G) = n − c. Аналогично фундаментальным циклам каж- º ¹ · ¸ º ¹ · ¸ • • • • • • • u i M 1 M 2 Рис. 4.47 дому фундаментальному разрезу K i ставится в соответствие вектор b i = (b i1 , . . . , b im ), опре- деляемый по правилу b ij = ( 1, если w j ∈ K i , 0, если w j / ∈ K i . Фундаментальное множество коциклов задает- ся матрицей фундаментальных разрезов K, строки которой являются век- торами b 1 , b 2 , . . ., b ν ∗ (G) : K = b 11 . . . b 1m b 21 . . . b 2m . . . . . . . . . . . . . . . b ν ∗ (G),1 . . . b ν ∗ (G),m . Поскольку каждый фундаментальный разрез K i содержит ровно одну ветвь, а именно u i , матрица K имеет вид K = b 11 . . . b 1,ν ∗ (G) b 21 . . . b 2,ν ∗ (G) . . . . . . . . . . . . . . . . . b ν ∗ (G),1 . . . b ν ∗ (G),ν ∗ (G) ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ 1 0 1 0 1 . Таким образом, K = (K 0 1 |K 0 2 ), где K 0 2 — единичная матрица порядка ν ∗ (G). Отметим, что если C = (C 0 1 |C 0 2 ) — соответствующая матрица фундаменталь- ных циклов, то K 0 1 = (C 0 2 ) T Пример 4.12.1. Найдем матрицу фундаментальных разрезов графа G = = hM; Ri, изображенного на рис. 4.45. Поскольку ν ∗ (G) = 6 − 1 = 5, имеется пять фундаментальных разрезов. Ребру 4 соответствует коцикл K 1 = {1, 4}, 4.13. ВЕКТОРНЫЕ ПРОСТРАНСТВА, СВЯЗАННЫЕ С ГРАФАМИ 159 так как при удалении ребра 4 из остова T множество вершин M разбивается на две части: {a 1 } и M \ {a 1 }, а ребра 1 и 4 образуют разрез по разбиению {{a 1 }, M \ {a}}. Аналогично ребру 5 соответствует коцикл K 2 = {5}, реб- ру 6 — коцикл K 3 = {1, 2, 3, 6}, ребру 7 — коцикл K 4 = {2, 3, 7}, ребру 8 — коцикл K 5 = {3, 8}. Следовательно, матрица фундаментальных разрезов имеет вид K = 1 2 3 4 5 6 7 8 K 1 K 2 K 3 K 4 K 5 1 0 0 0 0 0 1 1 1 0 1 1 0 0 1 ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ ¯ 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 1 . ¤ § 4.13. Векторные пространства, связанные с графами Рассмотрим алгебраическую систему Z 2 = h{0, 1}; ⊕, ¯i с двухместны- ми операциями кольцевого сложения ⊕ и умножения ¯, задаваемыми следу- ющими правилами: 0⊕0 = 1⊕1 = 0, 1⊕0 = 0⊕1 = 1, 0¯0 = 0¯1 = 1¯0 = 0, 1 ¯ 1 = 1. Система Z 2 является булевым кольцом (см. § 2.6) и, более того, образует поле. Пусть G = hM; Ri — связный неорграф, имеющий n вершин и m ребер u 1 , u 2 , . . ., u m . Произвольному множеству ребер A ⊆ R поставим в соответствие вектор a = (a 1 , a 2 , . . . , a m ), положив a i ( 1, если u i ∈ A, 0, если u i / ∈ A. Каждому множеству ребер соответствует единственный вектор, состоящий из нулей и единиц, а для любого набора (a 1 , a 2 , . . . , a m ) нулей и единиц най- дется единственное множество ребер, соответствующее этому набору. Таким образом, существует биекция между булеаном множества ребер R и множе- ством всех наборов длины m, состоящих из нулей и единиц: P(R) ↔ {0, 1} m Пусть a = (a 1 , . . . , a m ) и b = (b 1 , . . . , b m ) — наборы (векторы) из {0, 1} m . Опре- делим сложение векторов с помощью соотношения a⊕b = (a 1 ⊕b 1 , . . . , a m ⊕b m ) по правилам, определенным в поле Z 2 . Кроме этого, определим произведение векторов на элементы λ ∈ {0, 1}, положив λ¯a = (λ¯a 1 , . . . , λ¯a m ). Множе- ство векторов {0, 1} m с операциями сложения ⊕ и умножения ¯ на элементы 160 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ поля Z 2 образует линейное пространство над полем Z 2 . Это пространство обозначим через V m (Z 2 ). Отметим, что сложение ⊕ векторов a и b соответствует кольцевой сумме множеств ребер A и B, представляемых этими векторами. Действительно, равенство a i ⊕ b i = 1 выполняется тогда и только тогда, когда a i = 1, b i = 0 (т. е. u i ∈ A \ B) или a i = 0, b i = 1 (т. е. u i ∈ B \ A). Следовательно, сумме a ⊕ b соответствует множество (A \ B) ∪ (B \ A) = A ⊕ B. Внутреннее произведение векторов a = (a 1 , a 2 , . . . , a m ) и b = (b 1 , b 2 , . . . , b m ) определяется соотношением (a, b) = a 1 ¯ b 1 ⊕ a 2 ¯ b 2 ⊕ . . . ⊕ a m ¯ b m . Равенство (a, b) = 0 означает, что четное число произведений a i ¯ b i равно 1. Для таких произведений a i = 1, b i = 1 и, следовательно, соответствующие векторам a и b множества ребер A и B имеют четное число общих ребер. Множество ребер A называется границей (кограницей), если A есть объ- единение множеств ребер некоторых циклов (коциклов), из которых любые два множества не имеют общих ребер. Нетрудно заметить, что кольцевая сумма A 1 ⊕ A 2 границ (кограниц) A 1 и A 2 также является границей (когра- ницей). Следовательно, множества V Γ = {a | вектор a соответствует некоторой границе}, V K = {b | вектор b соответствует некоторой когранице} образуют линейные подпространства пространства V m (Z 2 ). Теорема 4.13.1. 1. Если {C 1 , C 2 , . . . , C m−n+1 } — фундаментальное мно- жество циклов графа G, то множество B C {a 1 , a 2 , . . . , a m−n+1 } векто- ров, соответствующих фундаментальным циклам, образует базис подпро- странства границ V Γ . 2. Если {K 1 , K 2 , . . . , K n−1 } — фундаментальное множество коциклов графа G, то множество B K = {b 1 , b 2 , . . . , b n−1 } векторов, соответствую- щих фундаментальным разрезам, образует базис подпространства когра- ниц V K . Следствие 4.13.2. 1. Размерность dim V Γ подпространства границ V Γ равна цикломатическому числу ν(G), а размерность dim V K подпростран- ства кограниц V K равна корангу ν ∗ (G). 2. Любой цикл (коцикл) в графе можно представить в виде коль- цевой суммы некоторых фундаментальных циклов (разрезов). 4.14. РАСКРАСКИ ГРАФОВ 161 Два подпространства V 1 и V 2 векторного пространства V m (Z 2 ) называют- ся ортогональными (обозначается V 1 ⊥V 2 ), если для любых векторов a ∈ V 1 и b ∈ V 2 их внутреннее произведение (a, b) равно 0. Заметим, что по теореме 4.12.3 любой цикл C с любым разрезом K име- ет четное число общих ребер, т. е. для соответствующих векторов a и b их внутреннее произведение (a, b) равно нулю. В частности, для любых векто- ров a i ∈ B C и b j ∈ B K справедливо (a, b) = 0. Так как множества B C и B K образуют базисы подпространств V Γ и V K , то V Γ ⊥V K Отметим также, что при умножении матрицы фундаментальных цик- лов C на транспонированную матрицу фундаментальных разрезов K T в поле Z 2 строка a i умножается на столбец b j по правилу внутреннего про- изведения и (a i , b j ) = 0. Это означает, что C · K T = 0, а также K · C T = 0. Упражнение.Проверить, что для матриц C и K из примеров 4.11.1 и 4.12.1 справедливо C · K T = 0. § 4.14. Раскраски графов Пусть G = hM; Ri — неорграф без петель. Раскраской (вершин) графа G называется такое задание цветов вершинам G, что если [a, b] — ребро, то вер- шины a и b имеют различные цвета. Хроматическим числом χ(G) графа G называется минимальное число цветов, требующееся для раскраски G. Пример 4.14.1. Так как в полном графе K n любые две различные вер- шины связаны ребром, то χ(K n ) = n. ¤ Многие практические задачи сводятся к построению раскрасок графов. Пример 4.14.2. 1. Рассмотрим задачу составления расписания. Пред- положим, что нужно прочесть несколько лекций за кратчайшее время. Чте- ние каждой лекции в отдельности занимает один час, но некоторые лекции не могут читаться одновременно (например, их читает один и тот же лек- тор). Построим граф G, вершины которого биективно соответствуют лекци- ям и две вершины смежны тогда и только тогда, когда соответствующие им лекции нельзя читать одновременно. Очевидно, что любая раскраска этого графа определяет допустимое расписание: лекции, соответствующие верши- нам одного цвета, могут читаться одновременно. Напротив, любое допусти- мое расписание определяет раскраску графа G. Оптимальные расписания 162 Глава 4. ЭЛЕМЕНТЫ ТЕОРИИ ГРАФОВ соответствуют раскраскам с минимальным числом цветов, а число часов, необходимое для прочтения всех лекций, равно χ(G). 2. Рассмотрим граф G, вершины которого — страны, а ребра соединяют страны, имеющие общую границу. Числу χ(G) соответствует наименьшее число красок, необходимых для раскраски карты так, чтобы никакие две соседние страны не были окрашены в один цвет. ¤ Существуют и практические задачи, связанные с раскраской ребер в муль- тиграфе. Раскраска ребер в мультиграфе G может быть определена с помощью раскраски вершин так называемого реберного мультиграфа L(G). Для про- извольного неориентированного мультиграфа G = hM, U, P i реберным муль- тиграфом L(G) называется тройка hU, M, P 0 i, где P 0 ⊆ U × M × U, и выпол- няется (u, a, v) ∈ P 0 тогда и только тогда, когда в мультиграфе G вершина a является концом ребер u и v. Раскраской ребер мультиграфа G называется раскраска вершин мультиграфа L(G). Пример 4.14.3. Проводится монтаж аппаратуры. Чтобы не перепутать проводники, необходимо их окрасить таким образом, чтобы два проводни- ка, идущие к одной плате, имели разные цвета. В этом случае вершинами являются платы, а ребрами — проводники. ¤ Неорграф G называется бихроматическим, если χ(G) = 2. Неорграф G = hM; Ri называется двудольным, если множество всех ребер графа G образует разрез графа G, т. е. для некоторого разбиения множества вершин {M 1 , M 2 } концы любого ребра принадлежат разным частям разбиения. Теорема 4.14.1. Пусть G — неорграф без петель, имеющий хотя бы одно ребро. Тогда следующие условия эквивалентны: 1) G — бихроматический граф; 2) G — двудольный граф; 3) G не содержит циклов нечетной длины. ¤ Следствие 4.14.2. Если G — лес, то χ(G) 6 2. ¤ Оценим хроматическое число графа G через его параметры. Обозначим через deg(G) максимальную степень вершин графа G. Теорема 4.14.3. Для любого неорграфа G без петель выполняется нера- венство χ(G) 6 deg(G) + 1. ¤ 4.15. ПЛАНАРНЫЕ ГРАФЫ 163 Рассмотрим простой алгоритм построения раскраски, который во многих случаях приводит к раскраскам, близким к минимальным. Алгоритм последовательной раскраски. 1. Произвольная вершина a 1 графа G принимает цвет 1. 2. Если вершины a 1 , . . . , a i раскрашены l цветами 1, 2, . . . , l, l 6 i, то новой произвольно взятой вершине a |