Как рассказать этот текст кратко "Лекция 3. Элементы теории графов Теория графов – это направление математики, особенностью которой является геометрический подход к изучению математических объектов. Часто ее относят к топологии, так как во многих случаях рассматриваются лишь топологические свойства графов. Однако она пересекается со многими направлениями теории множеств, комбинаторной математики, алгебры, геометрии, теории игр, математической логики и другими математическими дисциплинами. Первая работа по теории графов, принадлежащая известному швейцарскому математику Л. Эйлеру, появилась в 1736 г. Эйлер решал очень известную головоломку о мостах Кёнигсберга. Термин «граф» впервые был введен спустя 200 лет (в 1936 г) Д. Кениго. Толчок к развитию теория графов получила на рубеже ХIX и ХХ столетий, когда резко возросло число работ в области топологии и комбинаторики, с которыми ее связывают самые тесные узы родства. Как отдельная математическая дисциплина теория графов была впервые представлена в работе венгерского математика Кенига в 30-е годы ХХ столетия. В последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях едва ли не всю современную математику. Графы эффективно используются в теории планирования и управления, теории расписаний, социологии, экономике, биологии, медицине, географии. Широкое применение находят графы в таких областях, как программирование, электроника, в решении вероятностных и комбинаторных задач, нахождения кратчайшего расстояния, максимального паросочетания и др. Математические развлечения и головоломки тоже являются частью теории графов. Теория графов быстро развивается, находит все новые приложения. Язык графов оказывается удобным для описания многих физических, технических, экономических, биологических, социальных и других систем. § 3.1. Понятие графа. Графом G (V, E) называется совокупность двух множеств – непустого множества V (множества вершин) и множества Е его двухэлементных подмножеств множества V (Е – множество ребер). G (V, E) = V; E , V ≠ (, E ⊂ 2V Определение 3.1.1. Граф G – это математический объект, состоящий из множества вершин X = {x1, x2, ..., xn} и множества ребер A = {a1, a2,..., an}. Таким образом, граф полностью определяется совокупностью множеств X, A: G = (X, A). Для многих задач несущественно, являются ли ребра отрезками прямых или криволинейными дугами; важно лишь то, какие вершины соединяет каждое ребро. Существуют два основных вида графов (и множество их подвидов): ориентированные и неориентированные. Если ребрам графа приданы направления от одной вершины к другой, то такой граф называется ориентированным. Ребра ориентированного графа называются дугами. Соответствующие вершины ориентированного графа называют началом и концом. Если направления ребер не указываются, то граф называется неориентированным (или просто графом). Примеры неориентированных графов Граф Вершины Ребра Семья Люди Родственные связи Город Перекрестки Улицы Сеть Компьютеры Кабели Метро Станции Пересадки Листок в клеточку Клеточки Наличие общей границы Примеры ориентированных графов Граф Вершины Дуги Обучение Курсы Необходимое предшествование (например, курс по языку Pascal полезно изучить прежде, чем курс по Delphi, и т.п.) Одевание ребенка Предметы гардероба Необходимое предшествование (например, носки должны быть надеты раньше, чем ботинки, и т.п.) Организация Сотрудники Иерархия (начальник - подчиненный) Пример: на рис.1.изображен неориентированный граф G = (X, A). X = {x1, x2, x3, x4}, A = {a1= (x1, x2), a2=(x2, x3), a3=(x1, x3), a4= (x3, x4)}. рис.1 На рис.2. изображен ориентированный граф G = (X, A). X = {x1, x2, x3, x4}, A = {a1 = (x1, x2), a2 = (x1, x3), a3 = (x3, x4), a4 = (x3, x2)}. рис.2 Определение 3.1.2. Граф называется простым, если каждую пару вершин соединяет не более чем одно ребро. Определение 3.1.3. Граф, имеющий как ориентированные, так и неориентированные ребра, называется смешанным (рис.3). рис.3 Различные ребра могут соединять одну и ту же пару вершин. Такие ребра называют кратными. Определение 3.1.4. Граф, содержащий кратные ребра, называется мультиграфом (рис.4). рис.4 Неориентированное ребро графа эквивалентно двум противоположно направленным дугам, соединяющим те же самые вершины. Ребро может соединять вершину саму с собой. Такое ребро называется петлей (рис.5). рис.5 Определение 3.1.5. Граф с кратными ребрами и петлями называется псевдографом. Множество ребер графа может быть пустым. Множество вершин графа не может быть пустым. Пример. На рис.6. изображен граф G = (X, A). X = {a, b, c, d}, A = (. рис.6 Как в случае ориентированного, так и в случае неориентированного ребра говорят, что вершины x и y инцидентны ребру a, если эти вершины соединены a. Определение 3.1.6. Две вершины называются смежными, если они инцидентны одному и тому же ребру. Два ребра называются смежными, если они имеют общую вершину. Определение 3.1.7. Степенью вершины графа называется число ребер, инцидентных этой вершине. Вершина, имеющая степень 0, называется изолированной, а степень 1 – висячей. Пример. для графа, расположенного на рис.7: d(a) = 1, d(b) = 3, d(b) = 2, d(e) = 2, d(f) = 0. рис.7 Необходимость учитывать ориентацию ребер в орграфе приводит к расщеплению понятия «степень вершины» на две части: полустепенью захода вершины vi (d – (vi)) называется число ребер, заходящих в vi, полустепенью исхода vi (d + (vi)) – число ребер, выходящих из нее. Определение 3.1.8. Граф, степени всех k вершин которого одинаковы, называется однородным графом степени k. Определение 3.1.9. Дополнением данного графа называется граф, состоящий из всех ребер и их концов, которые необходимо добавить к исходному графу, чтобы получить полный граф. Для ориентированного графа множество вершин, в которые ведут дуги, исходящие из вершины х, обозначают G (х), то есть G (х) = {y:.(x,.y)∈.G}. Множество G.(x) называют образом вершины x. Соответственно G.–1(у) – множество вершин, из которых исходят дуги, ведущие в вершину у, G.–1(y) = {x: (x, y) ∈ G}. Множество G.–1(у) называют прообразом вершины y. Пример. В графе, изображенном на рис.8, концами ребра a1 являются вершины x1, x2; вершина x2 инцидентна ребрам a1, a2; степень вершины x3 равна 3; вершины x1 и x3 смежные; ребра a1 и a2 смежные; вершина x4 висячая. В ориентированном графе, изображенном на рис. 9, началом дуги a1 является вершина x1, а ее концом – вершина x2; верши на x1 инцидентна дугам a1 и a2; G (x1) = {x2, x3}, G.(x2) = (, G.–1(x3) = {x1}, G.–1(x1) = (. рис.8рис.9 Определение 3.1.10. Подграфом графа G называется граф, все вершины и ребра которого содержатся среди вершин и ребер графа G. Подграф называется собственным, если он отличен от самого графа (рис.10). Граф Подграфы 1) 2) 3) рис.10 Определение 3.1.11. Граф G = (X, A) – полный, если для любой пары вершин xi и xj существует ребро (xi, xj). Примеры полных графов рис.11. рис.11 Определение 3.1.12. Полным ориентированным графом называется граф, каждая пара вершин которого соединена в точности одним ориентированным ребром. Если с каждого ребра полного ориентированного графа снять направление, то образуется полный граф с неориентированными ребрами. Определение 3.1.13. Граф G = (X, A) – симметрический (рис.12), если для любой дуги (xi, xj) существует противоположно ориентированная дуга (xj, xi). рис.12 Определение 3.1.14. Граф G = (X, A) – планарный, если он может быть изображен на плоскости так, что не будет пересекающихся дуг (рис.13). Рис.13 § 3.2. Способы задания графов Возможны следующие различные способы задания графа: а) указанием множества вершин и множества ребер (дуг) – аналитический способ. Пусть граф G (V, E) - рис.14 задан списком вершин и ребер: V = {A, B, C, D, E}, E = {(A, B), (A, C), (A, D), (B, E), (A, E), (C, D)}. б) посредством графического изображения – геометрический способ (рис.14). Используется в случае небольшого количества ребер и вершин. При большом их числе рисунок теряет свою наглядность. рис.14 в) матрицей смежности. Матрицей смежности ориентированного помеченного графа с вершинами называется матрица А=[aij] i,j =1,….n, строки которой соответствуют вершинам, а столбцы ребрам, в которой aij= 1, если существует ребро (xi, xj) 0, если вершины xi, xj не связаны ребром Граф Матрица смежности 1 2 3 4 5 6 7 A 0 1 0 0 1 0 0 B 0 0 1 1 1 1 0 C 0 0 0 0 0 1 1 D 1 0 0 1 0 0 1 E 1 1 1 0 0 0 0 Матрица смежности однозначно определяет структуру графа. Отметим, что петля в матрице смежности может быть представлена соответствующим единичным диагональным элементом. Кратные рёбра можно представить, позволив элементу матрицы быть больше 1, но это не принято. г) матрицей инцидентности. Матрицей инцидентности для неориентированного графа с n вершинами и m ребрами называется матрица В=[bi,j], i=1, …, n, j=1, …, m, строки которой соответствуют вершинам, а столбцы ребрам. bij= 1, если вершина xi инцидентна ребру uj 0, если вершина xi не инцидентна ребру uj Матрицей инцидентности ориентированного графа с n вершинами и m ребрами называется матрица В=[bi,j], i=1, …, n, j=1, …, m, строки которой соответствуют вершинам, а столбцы ребрам. bij= +1, если вершина xi начальная вершина ребра uj -1, если вершина xi конечная вершина ребра uj 0, если вершина xi не инцидентна ребру uj Граф Матрица инцидентности 1 2 3 4 5 6 A 1 1 1 0 1 0 B 1 0 0 1 0 0 C 0 1 0 0 0 1 D 0 0 1 0 0 1 E 0 0 0 1 1 0 Ориентированный граф Матрица инцидентности 1 2 3 4 5 6 A -1 1 -1 0 -1 0 B 1 0 0 -1 0 0 C 0 -1 0 0 0 1 D 0 0 1 0 0 -1 E 0 0 0 1 1 0 Таким образом, если граф задан одним из указанных способов: аналитическим, геометрическим или матричным, всегда можно перейти к любому другому способу задания. Наиболее часто для задания графа используется аналитический и матричный способы, а геометрический способ служит для иллюстрации полученных результатов. § 3.3. Операции над графами а) Дополнением графа называется граф множеством вершин? которого является множество а множеством его рёбер является множество б) Объединением графов и при условии, что называется граф множеством вершин которого является множество а множеством его рёбер является множество G1 G2 в) Пересечением графов и называется граф множеством вершин которого является множество а множеством его рёбер является множество G1 G2 г) Суммой по модулю два графов и при условии, что называется граф множеством вершин которого является множество а множеством его рёбер – множество т. е. этот граф не имеет изолированных вершин и состоит только из рёбер, присутствующих либо в первом графе, либо во втором графе, но не в обоих графах одновременно. G1 G2 § 3.4. Изоморфизм графов Определение 3.4.1. Графы G1 =.(X1,.A1) и G2 =.(X2,.A2) изоморфны (рис.15), если существует взаимно однозначное соответствие между множествами вершин X1 и X2, такое, что любые две вершины одного графа соединены тогда и только тогда, когда соответствующие вершины соединены в другом графе. рис.15 G1 G2 Изморфные графы рассматриваются как идентичные: их различия связаны со способом реализации, но не с внутренней структурой. Определение 3.4.2. Инвариантом графа называется параметр, имеющий одно и то же значение для всех графов, изоморфных заданному графу. Среди самых очевидных инвариантов отметим следующие: 1. Число вершин |V|=n. 2. Число ребер |E|=m. 3. Число компонент связности. 4. Последовательность степеней, т.е.список степеней всех вершин в убывающем порядке значений. Для решения задач изоморфизма обычно состоят в попытках показать, что два рассматриваемые графа не изоморфны. Для этого составляется список различных инвариантов в порядке, определяемом сложностью вычисления инварианта. Затем последовательно сравниваются значения параметров графов. Как только обнаруживаются два различных значения одного и того же параметра, приходят к заключению, что данные графы не изоморфны. Множество инвариантов, которое позволило бы этой процедуре установить изоморфность графов за полиномиальное время, называется кодом графа. К сожалению, на сегодняшний день такое множество не найдено. По существу, алгоритм рассматриваемого типа сводится к сравнению кодов двух графов. Конечно, рассмотрение большого числа инвариантов увеличивает вероятность правильного заключения об изоморфизме при совпадении всех значений параметров, но в общем случае ничего не гарантирует. § 3.5. Маршруты, циклы в неориентированном графе Пусть G – неориентированный граф. Определение 3.5.1. Маршрутом или цепью в G называется такая последовательность (конечная или бесконечная) ребер a1, a2,... an..., что каждые соседние два ребра ai и ai+1 имеют общую инцидентную вершину. Одно и то же ребро может встречаться в маршруте несколько раз. В конечном маршруте (a1,a2,...an) имеется первое ребро a1 и последнее ребро an. Вершина x1, инцидентная ребру a1, но не инцидентная ребру a2, называется началом маршрута, а вершина xn, инцидентная ребру an, но не инцидентная ребру an–1, называется концом маршрута. Определение 3.5.2. Длиной (или мощностью) маршрута называется число ребер, входящих в маршрут, причем каждое ребро считается столько раз, сколько оно входит в данный маршрут. Замкнутый маршрут называется циклом. Пример. В изображенном на рис. 16 графе рассмотрим два маршрута из вершины x1 в вершину x4: M1 = (a1, a2, a4) и M2 = (a1, a2, a5, a6). рис.16 Длина маршрута M1 равна 3, а длина маршрута M2 равна 4. Определение 3.5.3. Маршрут (цикл), в котором все ребра различны, называется простой цепью (циклом). Маршрут (цикл), в котором все вершины, кроме первой и последней, различны, называется элементарной цепью (циклом). Пример. В приведенном на рис. 17 графе выделим следующие маршруты: рис.17 (a1,a3,a4) – простая элементарная цепь длины 3, т.к. все ребра и вершины попарно различны; (a2,a4,a3) – простой элементарный цикл, т.к. это замкнутый маршрут, у которого все ребра и вершины, кроме первой и последней, различны; (a1,a2,a4,a3) – цепь, которая является простой, но не элементарной, т.к. все ребра различны, но вершина x2 встречается дважды; (a1,a2,a2) – маршрут длины 3, не являющийся ни простой, ни элементарной цепью, т.к. ребро a2 и вершина x2 встречаются дважды. § 3.6. Пути, контуры в ориентированном графе Понятия пути, контура в ориентированном графе аналогичны понятиям маршрута, цикла в неориентированном графе. Определение 3.6.1. Путем ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей дуги. Определение 3.6.2. Число дуг пути называется длиной пути. Определение 3.6.3. Путь называется контуром, если его начальная вершина совпадает с конечной вершиной. Определение 3.6.4. Путь (контур), в котором все дуги различны, называется простым. Определение 3.6.5. Путь (контур), в котором все вершины, кроме первой и последней, различны, называется элементарным. Следует усвоить, что понятиям ребра, маршрута, цепи, цикла в неориентированном графе соответствуют понятия дуги, пути, ориентированной цепи, контура в ориентированном графе. Для лучшего запоминания приведем эти термины в таблице: Неориентированный граф Ориентированный граф Ребро Дуга Маршрут Путь Цикл Контур Пример. В приведенном на рис. 18. графе выделим следующие пути: (x1,x2,x3,x4) – простой элементарный путь, т.к. каждая вершина и каждая дуга используются не более одного раза; (x2,x5,x6,x7,x2) – простой элементарный контур, т.к. это замкнутый путь, в котором все дуги и вершины, кроме первой и последней, различны. рис.18 § 3.7. Связность графа Определение 3.7.1. Неориентированный граф называется связным, если каждая пара различных вершин может быть соединена, по крайней мере, одной цепью. Определение 3.7.2. Ориентированный граф называется сильно связным, если для любых двух его вершин xi и xj существует хотя бы один путь, соединяющий xi с xj. Определение 3.7.3. Ориентированный граф называется односторонне связным, если для любых двух его вершин, по крайней мере, одна достижима из другой. Определение 3.7.4. Компонентой связности неориентированного графа называется его связный подграф, не являющийся собственным подграфом никакого другого связного подграфа данного графа (максимально связный подграф). Пусть G = (X, A) неориентированный граф с множеством вершин X = {x1, ..., xn}. Квадратная матрица S = (sij) порядка n, у которой sij = 1, если вершины и принадлежат одной компоненте связности, 0, в противном случае. называется матрицей связности графа G. Для ориентированного графа квадратная матрица T = (tij) порядка n, у которой tij = 1, если существует путь из xi в xj и из xi в xj, 0, в противном случае. называется матрицей связности. Пример. У неориентированного графа, изображенного на рис. 19 две компоненты связности. Первая компонента связности включает вершины x1, x2, x4, x5, а вторая состоит из одной вершины x3. Граф Матрица связности рис.19 1 1 0 1 1 1 1 0 1 1 0 0 1 0 0 1 1 0 1 1 1 1 0 1 1 Пример. У ориентированного графа, изображенного на рис. 20 две компоненты сильной связности. Первая компонента связности включает вершины x1, x2, x3, x5, а вторая состоит из одной вершины x4. Действительно, для любой пары вершин из множества {x1, x2, x3, x5} существует хотя бы один путь, соединяющий эти вершины. Например, путь (x1, x2, x5, x3, x1) соединяет все эти вершины. Из вершины x4 нет пути ни в одну вершину графа. Граф Матрица связности рис.20 1 1 1 0 1 1 1 1 0 1 1 1 1 0 1 0 0 0 1 0 1 1 1 0 1 Мы видим, что 1 – ая, 2 – ая, 3 – ая и 5 – ая строки матрицы S одинаковы. § 3.8. Деревья, лес Определение 3.8.1. Неориентированным деревом (или просто деревом) называется связный граф без циклов. Дерево есть связный граф, содержащий n вершин и n – 1 ребер, дерево есть граф, любые две вершины которого можно соединить простой цепью. Пример. Графы, изображенные на рис 21, являются деревьями. рис.21 Если граф несвязный и не имеет циклов, то каждая его связная компонента будет деревом. Такой граф называется лесом. Можно интерпретировать рис.21 как лес, состоящий из трех деревьев. Определение 3.8.2. Остовным деревом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом. Пример. Для графа, изображенного на рис. 22 а), графы на рис. б и в являются остовными деревьями. рис.22 Определение 3.8.3. Ориентированным деревом называют граф, в котором в каждую вершину, кроме одной, называемой корнем дерева, заходит ровно одна дуга. В корень дерева ни одна дуга не заходит. Вершины, из которых не выходит ни одна дуга, называются листьями (рис.23). рис.23 § 3.9. Взвешенные графы Определение 3.9.1. Взвешенный граф – это граф дугам, которого поставлены в соответствие веса, так что дуге (xi, xj) сопоставлено некоторое число c (xi, xj) = cij, называемое длиной (или весом, или стоимостью) дуги. Обычный (не взвешенный) граф можно интерпретировать как взвешенный, все ребра которого имеют одинаковый вес 1. Определение 3.9.2. Длина пути во взвешенном графе - это сумма длин (весов) тех ребер, из которых состоит путь. Определение 3.9.3. Расстояние между вершинами – это длина кратчайшего пути. Например, расстояние от вершины a до вершины d во взвешенном графе, изображенном на рис. 24, равно 6. рис.24 Примеры взвешенных графов Граф Вершины Вес вершины Ребра (дуги) Вес ребра (дуги) Путешествия Государства Площадь территории Наличие наземной границы Стоимость получения визы Карта Государства Цвет на карте Наличие общей границы - Сеть Компьютеры - Сетевой кабель Стоимость кабеля § 3.10. Эйлеровы и гамильтоновы графы Определение 3.10.1. Если граф имеет цикл (не обязательно простой), содержащий все ребра графа по одному разу, то такой цикл называется эйлеровым циклом, а граф называется эйлеровым графом. Определение 3.10.2. Если граф имеет цепь (не обязательно простую), содержащую все вершины по одному разу, то такая цепь называется эйлеровой цепью, а граф называется полуэйлеровым графом. Эти понятия возникли в статье Эйлера в 1735 г., в которой он решал задачу о Кенигсбергских мостах и впервые ввел понятие графа. На рис.25, а приведен план расположения семи мостов в Кенигсберге"