Теория графов
Выбери формат для чтения
Загружаем конспект в формате doc
Это займет всего пару минут! А пока ты можешь прочитать работу в формате Word 👇
Лекция 14. Теория графов
Историю теории графов принято исчислять с 1736 года, когда Эйлер исследовал «задачу о кенигсбергских мостах»: построить в графе циклический путь, проходящий по одному разу через каждое ребро. В середине 19-го века Гамильтон заинтересовался задачей построения циклического пути, проходящего по одному разу через каждую вершину графа. К тому же времени относится использование графов для анализа электрических цепей (Кирхгоф) и химических молекул (Кэли). Развитие современной теории графов относится к 30-м годам 20-го столетия. Они нашли многочисленные применения в электротехнике, электронике, биологии, экономике, программировании и в других областях.
Бинарным отношением Т в множестве М называется подмножество его квадрата.
ТМ2=ММ
Говорят, что элементы mi и mj находятся в отношении Т, если (mi, mj)Т.
Совокупность множества М с заданным в нем бинарным отношением Т называется графом.
G=, где М – носитель графа (множество вершин); Т – сигнатура графа (множество ребер).
Граф G – совокупность двух множеств: вершин V и ребер E, между элементами которых определено отношение инцидентности – каждое ребро e E инцидентно ровно двум вершинам v, v V, которые оно соединяет. При этом вершины v, v называют коинцидентными ребру, ребро e называют инцидентным вершинам, а вершины v, v – смежные.
Два ребра называют смежными, если они инцидентны одной и той же вершине.
Ребро может иметь направление. В этом случае граф называется ориентированным, а ребро – дугой.
Ребра, инцидентные одной и той же паре вершин называются параллельными (кратными). Граф, содержащий параллельные ребра, называется мультиграфом.
Ребро, концевые вершины которого совпадают, называется петлей.
Граф без петель и кратных ребер называется полным, если каждая пара вершин соединена ребром.
Дополнением графа G называется граф , имеющий те же вершины, что и G и только те ребра, которые нужно добавить к G, чтобы получить полный граф.
Для получения из неориентированного графа ориентированного необходимо каждое ребро представить двумя разнонаправленными дугами с теми же концевыми вершинами (рис. 13.1).
Рис. 11.1
Множество вершин, смежных с вершиной v, называется её окрестностью О(v).
Степенью (локальной степенью) вершины v V н-графа G называется количество ребер (v), инцидентных вершине v. Имеет место зависимость , где m – число ребер графа.
Для орграфа 1(v) – число дуг с началом в вершине v; 2(v) – число дуг, входящих в v. Имеет место зависимость
Графы G1 и G2 равны (G1 = G2), если их множество вершин и ребер совпадают.
Граф G считается полностью заданным, если нумерация его вершин и ребер зафиксирована. Графы, отличающиеся только нумерацией вершин и ребер называются изоморфными.
Пример. Задать графы, изображенные на рис. 11.2 через множества вершин и ребер.
Рис. 11.2
Множество вершин G1 V1 = {v1, v2, v3, v4, v5}; множество ребер U1 = {u1, u2, u3, u4}.
Понятие взвешенного графа
Сопоставим каждой вершине vi вес qi из множества весов Q={qi: i=1,2,…,n}, получим множество взвешенных вершин {(vi, qi): i=1,2,…,n} при этом не обязательно, чтобы все веса были различны.
Сопоставим каждому элементу множества ребер uj вес из множества весов P={pj: j=1,2,…,m}, получим множество взвешенных ребер {(uj, pj): j=1,2,…,m}.
Множества взвешенных ребер и взвешенных вершин определяют взвешенный граф.
G=<(V,Q), (U,P)>
Взвешенный граф является функцией на вершинах и ребрах графа.
Способы задания неорграфов графов
Пусть граф G имеет n вершин и m ребер.
Матрица инцидентности
Матрица инцидентности A(n, m). Строки соответствуют вершинам; столбцы – ребрам. aij = 1, если i-я вершина инцидентна j-му ребру, aij = 0 иначе.
Например, на рис. 11.3. представлены граф и матрица инцидентности
u1
u2
u3
u4
u5
u6
u7
u8
u9
v1
1
1
v2
1
1
1
v3
1
1
v4
1
1
v5
1
1
1
v6
1
1
1
v7
1
1
Рис. 11.3. Пример для матрицы инцидентности графа
Матрица смежности
Квадратная матрица A(n, n). aij равен количеству ребер, инцидентных одновременно i-й и j-й вершинам. Матрица смежности симметрична относительна главной диагонали для н-графа без петель.
Для нашего примера матрица смежности приведена на рис. 11.4.
v1
v2
v3
v4
v5
v6
v7
v1
1
1
v2
1
1
1
v3
1
1
v4
1
1
v5
2
1
v6
2
1
v7
1
1
Рис. 11.4. Матрица смежности
Другие способы задания графов
1. Списком вершин и ребер. 2 (3) массива: 1 для вершин и 1 (2) для ребер
2. Списком ребер
3. Другие способы, ориентированные на экономии памяти или представление в БД. Например, упорядоченные деревья представляют парой предок-потомок, где вторая компонента всегда уникальна.
Разделение неориентированного графа на составляющие
Суграфом графа G = (V, U) называется граф G = (V, U), где U U, т.е. суграф получается из графа удалением некоторого количества ребер с сохранением вершин.
Подграф графа G = (V, U) – это граф G = (V, U), где V V, полученный удалением некоторых вершин и инцидентных ребер.
Часть графа G = (V, U) называется граф G = (V, U), где V V, U U, т.е. полученный удалением некоторых вершин и ребер.
Динамические свойства неориентированного графа
Путём (маршрутом) в графе G = (V, E) называется конечная последовательность n ребер u1, u2, …, un (не обязательно различных), если существует последовательность v0, v1, … vn (не обязательно различных) вершин, что ui соответствует (vi-1, vi). Число n в данных обозначениях называется длиной пути.
Если v0 = vn, то маршрут замкнут.
Пример. Граф G представлен на рис. 11.5. Последовательность ребер u1, u2, u3, u4, u5, u6 образует незамкнутый маршрут длины 6 и соединяет вершины v1 и v6. Ему соответствует последовательность вершин v1, v2, v2, v3, v4, v2, v5.
Маршрут u1, u2, u3, u4, u5, u1 замкнутый и объединяет вершины v1, v2, v2, v3, v4, v2, v1.
Рис. 11.5
Цепью называется незамкнутый маршрут, если его ребра различны.
Например, для графа, изображенного на рис. 11.5 цепью будет маршрут u1, u5, u4, u3, u2, соединяющий вершины v1, v2, v2, v4, v3, v2.
Циклом называется цепь, которая начинается и заканчивается в одной и той же вершине (v0 = vn).
Например, для графа, изображенного на рис. 11.5 циклом будет маршрут u2, u3, u4, (u5), содержащий последовательность вершин v2, v3, v4, v2, v2.
Простой цепью называется цепь, в которой все вершины различны.
Например, простая цепь для графа, изображенного на рис. 11.5, составлена ребрами u6, u2, u3 и содержит последовательность вершин v5, v2, v3, v4.
Простой цикл не содержит одинаковых вершин, кроме v0 = vn.
Например, простой цикл для рассматриваемого ранее графа составлен из ребер u2, u3, u4 с последовательностью вершин v2, v3, v4, v2.
