Граф это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек. Вершины, прилегающие к одному и тому же ребру, называются смежными.
Если ребра ориентированны, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом.Если ребра не имеют ориентации, граф называется неориентированным.Графы обычно изображаются в виде геометрических фигур, так что вершины графа изображаются точками, а ребра - линиями, соединяющими точки (рис. 2.15).
external image picture2_13_1.GIF

Рис. 2.15
Петля это дуга, начальная и конечная вершина которой совпадают.
Простой граф - граф без кратных ребер и петель.
Степень вершины - это удвоенное количество петель, находящихся у этой вершины плюс количество остальных прилегающих к ней ребер.
Пустым называется граф без ребер. Полным называется граф, в котором каждые две вершины смежные.
Путь в ориентированном графе — это последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей.
Вершины v0, vn называются связанными данным путем (или просто связанными). Вершину v0 называют началом , vn - концом пути. Если v0 = vn, то путь называют замкнутым. Число n называется длиной пути.
Маршрут в графе путь, ориентацией дуг которого можно пренебречь.
Цепь - маршрут, в котором все ребра попарно различны.
Цикл - замкнутый маршрут, являющийся цепью.
Маршрут, в котором все вершины попарно различны , называют простой цепью. Цикл, в котором
все вершины, кроме первой и последней, попарно различны, называются простым циклом.
Построим граф, изображающий отношение делимости на множестве {1,2,3,4,5,6,7,8,9,10}. Принцип такой: если от одного числа до другого есть цепь, ведущая вверх, тогда второе число делится на первое (рис. 2.16).

external image picture2_13_2.GIF

Рис. 2.16
Подграф графа - это граф, являющийся подмоделью исходного графа, т.е. подграф содержит некоторые вершины исходного графа и некоторые ребра (только те, оба конца которых входят в подграф).
Подграф называется остовным подграфом, если множество его вершин совпадает с множеством вершин самого графа.
Граф называется связным, если любая пара его вершин связана. Связными компонентами графа называются подграфы данного графа, вершины которых связаны.
Дерево — это связный граф без циклов.
Деревья особенно часто возникают на практике при изображении различных иерархий. Например, популярны генеалогические деревья.
На рисунке 2.17 показано библейское генеалогическое дерево.


external image picture2_13_3.GIF

Рис. 2.17
Граф без цикла называется лесом. Вершины степени 1 в дереве называются листьями.

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

Способы представления графов
Граф, как и большинство других математических объектов, может быть представлен на компьютере (сохранен в его памяти). Существуют несколько способов его интерпретации, вот наиболее известные из них:

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

Бинарная матрица
Бинарная матрица


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

matrix_smeghnost
matrix_smeghnost


Слева на рисунке изображена все та же матрица смежности, имеющая размерность 4×4. Числа, выделенные синим, можно рассматривать как вершины смешанного графа, расположенного справа – того, представлением которого является матрица.
Для графического отображения графа необходимо уметь вычислять по матрице смежности количество его вершин, а также обладать знанием следующего правила. Когда из одной вершины в другую проход свободен (имеется ребро), тогда в ячейку заноситься 1, иначе – 0. Немного формализовав только что сказанное, получим: если из i в j существует ребро, то A[i][j]:=1, в противном случае A[i][j]:=0. Как видно, все элементы на главной диагонали равны нулю, это следствие отсутствия у графа петель. Но ни что не мешает, чтобы некоторые или все элементы главной диагонали были единицами.


Матрица инцидентности


Говорить о том, что ребро g и каждая из вершин u и y инцидентна g, стоит лишь в том случае, если g соединяет u и y. Уяснив это, перейдем к рассмотрению данного метода. Матрица инцидентности строиться по похожему, но не по тому же принципу, что и матрица смежности. Так если последняя имеет размер n×n, где n – число вершин, то матрица инцидентности – n×m, здесь n – число вершин графа,m – число ребер. То есть теперь чтобы задать значение какой-либо ячейки, нужно сопоставить не вершину с вершиной, а вершину с ребром.
В каждой ячейки матрицы инцидентности неориентированного графа стоит 0 или 1, а в случае ориентированного графа, вносятся 1, 0 или -1. То же самое, но наиболее структурировано:
  1. Неориентированный граф
    1. 1 – вершина инцидентна ребру
    2. 0 – вершина не инцидентна ребру
  2. Ориентированный граф
    1. 1 – вершина инцидентна ребру, и является его началом
    2. 0 – вершина не инцидентна ребру
    3. -1 – вершина инцидентна ребру, и является его концом
