Изображение - граф
Cтраница 2
Таким образом, четность числа скрещиваний двух хороших изображений графа / C2r i 23 i одинакова. [16]
Эта теорема дает нам искомое обоснование использования диаграмм для изображения графов: достаточно взять трехмерное представление и спроектировать его на плоскость так, чтобы никакие две вершины не попадали в одну и ту же точку. Конечно, в общем случае такой метод приводит к пересечениям, хотя в некоторых случаях мы получим диаграммы без пересечений. Произойдет это только тогда, когда рассматриваемый граф может быть уложен на плоскости; такие графы называются планарными графами. Подробнее планарные графы будут изучены в гл. К ним относятся, например, вполне несвязные графы, граф / Си платоновы графы, циклические графы, колеса и звездные графы. [17]
 |
Выделение К3 3 из 010. [18] |
Такой подход легко можно реализовать вручную путем непосредственного исследования изображения графа, если число вершин в нем невелико. [19]
Следует упомянуть еще об одном упрощении, которым обычно лользуются шш изображении графов автоматов: если несколько стрелок соединяют одну и ту же ( упорядоченную) пару вершин, то все эти стрелки заменяются одной стрелкой того же направления с сохранением в ее обозначении всех букв, которые обозначали замененные ею стрелки. При этом, чтобы избежать путаницы в отношении выходных сигналов, каждый выходной сигнал пишется рядом с соответствующим ему входным сигналом и заключается обычно в скобки. [20]
Очевидно, что наиболее понятный и полезный для человека способ представления графа - изображение графа на плоскости в виде точек и соединяющих их линий - будет совершенно бесполезным, если мы захотим решать с помощью ЭВМ задачи, связанные с графами. Выбор соответствующей структуры данных для представления графов имеет принципиальное влияние на эффективность алгоритмов, поэтому мы подробнее остановимся на этой проблеме. Мы покажем несколько различных способов представления и кратко разберем их основные достоинства и недостатки. [21]
Основой геометрической формы задания графа является рисунок. Изображение графа в виде рисунка обладает наглядностью, раскрывает содержательный смысл представляемого объекта. [22]
Неорграф G называется планарным, если его можно изобразить на плоскости так, что никакие два ребра не будут иметь общих точек, кроме, может быть, общего конца этих ребер. Такое изображение графа на плоскости называется плоским. [23]
 |
Направленный граф ( а с шестью вершинами и его три фактора ( б, в, г. [24] |
Строим граф, для которого А является матрицей смежностей ( рис. 3.3, о), и его факторы. При изображении графа на плоскости необходимо стремиться к тому, чтобы число пересечений дуг было минимально. В этом случае граф приобретает большую наглядность и задача непосредственного визуального выделения факторов из графа значительно упрощается. Веса дуг, входящих в факторы, проставляются рядом с дугами. [25]
Обозначим через Km, n полный двудольный граф на множествах из га и п вершин, т.е. граф с ребрами, соединяющими всевозможные пары вершин, из которых одна принадлежит одному множеству, а вторая - другому. Через Dmtn обозначим изображение графа Km, n, т.е. его отображение на плоскость, при котором вершинам сопоставляются точки плоскости a, bj ( l i n, 1 / га), называемые узлами, а ребрам - жордановы кривые конечной длины ( дуги), ограниченные соответствующими узлами. Изображение будем называть хорошим, если никакие две дуги не имеют более одной общей точки и эта общая точка есть либо узел, ограничивающий каждую из этих дуг, либо скрещивание. Будем говорить, что две дуги at-bj, akbt ( i Ф k, j Ф l) скрещиваются, если дугу aibj можно замкнуть кривой, соединяющей и с bj, не пересекающейся с a bi и такой, что дуга a bi имеет точки как внутри, так и вне этой замкнутой кривой. [26]
Соображения, связанные с перестановками. Пусть D - изображение графа Кт п и а; - узел. Опишем вокруг а замкнув ную кривую, столь малую, что она пересекает каждую дуН uibj в точности один раз в точке PJ. Обозначим через Яг множество последовательностей индек сов, расположенных против часовой стрелки. [27]
Если анализ схем механизмов производится вручную или с помощью простейших микрокалькуляторов, а поиск путей и контуров на графе осуществляется визуально, то как правило число контуров и путей, которые имеются в графе Мэзона и учитываются формулами (3.19) и (3.20), получается меньше, и они легче находятся из рисунка. Немаловажно также то, что изображение графа Мэзона отличается от изображения структурного только лишь ориентацией ребер, в связи с этим структурный граф легко преобразовать в граф Мэзона, не делая при этом нового рисунка. [28]
Но тогда нельзя нарисовать часть изображения D, включающую дуги, исходящие из ач и я4 и имеющие лишь одно скрещивание. Это противоречие показывает, что хорошего изображения D графа / Cs, б с указанными свойствами не существует. [29]
Если ребра ориентированы, то их направления также должны соответствовать друг другу. Для нас в дальнейшем всюду будет несущественно, какое именно изображение графа используется, так как все изоморфные графы имеют одни п те же свойства. На рис. 1.2.1 приведены примеры изоморфных графов, образованных ребрами и вершинами правильных многогранников. [30]
Страницы: 1 2 3