Cтраница 3
Если при разбиении графа на цикл и связные компоненты среди полученных подмножеств ребер встречаются соединения, относящиеся ко второму случаю, то их необходимо свести к одному из видов первого случая, что выполняется формально по матрице смежности путем удлинения выбранного цикла. Если указанную операцию не выполнить, то в дальнейших преобразованиях из рассмотрения выпадает по крайней мере одно из ребер, которое могло бы влиять на планарность графа. [31]
В этой главе приведены все известные критерии планарности. В их число входят теоремы Понтрягина - Куратовского и Вагнера, в которых пленарные графы характеризуются в терминах запрещенных подграфов; результат Уитни о связи планарности графа с существованием комбинаторно двойственного графа; данное Мак-Лейном описание планарности, в котором используется циклическая структура графа. [32]
Вводится понятие числа планарности. Приводятся приближенные оценки числа планарных и непла-нарных графов. Рассматривается методика определения планарности графа схемы цифрового автомата. Если граф планарен, то получается его плоская реализация, в противном случае выполняется декомпозиция графа на плоские подграфы. Излагается метод разбиения графа на плоские суграфы с использованием внутренне устойчивых множеств. Приведены ЛЯПАС-программы основных алгоритмов. [33]
Однако при исследовании планарности G при условии отсутствия перекрещивающихся цепей с помощью ЭВМ проще сначала одним из описанных алгоритмов проверить, планарен ли граф G, и затем, в случае положительного ответа, проанализировать планарность графа ДО. [34]
Таким образом, для некоторых NP-свойств их отрицания тоже являются NP-свойствами. Такое NP-свойство называется хорошо характеризованным, а теорема: устанавливающая эквивалентность какого-либо NP-свойства отрицанию другого NP-свойства, называется хорошей характе-ризацией второго свойства. Известно немало хороших характеризаций и в самой теории графов, и вне ее. Теорема Понтрягина - Куратовского является хорошей характеризацией планарности графа; теорема Кенига дает хорошую характеризацию двудольных графов; теорема Эйлера есть хорошая характеризация графов, обладающих эйлеровым циклом; в этой книге многие теоремы являются хорошими характеризациями различных других свойств. В действительности, ведущим побуждающим принципом в наших изысканиях будет поиск хороших характеризаций всюду, где только возможно. [35]
Бадер [169] определяет планарность графа схемы, когда задан гамильтонов цикл и когда неизвестно его существование. В работе схема представляется графом, у которого вершины соответствуют контактам схемы, а ребра - проводникам. Если задан гамильтонов цикл графа, то в этом случае ребра гамильтонова цикла располагаются таким образом, чтобы он разбивал плоскость на две области - внутреннюю и внешнюю. Строится граф пересечений путем отождествления ребер графа внутри ГЦ вершинам графа пересечений. Далее проверяется, содержит ли граф пересечений циклы нечетной длины, и если содержит, то исходный граф непланарен. Если неизвестно существование ГЦ, то в этом случае граф разбивается на такое число подграфов, чтобы в каждом существовал ГЦ. Если все подграфы планарны, то проверяется планарность подграфов совместно друг с другом и делается заключение о планарности графа. [36]