52. Планарные графы. Критерий планарности.
Говорят, что граф G укладывается на плоскости, т. е. является планарным, или плоским, если его можно нарисовать так, что его ребра будут пересекаться лишь в концевых точках – вершинах. Изображение планарного графа на плоскости называется планарной укладкой.
Рис. 1.24. Примеры планарного и непланарных графов: а — планарная укладка с непрямолинейными ребрами; б — планарная укладка того же графа с прямолинейными ребрами; в — непланарный граф K5;
г — непланарный граф K3,3
Теорема. Граф планарен тогда и только тогда, когда он не содержит в качестве подграфа графа 
или
.До появления этой теоремы определение планарности графа считалось одной из труднейших задач теории графов.
На рис. 1.25 приведен непланарный граф Петерсена.
Рис. 1.25. Непланарность графа Петерсена:
а — граф Петерсена; б — граф Петерсена, стянутый к K5; в — один из подграфов графа Петерсена, гомеоморфный K3,3
Граф Петерсена не имеет подграфов, гомеоморфных K5, но легко стягивается к K5. Сложнее увидеть, что граф Петерсена имеет подграф, гомеоморфный K3,3.
53. Теорема Куратовского-Понтрягина. Граф Петерсена.
Доказательство: необходимости. С геометрической точки зрения, добавление вершины степени 2 — это добавление точки на ребре, а стирание такой вершины объединяет два ребра с общим концом в одно.
Очевидно, что любая из этих операций, примененная к плоскому графу, снова даст плоский граф. Значит, по следствиям из теоремы Эйлера, никакой плоский (а следовательно, и планарный) граф не гомеоморфен графам K5 и K3,3. С учетом замечания о непланарных подграфах, необходимость доказана.
Граф Петерсена
54.Двухполюсные сети. Параллельно-последовательные сети. Поток в сети.
Опр. (k,l) – полюсником называется сеть имеющая k+l полюсов разбитых на два класса: k-входных полюсов, l – выходных полюсов.
(1,1)-полюсник называется двухполюсной сетью.
Цепью называют простую цепь между полюсами сети(S). 
– входной, выходной полюс. Полюсные ребра-Z.
Сеть состоящая из n параллельных ребер, соединяющих полюса 
обозначается через
.
Сеть, которая может быть получена из сетей 
и
применением конечного числа операций подстановки сети вместо ребра называетсяпараллельно-последовательной сетью.
Опр. Сетью называется связный ориентированный граф G(V, E) без петель с выделенными вершинами 
истоком и 
стоком, причем каждой дуге поставлено в соответствие некоторое натуральное число 
–пропускная способность дуги.
Пропускная способность дуги характеризует максимальное количество вещества, которое может пропустить за единицу времени дуга 
. Договоримся на сети пропускную способность дуги записывать в круглых скобках.
Поток в сети определяет способ пересылки некоторых объектов из одной вершины графа в другую по направлению дуги. Число объектов (количество вещества) 
, пересылаемых вдоль дуги
, не может превышать пропускной способности
этой дуги:
. Будем считать, что если существует дуга из
в
, то нет дуги из
в
. Таким образом, рассматривается поток вещества только в одну сторону.
Алгоритм определения планарности графа Текст научной статьи по специальности «Математика»
Текст научной работы на тему «Алгоритм определения планарности графа»
Материалы Всероссийской конференции “Интеллектуальные САПР-96”
поле, и по одной подзадаче для размещения элементов внутри каждого блока. Эффективность данного метода распределения является высокой, поскольку все подзадачи (кроме размещающей блоки, которую необходимо решить предварительно) являются независимыми, следовательно, отсутствует необходимость во взаимном обмене данными и синхронизации выполнения. Основным критерием, предъявляемым к алгоритму распределения, с точки зрения скорости решения всей задачи, в целом, является обеспечение максимально близких друг к другу времен решения всех подзадач.
При использовании итерационного подхода объектом распределения являются отдельные итерации. Задачей алгоритма распределения является генерация исходных параметров некоторого итерационного шага на основании результатов предыдущих шагов, распределяемые же фрагменты задачи выполняют оценку и улучшение исходных параметров соответствующей итерации. Следует отметить, что здесь, в отличие от блочно — иерархического подхода, процесс распределения идет непрерывно в течение всего времени решения задачи. Важной является проблема объединения результатов, полученных при параллельном выполнении некоторых итераций. С этой точки зрения представляется перспективным использование распределенной обработки применительно к генетическим и эволюционным методам.
Безусловно, оба эти подхода могут использоваться совместно, так, подзадачи, полученные на основе блочно иерархического метода, в свою очередь оказываются распределенными по отдельным итерациям. Аналогично каждая итерация может быть выполнена с использованием блочно иерархического распределения. В целом распределенное решение задачи размещения представляется высокоэффективным как с точки зрения времени выполнения, так и с точки зрения оптимальности использования вычислительных ресурсов.
Для задачи трассировки основным методом распределения также является блочно иерархический, однако общая эффективность распределенной трассировки представляется не столь высокой, как для задачи размещения. Это в первую очередь связано с тем, что необходимо учитывать взаимовлияние блоков на их границах, приводящее к высоким объемам информации, передаваемым по сети от одной подзадачи к другой. Улучшить эффективность распределенной трассировки можно посредством использования алгоритмов, ориентированных на макродискреты, либо методов анализа структуры исходной задачи, таких, как выделение изоморфных компонент.
Таким образом, использование распределенных методов позволит существенно ускорить решение задач конструкторского проектирования ЭВА посредством минимальных затрат.
Л. А. Гладков Алгоритм определения планарности графа
Задача определения планарности графа относится к числу важнейших задач САПР и состоит в нахождении такого представления графа, при котором ребра рассматриваемого графа не пересекаются между собой. Идея описываемого алгоритма определения планарности графов базируется на известном принципе Харари [1]. Согласно этому принципу, граф в планарен в том случае, когда можно выделить к — циклов, таких, что любое ребро графа принадлежит одновременно двум и только двум циклам из выделенного множества. Тогда алгоритм определения планарности графа в заключается в выделении из матрицы всех возможных циклов графа(Вгш) субматрицы(Вг1) такой, что количество строк
подматрицы Вг1 равно ш — п + 2, где ш — число ребер ,а п — число вершин графа С; и каждое ребро графа в принадлежит одновременно двум и только двум строкам субматрицы Вг1 [2,3].
Сложность задачи состоит помимо прочего в том, что прежде чем перейти собственно к определению планарности необходимо сформировать матрицу всех Циклов, что подразумевает собой полный перебор всех возможных путей в графе. В силу этого при увеличении размерности графа (п > 40) наблюдается резкий рост ВСА.
В настоящей статье предложен ряд эвристик, позволяющих если не исключить, то по крайней мере значительно уменьшить вероятность полного перебора.
Остановимся более подробно на предлагаемом алгоритме.
Прежде, чем приступить к формированию матрицы циклов, мы производим нумерацию всех ребер графа. После чего формируется список смежности, где число столбцов соответствует числу вершин графа, число строк — локальным степеням вершин графа, а элементы матрицы представляют собой номера вершин графа, инцидентных вершине с номером, соответствующим номеру текущего столбца. В такой матрице выбирается столбец с максимальным количеством строк(при наличии столбцов с равным количеством строк — любой из них) и с этого столбца начинается процесс генерации циклов к той длины. В рабочем столбце выбирается первая вершина, после чего мы переходим к столбцу с номером, соответствующим номеру текущей вершины. При этом не рассматриваются уже задействованные на предыдущих шагах вершины, а также, до достижения к • того шага, начальная вершина хО. При достижении к • той вершины алгоритм проверяет возможность замыкания цикла, т.е. наличие связи между вершинами хк и хО. В случае, если на любом из шагов обнаруживается невозможность дальнейшего наращивания(замыкания), алгоритм возвращается на один шаг назад и просматривает другие возможности для выбора пути. Таким образом, формируется некоторое множество циклов, представляющих собой цепочки вида хО — х1 — х2 хк — хО. После того, как просмотрены все возможности и сформированы все циклы, использующие вершину хО в качестве начальной, из исходного списка удаляется текущий столбец, а также из всех столбцов списка удаляются вершины, соответствующие номеру текущего столбца, после чего процесс потеряется. Причем, для того чтобы избежать повторной генерации одинаковых циклов, Достаточно в процессе работы алгоритма отслеживать вторую и к-тую позиции формируемых цепочек. Для этих целей необходимо, чтобы вершины участвующие в уже сформированных циклах, на к-той позиции, не были задействованы при дальнейшей генерации на второй позиции. Вершины, использовавшиеся в процессе генерации на к той позиции и не приведшие к замыканию цикла, могут заноситься в отдельный список и в дальнейшем исключаться из рассмотрения в качестве варианта для заполнения к — той позиции, что позволяет сократить число просматриваемых вариантов.
После того, как в результате работы алгоритма сформированы все возможные Циклы длины к, они заносятся в матрицу Вгш. Далее происходит проверка полученной информации. Данный процесс для краткости можно записать в виде следующего словесного алгоритма:
1. Подсчет числа строк г и числа единиц х в каждом столбце матрицы Вт.
2. В случае, если выполняется условие: г^т-п + 2их^2, то переход к п.З, если нет, то запускается процесс генерации циклов длины к + 1.
3. В матрице Впв выделяются столбцы, содержащие точно две единицы.
4. Сформированный таким образом базис циклов Вм проверяется на наличие столбцов с числом единиц х > 2. Если условие выполняется, то запускается процесс генерации циклов длины к + 1, если нет, то переход к п.5.
5. Рассматриваемый базис Вм проверяется на предмет выполнения условия г = т — п + 2. Если условие выполняется, то переход к п.7, если нет, то переход к п.б.
6. Происходит последовательный перебор циклов, записанных в матрице Вт, но не вошедших в формируемый базис Вм на предмет дополнения базиса ВГ| до г, при соблюдении условия х = 2. В случае выполнения данной задачи — переход к п.7, в противном случае запускается процесс генерации циклов длины к + 1.
7. Исходный граф планарен, работа алгоритма завершена.
Проиллюстрируем работу описанного алгоритма на примере.
Пусть задана ма1рица смежности произвольного графа <2(рис.1), причем в случае наличия ребра между вершинами XI — Х| на пересечении 1 — той строки и ) -того столбца ставится не единица, как в обычной матрице смежности, а номер данного ребра.
Прежде чем начать проверку планарности исходного графа, сформируем матрицу всех возможных циклов. На первом этапе это циклы длины три. Для этого с помощью матрицы смежности формируется список смежности(рис.2). Как видно из сформированного списка смежности, максимальную локальную степень р(в) = б имеют сразу две вершины. Это вершины Х| и хз. Выберем в качестве исходной вершины для начала процесса генерации циклов вершину хь
Затем по списку смежности выбираем первую вершину из столбца с номером
1. Это будет вершина 2. Теперь переходим к столбцу 2. Первая вершина во втором столбце это вершина один. Но поскольку она уже используется в качестве начальной, выбираем следующую вершину и переходим к столбцу 3.
Так как нам нужно построить цикл длины три, то проверяем возможность замыкания цикла. Такая возможность имеется, следовательно, сформирован первый цикл длины три: хі — хг — хз — хі.
После этого возвращаемся на шаг назад к вершине Х2 и проверяем возможность построения других циклов длины три с использованием уже имеющихся двух вершин и так далее до построения всех циклов длины три.
Проверка планарности графа
Проверка планарности графа — это проверка возможности отображения данного графа на плоскости без пересечения ребер.
Введение
Проблема определения планарности графа может быть отнесена к самым важным задачам систем автоматизированного проектирования (САПР), она заключается в определении специального представления графа, при котором ребра исследуемого графа не имеют взаимных пересечений.
Это означает, что формирование рисунка плоского графа и визуализация его изображения считаются одними из самых важных подзадач, которые возникают при разрешении большинства актуальных прикладных проблем. К примеру, это может потребоваться для визуализации разных производственных задач, а также при формировании систем автоматизации проектирования плоских конструктивов. Здесь под плоским конструктивом следует понимать техническое устройство, то есть конструкцию, в которой непересекающиеся соединения среди элементов устройства и сами элементы располагаются в параллельных (эквидистантных) плоскостях.
В качестве такого устройства может выступать печатная плата, интегральная микросхема, БИС, СБИС и так далее. Существует метод проверки планарности графа с одновременным формированием математических структур, предназначенных для описания топологического рисунка графа с целью его визуализации. Метод базируется на создании системы изометрических циклов, понятии вращения вершин графа, а также задании операции определения пересечения ребер в виде пересечения их проекций на координатно-базисную систему, в качестве которой может использоваться опорный цикл DFS-дерева (Depth-first search, то есть, поиска в глубину) графа.
Необходимо заметить, что на текущий момент есть эффективные алгоритмы, которые позволяют определить, может ли считаться граф планарным, со сложностью, определяемой линейной зависимостью от количества вершин графа. В отличие от алгоритмов, имеющих линейную сложность, известен также метод, обладающий более высокой вычислительной сложностью:
где m является количеством вершин графа.
Но хотя данный метод предоставляет возможность не только определять, может ли граф считаться планарным, но и получать топологический рисунок графа, который можно в дальнейшем использовать для визуализации графа, его высокая вычислительная сложность может считаться его большим недостатком.
Проверка планарности графа
Предположим, что имеется произвольный граф G. Путем последовательного просмотра всех вершины графа, следует удалить петли, «висячие» вершины и кратные ребра, если они присутствуют в графе. Далее следует удалить мосты и точки сочленения, что позволяет получить несколько компонент связности, которые могут рассматриваться по отдельности. Пара ребер, которые соединены одной вершиной, имеющей локальную степень равную двум, следует заменить одним ребром. Подразумевается, что эти преобразования необходимо запомнить, для того чтобы впоследствии можно было восстановить первоначальный вида графа G после его проверки.
Несепарабельным графом G называется связный неориентированный граф, не имеющий петель и кратных ребер, а также не имеющий мостов и точек сочленения, вершин с локальной степенью меньшей или равной двум. К подобным несепарабельным графам, для того чтобы определить их планарность, может быть использован критерий планарности Маклейна, а также операция кольцевого суммирования суграфов в подпространстве циклов.
Пусть G = (X,U) является несеперабельным графом, имеющим пронумерованные множество ребер:
При этом card X = n и card U = m.
Как правило, граф G может быть представлен матрицей инциденций или матрицей смежностей. Графически граф можно представить в виде диаграммы, в которой вершины изображены точкой или кружком, а ребра представлены отрезками линий, которые соединяют вершины. На рисунках ниже представлены различные возможные диаграммы графа G.
Рисунок 1. Диаграмма графа G. Автор24 — интернет-биржа студенческих работ
Рисунок 2. Диаграмма графа G. Автор24 — интернет-биржа студенческих работ
Рисунок 3. Диаграмма графа G. Автор24 — интернет-биржа студенческих работ
Если граф является планарным, то всегда присутствует возможность провести соединения (ребер графа) без наличия пересечений. Данное представление планарного графа именуется плоским изображением графа, как на рисунке выше.
Необходимо заметить, что известны структуры, являющиеся общими для всех плоских изображений графа. Рассмотрим множество простых циклов, которые являются границами граней плоского изображения. Приведем пример, в котором используем граф G, изображенный на рисунке выше. Представим множество граничных циклов в форме компонентов пространства суграфов:
Цикломатическое число должно определять число независимых циклов графа:
Кольцевая сумма независимых циклов способна определить обод. На рисунке ниже показано задание направления обхода ребер в циклах.
Рисунок 4. Задание направления обхода ребер в циклах. Автор24 — интернет-биржа студенческих работ
Если выполнить задание направления обхода ребер в циклах, соблюдая условия планарности Маклейна, то тогда следует записывать циклы как кортежи вершин:
Рисунок 5. Циклы как кортежи вершин. Автор24 — интернет-биржа студенческих работ
Но если взглянуть с обратной стороны, то задаваемое подмножество циклов, имеющее заданное направление обхода ребер, способно породить (индуцировать) некоторый циклический порядок распределения смежных вершин для каждой из вершин. На рисунке ниже показано вращение вершины $х_1$.
Рисунок 6. Вращение вершины х1. Автор24 — интернет-биржа студенческих работ
Для заданного графа G вращением вершины А графа G является ориентированный циклический порядок (или циклическая перестановка) всех ребер, которые являются инцидентными к вершине А. Вращение графа следует описать и представить следующим образом. Введем обозначения вершин как $x_1, x_2, . x_n$. Далее запишем циклическую перестановку соседей для всех вершин $x_i$. Эта перестановка определяется вращением вершины $x_i$, являющимся циклической перестановкой ребер, которые инцидентны вершине $x_i$.
Как доказать планарность графа
Цепью называют простую цепь между полюсами сети(S). – входной, выходной полюс. Полюсные ребра-Z.
Сеть состоящая из n параллельных ребер, соединяющих полюса обозначается через.
Сеть, которая может быть получена из сетей иприменением конечного числа операций подстановки сети вместо ребра называетсяпараллельно-последовательной сетью.
Опр. Сетью называется связный ориентированный граф G(V, E) без петель с выделенными вершинами истоком и стоком, причем каждой дуге поставлено в соответствие некоторое натуральное число –пропускная способность дуги.
Пропускная способность дуги характеризует максимальное количество вещества, которое может пропустить за единицу времени дуга . Договоримся на сети пропускную способность дуги записывать в круглых скобках.
Поток в сети определяет способ пересылки некоторых объектов из одной вершины графа в другую по направлению дуги. Число объектов (количество вещества) , пересылаемых вдоль дуги, не может превышать пропускной способностиэтой дуги:. Будем считать, что если существует дуга изв, то нет дуги изв. Таким образом, рассматривается поток вещества только в одну сторону.