Построим матрицу инцидентности сначала для неориентированного графа, а затем для орграфа.

Матрица инцидентности
Матрица инцидентности


Ребра обозначены буквами от a до e, вершины – цифрами. Все ребра графа не направленны, поэтому матрица инцидентности заполнена положительными значениями.

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


Для орграфа графа матрица имеет немного другой вид. В каждую из ее ячеек внесено одно из трех значений. Обратите внимание, что нули в двух этих матрицах (рис. 1 и 2) занимают одинаковые позиции, ведь в обоих случаях структура графа одна. Но некоторые положительные единицы сменились на отрицательные, например, в неориентированном графе ячейка (1, b) содержит 1, а в орграфе -1. Действительно, это уместно, т. к. в первом случае ребро b не направленное, а во втором – направленное, и, причем вершиной входа для него является вершина «1».
Каждый столбец отвечает за какое-либо одно ребро, поэтому граф, описанный при помощи матрицы инцидентности, всегда будет иметь следующий признак: любой из столбцов матрицы инцидентности содержит две единицы, либо 1 и -1 когда это ориентированное ребро, все остальное в нем – нули.

Составим матрицы инциндентности и смежности для следующего непрерывного графа (рис. 2.18)


external image picture2_13_4.gif
Рис. 2.18
Матрица инцидентности
external image matrix_incidence.GIF
Матрица смежности
external image matrix_adjacency.GIF

Составьте матрицы инцидентности и смежности для следующих графов: задание

Примеры решений задач по теории графовЗадача 1. Постройте граф отношения "x+y ≤7" на множестве М={1,2,3,4,5,6}. Определите его свойства.
Посмотреть решение (pdf, 134 Кб)
Задача 2. Найти кратчайшие пути в орграфе от первой вершины ко всем остальным, используя алгоритм Дейкстры. Постройте дерево кратчайших путей.
Посмотреть решение (pdf, 196 Кб)
Задача 3. Найти максимальный поток и минимальный разрез в транспортной сети, используя алгоритм Форда–Фалкерсона (алгоритм расстановки пометок) Построить граф приращений. Проверить выполнение условия максимальности построенного полного потока. Источник – вершина 1, сток – вершина 8.
Посмотреть решение (pdf, 282 Кб)
Задача 4. Постройте остовное дерево минимального веса, используя алгоритмы Прима и Краскала. С помощью матрицы Кирхгоффа найдите количество (неизоморфных) остовных деревьев, используя пакеты компьютерной математики (например, MathCAD, Mathematica, MatLab).
Посмотреть решение (pdf, 173 Кб)
Применение теории графов при решение практических задач:

Языки описания и программы построения графов:
Для описания графов в целях, пригодных для машинной обработки и одновременно удобном для человеческого восприятия используется несколько стандартизированных языков, среди которых:
DOT (язык)
GraphML
Trivial Graph Format
GML
GXL
XGMML
DGML
Отметим специализированные коммерческие программы для построения графов:
ILOG
GoView
Lassalle AddFlow
LEDA (есть бесплатная редакция).
Из бесплатных можно отметить:
Boost Graph Library.
Для визуализации графов можно использовать:
Graphviz (по мнению экспертов[источник?], она хорошо работает для орграфов)
LION Graph Visualizer.
Графоанализатор — русскоязычная программа, с простым пользовательским интерфейсом.
Gephi — графическая оболочка для представления и изучения графов.


Полезные ресурсы:
Электронный вариант курса "Дискретная математика" ОГУ http://www.univer.omsk.su/departs/compsci/kursi/disc/graphs.htm
Сайт, посвящённый фестивалю педагогических идей "Открытый урок" http://festival.1september.ru/articles/416943/
http://matmetod-popova.narod.ru/theme213.htm
http://www.urtt.ru/bib/dataindex/dm/glava_4~.htm
http://kvodo.ru/graph-algorithms-introduction.html
http://www.univer.omsk.su/departs/compsci/kursi/disc/graphs.htm
http://www.math.mrsu.ru/text/courses/method/graphi_i_seti__potoki_v_setyah.htm