Теория графов
Дипломная работа - Математика и статистика
Другие дипломы по предмету Математика и статистика
ссмотрим, например, граф, изображенный на рис.10.
Рис. 10
Построенная в соответствии с описанным правилом матрица инциденций этого графа имеет вид
Примечание: для графа на рис.10 приняты следующие обозначения дуг: Х1 = (v1, v2), Х2 = (v1, v3), Х3 = (v3, v2), Х4 = (v3, v4), Х5 = (v5, v4), Х6 = (v5, v6), Х7 = (v6, v5).
Ориентированный граф, как правило, петель не содержит. Его матрица инциденций имеет в каждом столбце +1 и -1, которые отвечают началу и концу каждого ребра.
Задачи, возникающие на практике, приводят к разного вида операциям над матрицами. Рассмотрим некоторые из них.
Пусть система авиалиний между городами Х1, Х2, Х3 одной страны и городами У1 и У2 другой страны задается подмножеством пар: (Х1, У1), (Х1, У2), (Х2, У1), (Х2, У2), (Х3, У2), т.е. множеством ребер соответствующего графа. Система связи между этими же городами водным транспортом задается другим подмножеством пар: (Х1, У1), (Х2, У1), (Х2, У2), (Х3, У1). Кроме этого, для каждой пары городов (Хi, Уj). Известно число различных водных и авиамаршрутов. Эти числа можно проставить над ребрами на рисунке графа или зафиксировать с помощью двух матриц одинакового порядка:
У1 У2 У1 У2
Х1 4 1 Х1 2 0
А = Х2 2 6 В = Х2 1 3
Х3 0 4 Х3 2 0
Требуется определить, сколькими различными способами с помощью воздушного или водного транспорта можно попасть из каждого города одной страны в каждый город другой страны.
Естественно, что для этого достаточно сложить соответствующие элементы матриц А и В. Ответ можно записать с помощью новой матрицы того же порядка:
У1 У2
Х1 6 1
С = Х2 3 9
Х3 2 4
В общем случае операцию сложения двух матриц можно записать так: если А = (аi,j) и В = (bi,j) - матрицы одного порядка, то матрица С = А + В = (Сi,j), где Сi,j = аi,j + bi,j.
Рассмотрим еще одну задачу. Пусть в каких-то трех странах выделены некоторые города, связанные с транспортом четырех видов: воздушным, железнодорожным, водным и автобусным. Схема транспортных связей между городами Х1 и Х2, принадлежащими первой стране, и городами У1, У2, У3, принадлежащими второй стране, зафиксирована матрицей А, где аi,j показывает на число видов транспорта, соединяющих города Хi и Уi. Аналогичная схема транспортных связей между городами У1, У2, У3, принадлежащими второй стране, и городами Z1, Z2, принадлежащим третьей стране, представлена матрицей В. Какие конкретно виды транспорта связывают пары городов, нас не интересует. Города первой и третьей стран непосредственных связей не имеют.
У1 У2 У3 Z1 Z2
А = Х1 4 0 2 У1 2 1
Х2 2 3 1 В = У2 0 3
У3 3 0
Требуется подсчитать число различных маршрутов от каждого из городов первой страны в каждый из городов третьей страны, проходящих через вторую страну.
Если нарисовать соответствующую схему, то решить задачу не трудно, попробуем решить матричным методом.
Таким образом, по заданным матрицам А и В требуется определить элементы сi,j матрицы С:
1Z2
C = Х1 С11С12
Х2 С21 С22
Рассуждения определяют матрицу С и алгоритм нахождения элементов сi,j, а именно
Z1Z2
C = Х1 (а11в11 + а12в21 + а13в31а11в12 + а12в22 + а13в32
Х2 (а21в11 + а22в21 + а23в31 а21в12 + а22в22 + а23в32
Z1Z2
C = Х1 14 4
Х2 7 11
Рассмотренная задача убеждает в целесообразности введения еще одной операции над матрицами. Эту операцию принято называть операцией умножения матриц.
Если С = АВ, то элементы матрицы С определяются следующей формулой:
сi,j = ai1в1j + ai2в2j + ai3в3j + … + ainвnj
Таким образом, элемент сi,j образуется из элементов i-й строки матрицы А и элементов j-го столбца матрицы В.
Следует обратить внимание на следующие два факта:
) операция умножения матрицы А на матрицу В определена только в том случае, если число столбцов в матрице А равно числу строк в матрице В.
) если матрица А имеет порядок (m x n), а матрица В - порядок (n x r), то матрица - произведение С = АВ имеет порядок (n x m).
Рассмотрим некоторые основные операции, производимые над графами.
Операцией добавления к графу G = .
Операцией добавления дуги (а, в) к графу G состоит в образовании графа . Операция отождествления вершин (в случае, когда Vi и Vj соединены дугой, операцию называют стягиванием дуги (ViVj).
Пример:
Рис. 11
Из графа G, добавлением вершины 5 образуется граф G1, добавлением дуги (3, 1) - G2, удалением дуги (3, 2) - G3, удалением вершины 2 - G4, отождествлением вершин 1 и 4 - G5 , стягиванием дуги (2, 3) - G6.
Добавлением графа без петель G = .
Рис. 12
Объединением G1 u G2 называется граф .
Если V1 ? V2 ? , то пересечением G1 ? G2 называется граф .
Кольцевой суммой G1 + G2, называется граф <V1 u V2, (U1 \ U2) u (U2 \ U2).
Соединением G1 + G2 называется .
Произведением G1 x G2 называется граф .
Композицией G1 [G2] называется граф , в котором ((V1j, V1j), (Vj2, Vj2)) є U, если 1) (Vj1, Vj2) є U1; 2) Vi1 = Vi2, (Vj1, Vj2) є U2.
Рассмотрим специальный класс графов, имеющий важное практическое значение, представители которого именуются деревьями.
Связный неориентированный граф называется деревом, если он не имеет циклов. В частности, дерево не имеет петель и кратных ребер. Граф без циклов есть граф, связные компоненты которого являются деревьями; иногда такой граф