Как нарисовать граф

Графы

Граф — является множеством вершин (узлов) и рёбер, которые соединяет пару различных вершин. Будем описывать граф массивом узлов nodes, каждый из которых содержит массив go с номерами узлов в которые можно перейти непосредственно из данного. В отличие от списков и деревьев, графы имеют сложную топологию, поэтому для их визуализации необходимо задать координаты x и y каждого узла. Узел также может иметь имя nm и хранить другие данные. Граф реализован классом Graph. Его можно задать по другому графу или массиву узлов, как в этом примере:

Ещё один способ, создание графов в классе Graph — это задание числа его узлов, а затем постепенное добавление рёбер:

При создании графов можно также пользоваться редактором.

Большинству алгоритмов достаточно знать только узлы в которые можно перейти из данного. Однако, в ряде случаев необходима обратная информация — массив узлов из которых можно попасть в данный. Такие массивы on (в каждом узле) строятся по массивам go при помощи функции g.createOn(). В общем случае, узел может иметь следующие свойства: По умолчанию, цвет узла равен Graph.svg.cFill=»#FFC». Если задан массив цветов Graph.svg.colors и у узла есть пометка chk, то он красится цветом под номером chk из этого массива. Другой способ покраски узлов и рёбер — это прямое задание свойств col и cols каждого узла.

Немного определений

Однонаправленное ребро графа иногда называют дугой, а двунаправленное — собственно ребром. Граф, состоящий из V узлов ( == вершин), содержит не более V·(V-1) рёбер (считая двунаправленное ребро, как два ребра). Два графа называют изоморфными, если с точностью до имён узлов их топология (число узлов и способы их соединений) совпадает.

Путь на графе — это множество вершин в которые можно попасть последовательно одна за одной. Если все вершины и рёбра составляющие путь различны, то он называется простым путём. Ниже вершины 0,1,2 составляют путь. Цикл — это простой замкнутый путь (начинающийся и кончающийся на одной и той же вершине. На втором рисунке это 1,3,4:

Граф состоящий из двунаправленных рёбер называется связным, если из каждого узла существует путь в любой другой узел. При наличии односторонних рёбер пути может не быть (выше, например из 4 в 0), но этот граф по-прежнему является связным. Несвязный граф состоит из набора связных (внутри себя) подграфов.
Ацикличный граф не содержит внутри себя циклов (он также называется лесом). Если в ациклическом графе существует единственный узел из которого можно попасть в любой другой (причём единственным образом), то такой граф называется деревом.

Гамильтонов путь -это простой путь, проходящий через каждый узел графа один раз. Эйлеров путь — проходит через каждое ребро в точности один раз.

Поиск кратчайшего пути.
Поиск самого длинного пути.
Проверка графа на связность.
Поиск гамильтонового пути (или доказательство его отсутствия).
Поиск эйлерового пути (или доказательство его отсутствия).
Проверка изоморфности двух графов (их тождественность без учёта имён узлов и их координат).
Планарность графа (возможность рисования его на плоскости без пересечения ребер и вершин).
Раскраска узлов графа в k цветов, чтобы ни одно ребро не соединяло узлы одинакового цвета.

Генерация больших графов

Большие графы задавать «ручным» способом непросто, поэтому для тестирования алгоритмов удобны функции генерации графов произвольного размера. Например, решётка шириной w узлов и высотой h узлов с длиной ребра len (в пикселях) создаётся функцией createGrid(w,h,len, oneway). Четвёртый аргумент в функции (если он есть и равен true) делает рёбра графа направленными. Ниже приведены три варианта использования этой функции. В третьем случае, при рисовании графа, отключен вывод имён узлов (Graph.svg.showNm = false). Во втором случае функция g.swapRibs(prob, ribs) с вероятностью prob переворачивает в узле от одного до ribs рёбер:

Ещё один, более «дырявый» вариант — это граф в виде треугольника Серпинского createTriangle(num, len) с числом рекурсий num и стартовым ребром длиной len (в px):

Приведём код этой функции: Функция createTri(num, k0, k1, k2) внутри треугольника, образованного вершинами k0, k1, k2 рекурсивно num раз повторяет треугольник Серпинского:

Модифицированный треугольник Серпинского можно получить функцией createTriangle2:

Простейшие понятие о графах. Представления графов в памяти, классические алгоритмы.

Теория графов — раздел математики и информатики, нашедший широкое применение в современных прикладных задачах. В первую очередь, это задачи поиска маршрута на картах, но её применение не ограничивается навигационными приложениями. Графы возникают там, где между данными существуют какие-либо нелинейные связи. Например, это могут быть компьютеры, соединённые в сеть. Или же это могут быть задачи, которые надо выполнить в каком-то порядке, причём некоторые задачи надо выполнять строго после каких-то других. Существуют алгоритмы, позволяющие вычислить оптимальный порядок выполнения таких задач.

История возникновения теории графов

Леонард Эйлер и задача о Кёнигсберских мостах

Родоначальником теории графов считается Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кёнигсбергских мостах, ставшей впоследствии одной из классических задач теории графов.

Издавна среди жителей Кёнигсберга (теперь Калининграда) была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды? Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.

В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно).

