Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 36
Текст из файла (страница 36)
Усшобчиаосшь, лонрмшил, ларосочгшанил 193 ребра. Повторяя такое разложение графа до получения неакрестностей, равных ж, порождаем все реберно независимые множества (рис. 3.19): Ег —— (Ь,ь,л), Ез=(3,ь,л), Ез=(с,ь,л), Е,=(а,с,Ц, Ез=(а,е,Ц, Ез=(а,е,Ц, Етш(Ь,'У,'р),' Езю И,'У,р),' Ез =(с, У,Р), Его=(Ае, У), Ем=(е,1 ш), Егз=(Ь,У,ш), Езз=(а,с,р), Егь=(а,е,ш), Егя = (Ь, гл, л). Пакрывая строки'столбпами модифицированной матрицы смежности ребер л! лт лз пя л5 из д'т лз лз л!е лн !2 л!3 !4 ~15 Рнс.
3.19 195 $3.6, Вложение графов Гл.З. Теория графов и мографов 194 аалаинага графа тс й у «т а О 1 О 1 О О О О О О 1 О О О 1 О О О О 1 1 1 1 О 1 1 О 1 1 О 1 О О 1 О 1 1 О 1 О ь с г 1 1 О 1 О 1 1 1 1 1 О 1 1 1 1 1 1 1 1 О О 1 1 О 1 О О О О О 1 О О О О О О 1 1 О 1 О О О 1 О О О О 1 О Ь с с с Ь т' ет и р тут(сс) графа С равно 3: б Рис. 3.2О Рис. 3.22 Рис.
3.21 получаем, чга ребернее числе внелтией устойчивости )(Ь, пт, пЯ са 3, 3 3.6. Вложение графов Рассмотрим топологические свойства графов. Топология исследует свойства графов, инвариантные относительно гомеоморфных преобразований. Эти свойства определяются топологическими инвариантами. Два графа гомеоморфкы, если они изоморфны с точностью до вершин степени 2. Другими словами, два графа гомеоморфны, если они преобразуются до графов, изоморфных друг другу, заменой некоторых ребер цепями соответствующей длины.
Рад повергкоспти — это наибольшее число простых замкнутых кривых на поверхности, которые не разъединяют зту поверхность. Сфера и плоскость являются поверхностямн нулевого рода, поскольку нх разъединяет любая замкнутая кривая. Тор — поверхность первого рода. Любая поверхность р-го рода эквивалентна сфере с р ручками. Род графа 7(С) — зто минимальный род среди всех поверхностей, на которых граф С можно изобразить так, чтобы его ребра пересекались только в вершинах. Граф называется планаркым, если изображается на плоскости так, что его ребра пересекаются только в вершинах. Проблема характеризацни планарных графов долгое время оставалась нерешенной.
В 1927 г. Л.С. Понтрягин доказал (но не опубликовал) критерий планарности, который независимо от него был открыт и опубликован польским математиком Куратовским в 1930 г. Теорема 3.18 (Л.С. Понтрягин). Граф планарен тогда и тполько тогда, когда он не содержитп подграфц гомеоморфного Ра или Кз,з (рис. 3.20). Основываясь на критерии Понтрягина, можно получить еше опкн критерий иланарности, если ввести понятие элементарного стлгивакил, которое состоит в следующем. При стягивании любого ребра графа оно выбрасывается, а обе его вершины а и Ь (рис. 3.21), коинцидентные ему, отождествляются; полученная при атом вершина коинцидентна тем же ребрам, что и а, Ь (кроме ребра, которое выброшено). Теорема 3.19.
Граф планарен тогда и игольно тогда, когда ок ке содержит подграфов, стплгиваемых к Ра или к Кз 3. В 1932 г. американец Уитни ввел еше один критерий планар- ности, использовав понятие абстрактной двойственности графа. Граф С' называется абстпрактно двойственным к С, если между ребрами графов С и С' существует взаимно однозначное соответ- ствие; подмножеству ребер из С, образующих цикл в С, соответствует подмножество ребер из С', образующих разрез в С'.
Если С содержит висячую вершину щ г(о) = 1, то в С' получается петля. На рис. 3.22 изображены графы С и С', причем граф С изображен штриховыми линиями. Теорем а 3.20 (Уитни). 1 риф лвллетпся плакаркым тпогда и только тпогда, когда сущгстпвует абстрактна двойственный к нему граф.
197 3 3.6. Вложение графов Гл.З. Теория графов и могрофов 196 Рис. 3.24 Р .З2З Рассмотрим задачу, возникшую при проектировании печатной схемы. При изготовлении электронных приборов соединительные провода наносят печатным способом на плоскую поверхность изо.
ляционного материала. Печатные проводники не изолированы, поэтому они не должны пересекаться. Однако расположение приборов на плате может быть таким,' что невозможно избежать пересечения, поэтому, чтобы правильно спроектировать печатную схему, надо знать, является ли граф, в котором роль вершин играют приборы, а ребрами служат соединения между ними, планарным. Если граф непланарный, то печать должна проводиться на нескольких плоскостях и необходимо знать либо число скрещивзний графа (наименьшее возможное число пересечений при изображении его на плоскости), либо его толщину.
Толщиной графа С называется наименьшее число планзрных графов, объединение которых лает сг. Толщина планарнаго графа равна 1. Нижняя оценка толщины г(О) графа О = (У, Н), определяется неравенством а 2;3; — 2 1(С) > 1+ 6(я — 2) (3.16) где [ — целан часть, (У~ = а, в; — степень г'-й вершины. ассмотрим граф, изображенный на рис. 3.23, о.
Определим, можно ли осуществить однослойную печать, и если нет, то вы- ясним, сколько потребуется слоев и какие ребра следует удалить, чтобы граф стал плоским. Согласно критерию Понтрягина этот граф является непланарным, поскольку содержит подграфы, гомеоморфные Еб (рис. 3.24, а) и Кз з (рис. 3.24, б).
Толщина графа С ие меньше 2: 1(0) > 1+ = 2, 1(0) > 2. 32 — 2 6(7 — 2) Чтобы определить, какие ребра необходимо удалить для преобразования графа в пленарный, выделим все запрещенные фи- гуры и построим двумерную таблицу, каждая строка которой взаимно однозначно соответствует запрещенной фигуре Щ, а столбец — ребру р . Тогда покрытие строк столбцами этой таблицы апределит, какйе ребра необходимо удалить, чтобы граф стал пла- парным.
Минимальное покрытие будет соответствовать минимальному решению, так как удаление любога ребра выводит запрещениУю фигУРУ из класса подгРзфов, гамеомаРфных Рб или'Кз,з. Таблица для рассматриваемого графа имеет следующий вид: Таблица 31 Минимальное покрытие содержит одно из ребер (2, 3), (2, 4), еб, 61, (3, 7), (4, 6~, (4, 5) нли (5, 7~. После удаления, например, ребра (3, 61 получаем планарный граф, плоское представление коцорого изображено на рис.
3.23,б. Соединение, которое соответствует удаленному ребру (покззано штриховой линией), реализуется на второй плоскости. Толщина 1(С) графа 0 равна 2. Большой практический интерес представляет проблема вложения графов в другие графы, имеющие специальные структуржые свойства. Важным классом таких графов является класс и мерных кубов. Они находят применение в теории кодирования при передаче данных и при проектировании автоматов.
Обозначим я-мерный куб через Н„. Мощность его носителя равна 2", мощность сигнатуры — я 2" '. Введем метрику на графе Н„следующим образам. Пусть неотрицательная функция от двух переменных Н(о, 6) определяет расстояние между двумя вершинами а, 6 6 Н„, равное числу ребер в кратчайшей простой цепи, соединяющей а и 6. При этом выполняются следтющие условия: 1) Ы(а, о ) = О тогда и только тогда, когда вершины о, и а' совпадают; 199 Гл.3.
Теория г афов и могрвфов 13.6, Вложение графов 198 2) И(а, Ь) = И(Ь, а); ,) 3 И(а, Ь) + д(Ь, с) > д(а, с) для любых а, Ь, с Е Н„. ледовательно, множества вершин и-куба вместе с введенной таким образом метрикой, является метрическим пространством, которое назовем булевым пространством. Если метрика введена в данное множество, то она введена и в любое его подмножество как ограничение функции И.
Поэтому всякий подграф и-куба также есть метрическое пространство. Рассмотрим задачу вложения графа ся в булеза пространство Н„. Граф >я = (У, Ц называется вложимым в булгво пространство Н„= (Ун, Но) или кубируемым, если существует соответствие у> между вершинами графа ся и гиперкуба Н„такое, что если (о, од) к Н, то (9>(о ), у(од)) к Уо. Кубируемый граф не следует путать с кубическим графом — графом, каждая вершина которого имеет степень, равную 3. Так как и-куб является двудольным графом, то в соответствии с теоремой Кенига все его простые циклы четны, и поэтому любой граф, который содержит лодграф, являющийся нечетным циклом, некубируем. Так как п-куб изоморфен дистрибутивной решетке, то граф Кеннга Кэ,з (рис. 3.25) также является некубируемым графом. Любой же частичный граф цикла нечетной длины и граф Кт,з вложимы в булеза пространство.
Следовательно, циклы нечетной длины и граф Кенига Кхэ являются запрещенными фигурами вложения графа в булево пространство. Под эапрещенной фигурой в данном случае понимаем критически певложимый граф, т. е. некубируемый граф, у которого все частичные графы кубируемые. Рассмотрим процедуры порождения запрещенных фигур на основе известных. Теорема 3.21 (Грехем). Зангна ребра р в грани эапрещенной фигуры Я на граф Кенига Кт з беэ этого ребра р, т. е.
на Кт з1р, порождает новуюэапрещенную формулуТ>(ф (рис. 3 26). Порождение запрещенных фигур вложения графов в булево пространство с помощью процедуры Грехема (теорема 3.21) показано на рис. 3.27. Характеризация кубируемых графов достаточно сложна из-за трудностей, возникающих при анализе этих комбинаторных структур. Для тога чтобы определить причины, мешающие графу быть кубируемым, надо выявить его структурные свойства, сформулировав, например, условия, описывающие взаимосвязь между его параметрами, которые несут информацию об этих причинах. Рассмотрим некоторые свойства п-куба, влияющие на структуру запрещенных фигур. Максимальная длина цепи, соединяю- шей две вершины о, о>> п-куба, равна 2" -' 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
