Тема 3. Графы и сети.

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

Две вершины называются смежными, если существует ребро их соединяющее. Два ребра называются смежными, если они имеют общую вершину. Мощность графа – число его вершин.

Вершина и ребро называются инцидентными, если является концом ребра .

Два графа и называются изоморфными, если существует взаимно-однозначное соответствие между множествами их вершин, сохраняющее смежность.

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

Матрица смежности вершин однозначно определяет структуру графа.

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

Матрицей инцидентности графа называется матрица , где - число вершин, - число дуг, элементы которой определяются следующим образом:

.

Матрица инцидентности также однозначно определяет структуру графа.

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

Маршрутом для графа называют последовательность , при этом вершину называют началом, а вершину - концом маршрута. В ориентированном графе маршрут называют – путь. Число рёбер в маршруте называют – длина маршрута.

Незамкнутый маршрут, в котором все рёбра попарно различны, называют – цепь. Простой называют цепь в которой попарно различны все вершины. Замкнутую цепь называют цикл.

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

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

Связный граф не имеющий циклов называют – дерево.

Сеть – ориентированный граф со взвешенными дугами.

Получить ответ на вопрос о существовании -маршрутов, циклов содержащих вершину , а также найти все маршруты заданной длины можно с помощью матрицы смежности, используя следующую теорему и следствия из неё.

Теорема. Количество маршрутов из вершины в вершину длины даёт элемент матрицы , являющейся -ой степенью матрицы смежности вершин .

Следствие 1. В графе мощности существует -маршрут тогда и только тогда, когда -элемент матрицы не равен нулю.

Следствие 2. В графе мощности существует цикл содержащий вершину тогда и только тогда, когда -элемент матрицы не равен нулю.

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

Одной из основных задач теории графов является задача о нахождении в заданном графе пути, соединяющем две заданные вершины графа и доставляющие минимум или максимум некоторой аддитивной функции, определённой на путях (длина, стоимость и т.д). Частным случаем такой задачи является задача о кратчайшем пути. Существуют различные алгоритмы нахождения кратчайшего пути (например – алгоритмы Дейкстры, Беллмана-Мура).

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