Для того, чтобы решить эту задачу, Эйлер сделал специальные обозначения. Каждую часть суши (остров или берег реки) он обозначил кружком на бумаге, а затем соединил линиями те кружки, между которыми существуют мосты. Такие обозначения подчеркивают, что в этой задаче фактическое расположение, форма, длина и другие свойства объектов не представляют интереса, важны только связи между ними. Такая картинка на бумаге или на экране компьютера называется графом. Кружки — это его вершины, а линии — рёбра. Размышляя над этой и другими картинками из кружков и линий, Эйлер пришел к следующим выводам о графах:

Число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно всегда быть чётно. То есть, просто не может существовать графа, который имел бы нечётное число нечётных вершин.
Если все вершины графа чётные, то его можно начертить не отрывая карандаша от бумаги, при этом начинать можно с любой вершины графа и завершить его в ней же.
Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.

Граф кёнигсбергских мостов имел четыре нечётные вершины (т.е. все), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

Кёнигсбергские мосты в виде графа

Проблема четырёх красок

Проблема четырёх красок — математическая задача, предложенная Гутри в 1852 году.

Выяснить, можно ли всякую расположенную на сфере карту раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета.

Иначе говоря, показать что хроматическое число плоского графа не превосходит 4.

О доказательстве

К. Аппель и В. Хакен доказали в 1976 г., что так можно раскрасить любую карту. Это была первая крупная математическая теорема, для доказательства которой был применён компьютер. Несмотря на последующие упрощения, доказательство практически невозможно проверить, не используя компьютер. Поэтому некоторые математики отнеслись к этому доказательству с недоверием, что объяснялось не только использованием компьютера, но и громоздкостью описания алгоритма первых доказательств (741 страница), впоследствии были предложены более компактные алгоритмы и скорректирован ряд ошибок. Проблема четырех красок является одним из известнейших прецедентов неклассического доказательства в современной математике.

Определения теории графов

Граф — конечное множество вершин, природа которых не важна, и конечно множество рёбер, соединяющих между собой какие-либо вершины.

Графы могут быть ориентированными и неориентированными. Если в рамках задачи по рёбрам можно перемещаться в обоих направлениях, то граф называется неориентированным. Если же по каждому ребру можно пройти только в одну сторону, то граф ориентированный. В таком случае рёбра обычно обозначаются стрелками, а не просто линиями.

Пример ориентированного графа

Иногда бывает полезно связать с ребрами графа какие-то числа. Это могут быть длины дорог или плата за проезд, если граф моделирует карту какой-то местности. В таком случае граф называется взвешенным, а сами числа — весами.

Пример: граф с шестью вершинами и семью рёбрами

Граф, в котором каждая пара вершин соединена ребром, называется полным. Обозначение: K_n – граф, состоящий из n вершин и ребер, соединяющих всевозможные пары этих вершин. Такой граф можно представить как n–угольник, в котором проведены все диагонали.

Ниже приведены полные графы с числом вершин от 1 до 8 и количества их рёбер.

K₁ : 0	K₂ : 1	K₃ : 3	K₄ : 6

K₅ : 10	K₆ : 15	K₇ : 21	K₈ : 28

Степенью вершины называется число ребер, которым принадлежит вершина (число рёбер с концом в данной вершине).

Дополнением данного графа называется граф, состоящий из всех ребер и их концов, которые необходимо добавить к исходному графу, чтобы получить полный граф.

Граф, который можно представить на плоскости в таком виде, когда его ребра пересекаются только в вершинах, называется плоским.

Многоугольник плоского графа, не содержащий внутри себя никаких вершин или ребер графа, называют его гранью.

Понятия плоского графа и грани графа применяется при решении задач на «правильное» раскрашивание различных карт.

Путем от вершины A до вершины X называется последовательность ребер, ведущая от A к X, такая, что каждые два соседних ребра имеют общую вершину, и никакое ребро не встречается более одного раза.

Циклом называется путь, в котором совпадают начальная и конечная точка (т.е. можно «ходить по циклу» — «ходить по кругу»).

Простым циклом называется цикл, не проходящий ни через одну из вершин графа более одного раза.

Длиной пути, проложенного на цикле, называется число ребер этого пути.

Две вершины A и B в графе называются связными (несвязными), если в нем существует (не существует) путь, ведущий из A в B.

Граф называется связным, если каждые две его вершины связны; если же в графе найдется хотя бы одна пара несвязных вершин, то граф называется несвязным.

Специальным типом графов является дерево. В дереве выделяется особая вершина — корень, которая соединена рёбрами с другими вершинами — своими потомками, которые в свою очередь могут иметь своих потомков. Вершина, не имеющая потомков, называется листом. Наглядный пример дерева — иерархия файлов и папок в файловой системе компьютера или систематика живых организмов

Если не выделять особым образом корень, то дерево — это просто любой связный граф, не имеющий циклов

Представление графов в памяти

Чтобы решать задачи, связанные с графами, нужно сначала научиться сохранять его в памяти, а ещё лучше — сохранять оптимально. Существует несколько способов сделать это, и для каждой конкретной задачи оптимальным будет свой способ.

Матрица смежности

Самый простой способ сохранить граф в памяти — матрица смежности. Нарисуем таблицу, которая чем-то напоминает таблицу умножения: в первой строчке и в первом столбце будут стоять номера (или любые названия) вершин, а на пересечении столбца и строки будем ставить, например, 1 если между этими вершинами есть ребро и 0 если нет. Кроме 1 и 0 можно ставить, например, вес ребра, а для обозначения отсутствия ребра — просто очень большое число. Какой именно вариант использовать, зависит от каждой конкретной задачи. Также задача определяет, что ставить на диагонали получившейся матрицы.

электрическая схема является графом, в котором вершины — элементы схемы, а дуги — соединяющие провода;
;
система каталогов операционной системы является частным случаем графа — каталоги и папки задаются вершинами, а отношение вложенности — дугами.

Если направление ребер графа имеет значение (например при отражение отношения вложенности каталогов) — то граф называется ориентированным. Если направление не важно (например при соединении элементов электрической цепи) — граф является неориентированным. Кроме того, ребрам часто приписывается вес, граф в этом случае называется взвешенным — в системе дорог веса ребер могут отражать расстояния между городами.

В связи с этим возникает необходимость обработки графов компьютером, но для этого необходимо сначала каким-то удобным для обработки образом разместить его в памяти. Итак, граф ( G ) — это совокупность вершин ( V ), и дуг ( E ), в зависимости от того, как они задаются, выделяются следующие способы машинного представления графа:

матрица смежности для графа из N вершин хранится в виду двумерного массива размером N x N . Вершины графа в этом случае задаются номерами (индексами строк и столбцов матрицы), а ячейка графа matrix[i, j] отражает наличие дуги между соответствующими вершинами. Например, при наличии дуги в ячейке может быть записана единица (или вес ребра i->j для взвешенного графа) , а при отсутствии — ноль;
матрица инцидентности для графа из N вершин и M дуг хранится в виде двумерного массива размером N x M . Ячейка матрицы matrix[i, j] отражает инцидентность ребра j вершине i , т.е. тот факт, что это ребро выходит или входит в вершину i . Если ребро не связано с вершиной — в соответствующей ячейке матрицы записывается ноль, в противном случае единица (если граф ориентированный, то начало ребра можно отметить -1 , а конец 1 , если граф взвешенный — единица может быть заменена весом соответствующего ребра).

graph_example

Матрица смежности графа:

A	B	C	D	E	F	G
A	0	12	0	0	0	16	3
B	12	0	8	0	0	0	6
C	0	8	0	4	0	0	8
D	0	0	4	0	14	0	30
E	0	0	0	14	0	28	11
F	16	0	0	0	28	0	13
G	3	6	8	30	11	13	0

Матрица инцидентности графа:

AB	BC	CD	DE	EF	FA	AG	BG	CG	DG	EG	FG
A	12	0	0	0	0	0	3	0	0	0	0	0
B	12	8	0	0	0	0	0	6	0	0	0	0
C	0	8	4	0	0	0	0	0	8	0	0	0
D	0	0	4	14	0	0	0	0	0	30	0	0
E	0	0	0	14	28	0	0	0	0	0	11	0
F	0	0	0	0	28	16	0	0	0	0	0	13
G	0	0	0	0	0	16	3	6	8	30	11	13

Работая с приведенными матрицами возможно, например, найти в графе кратчайшие пути между вершинами, построить минимальные остовы и т.д., однако, у них есть недостатки:

избыточность. Зачастую в графах ребра существуют между небольшим (количеством вершин), поэтому в матрице смежности будет огромное количество нулей. В матрице инцидентности в каждом столбце может быть лишь два ненулевых значения (т.к. у дуги два конца). На хранение нулей тратится память, что может быть существенно при обработки больших графов;
недостаточная расширяемость. В матрицу смежности можно без проблем добавлять новые дуги, но чтобы добавить вершину нужно создавать новую матрицу большего размера и копировать в нее данные из старой. Это работает очень медленно при больших матрицах. В матрице инцидентности такие проблемы возникнут как при добавлении дуг, так и при добавлении вершин.

В связи с этим, зачастую применяются списки смежности и инцидентности. Для каждой вершины при этом хранится список с номерами смежных вершин или инцидентных ребер. В качестве структуры данных при этом могут использоваться массивы, связные списки и даже хеш-массивы.

Списки смежности графа:

A	B(12)	F(16)	G(3)
B	A(12)	C(8)	G(6)
C	B(8)	D(4)	G(8)
D	C(4)	E(14)	G(30)
E	D(14)	F(28)	G(11)
F	A(16)	E(28)	G(13)
G	A(3)	B(6)	C(8)	D(30)	E(11)	F(13)

Списки смежности и инцидентности решают проблему расширяемости графа, т.к. новые узлы и дуги могут быть очень просто и эффективно добавлены во время выполнения программы, кроме того они более оптимальны по памяти, т.к. хранятся только данные о существующих дугах. Однако, такой способ представления графа менее эффективен по процессорному времени, т.к. для проверки существования дуги в худшем случае нужно будет перебрать все дуги, выходящие из некоторой вершины, но в матрице смежности было достаточно обратиться к элементу массива (асимптотическая сложность ухудшилась с O(1) до O(K) при использовании связных списков или O(log(K)) при использовании хеш-массивов). Важно, что K в этом случае — количество смежных вершин, для многих графов оно не будет очень большим (например, если граф представлял бы карту города, то скорее всего значение K для каждой вершины не превышало бы 4-6 ), в связи с этим, нужно очень внимательно выбирать структуру данных для хранения списков смежности/инцидентности.

Еще одним способом задания графа в программе может быть хранение указателей на смежные вершины/инцидентные дуги внутри каждого узла программы, при этом узел описывается в виде структуры, содержащей данные и эти указатели. Примерно так: