- •Тема 2. Элементы теории графов.
- •§ 2.1. Основные понятия.
- •§ 2.2. Отношения и характеристики элементов графа
- •§ 2.3.1. Задание графов через соответствие
- •Пример 2.
- •§ 2.3.2. Матрица смежности. Задать в графе отношение смежности – это указать, какие вершины смежны. Обычно это задается матрицей смежности.
- •Пример 4.
- •§ 2.3.3. Матрица инцидентности Задать отношение инцидентности - значит указать, какие вершины и ребра графа являются инцидентными. Такое отношение задается матрицей инцидентности.
- •§ 2.4. Подграфы
- •§ 2.5. Изоморфизм графов.
- •§ 2.6. Типы графов.
- •§ 2.7. Маршруты и пути.
- •§ 2.7.1. Маршрут, путь, вес и длина пути.
- •§ 2.7.2. Цепи, орцепи, простые цепи и простые орцепи.
- •§ 2.7.3. Циклы, орциклы, простые циклы, простые орциклы (контуры).
- •§ 2.7.3. Классификация маршрутов.
- •§ 2.8. Степени связности графов
- •§ 2.8. Достижимость и связность.
- •§ 2.8.1. Матрицы достижимостей и контрдостижимостей. Существенные вершины
- •§ 2.9. Связность.
- •§ 2.9.1. Степени связности графов
- •§ 2.9.2. Нахождение сильных компонент графа. Максимальный подграф.
- •§ 2.9.3. Конденсация графа. Базы.
- •§ 2.10. Пути между заданными вершинами
- •§ 2.10.1. Кратчайший путь между двумя заданными вершинами s и t
- •§ 2.10.2. Кратчайший (s t)-путь. Случай неотрицательной матрицы весов
- •§ 2.10.4. Наиболее надёжный путь
- •§ 2.11. Деревья
- •§ 2.11.1. Типы деревьев
- •§ 2.11.2. Количество остовных деревьев графа.
- •§ 2.11.3. Кратчайший остов графа (sst)
- •§ 2.13. Сети. Потоки в сетях.
ТГ
Тема 2. Элементы теории графов.
Леонард Эйлер (1707 – 1783)
Родился в Швейцарии, г. Базель. Отец был пастором. В Базельском университете Л.Э. готовился к карьере священника по желанию отца, но также посещал математические лекции профессора Иоганна Бернулли, который принадлежал научной школе Лейбница.
В 1725 году в России организовывалась Петербургская академия наук, Л.Э получил приглашение преподавать здесь. Он согласился, но приехал в Россию только через два года, в 1727 году, закончив университет. Вскоре мировая математическая общественность единодушно признала его первым математиком мира. В 1741 году, когда Россией правила Анна Леопольдовна, и науки не входили в круг её интересов, Л.Э уезжает в Берлинскую академию наук. В 1966 г. он вновь возвращается в Россию.
В последние годы жизни он почти совсем потерял зрение, писать сам не мог, поэтому диктовал ученикам. Только за один 1777 год он с секретарём подготовил 100 статей – почти 2 статьи в неделю.
Умер Эйлер в 1783 году в возрасте 76 лет. Он оставил более 800 научных трудов, причём многие из них – 2-3 томные издания. Его статьи издавались в академическом журнале, и после его смерти продолжали издаваться в течение 80 лет!
Эйлер был самым разносторонним математиком, занимался всеми вопросами современной ему математики и её приложениями, а некоторые разделы стал разрабатывать впервые. Его интересовали:
теория чисел;
теория движения луны;
геометрия;
оптические приборы;
алгебра;
сопротивление материалов;
тригонометрия;
баллистика;
первая теория расчёта действия турбин;
основы теории гироскопа;
начала топологии и мн. др.
Н ачало теории графов все единодушно относят к 1736 году, когда Л. Эйлер не только решил популярную в то время задачу о Кёнигсбергских мостах, но и нашёл критерий существования в графе специального маршрута (Эйлерова цикла).
Задача о мостах. Река образует острова. Через два речных рукава перекинуто 7 мостов.
Спрашивается, можно ли пройти все 7 мостов так, чтобы каждый был пройден по одному лишь разу.
Через век, в середине 19 столетия, теория графов была продвинута инженером – электриком Кирхгофом, который разработал теорию деревьев для исследования электрических цепей.
Нигде в других науках теория графов долго не применялась и развивалась только в приложениях: игры, занимательные задачи, математические ребусы.
Термин «граф» впервые появился в книге выдающегося венгерского математика Кёнига в 1936 году. За последние ¾ столетия теория графов превратилась в один из наиболее развитых разделов математики. Одна из причин - становление и развитие науки об управлении кибернетики. Теория графов является существенной частью математического аппарата кибернетики.
§ 2.1. Основные понятия.
Опр.1. Пусть V – непустое множество, Е12 – множество всех его двухэлементных подмножеств, Е– любое подмножество множества Е12 (Е Е12). Тогда пара G = (V,E) называется графом (неориентированным графом). Элементы множества V называются вершинами, а множества Е – ребрами графа.
Вершины и рёбра графа называются элементами графа. Число вершин графа G (мощность множества вершин V) называется порядком графа и обозначается │G│. Если │G│=n, а число его рёбер │Е│=m, то G называют (n,m)-графом.
Приведённое определение графа является весьма абстрактным. Для наглядности представления введём геометрическую интерпретацию графа. С этой целью будем рассматривать в евклидовом пространстве фигуры определённого вида. Каждая из этих фигур g состоит из различных вершин b1, b2, b3 … и кривых (дуг или отрезков прямых), каждая из которых соединяет некоторую пару вершин bi, bj. Возможно вырождение bi = bj. Предполагается, что никакая внутренняя точка кривой не является вершиной или внутренней точкой другой кривой.
Опр.2. Фигура g называется геометрической интерпретацией графа G, если существует взаимно однозначное соответствие между вершинами фигуры g и вершинами графа G, а также между кривыми фигуры g и рёбрами графа G, такое, что соответствующие кривые и рёбра соединяют соответствующие вершины.
Спрашивается, любой ли граф можно реализовать в евклидовом пространстве и какова мерность пространства для реализации любого графа? В теории графов существует теорема, в которой доказывается, что каждый конечный граф G можно реализовать в трёхмерном евклидовом пространстве.
Пример 1.
Пусть дан граф G = (V,E). Ребро {u, v}E обозначают uv. Говорят, что ребро uv соединяет вершины u и v, а вершины u и v являются концевыми для данного ребра.
Если порядок концевых точек ребра е безразличен, то говорят, что е – неориентированное ребро. Как уже говорилось, обозначается ребро е = {а,b}. Если этот порядок важен, то е называют ориентированным ребром – дугой. Обозначается в этом случае ориентированное ребро (дуга) е = (a,b), причём (a,b)(b,а). При этом а называют начальной вершиной дуги, а b – конечной вершиной. На рисунках дуги обозначают стрелками.
Граф, состоящий из неориентированных рёбер, называется неориентированным графом. Граф, состоящий из ориентированных рёбер, называется ориентированным графом, орграфом. Элементы множества Х графа G называются вершинами, как и в случае неориентированного графа, а элементы множества А – дугами орграфа. При геометрической интерпретации дуги графа обозначаются линиями со стрелками, направленными от первого элемента дуги ко второму. При этом первый концевой элемент дуги называется её началом, а второй (на который указывает стрелка) – её концом. Петлёй называется дуга, начальные и конечные вершины которой совпадают.
Чтобы от неориентированного графа перейти к ориентированному, надо удвоить каждое его ребро и придать каждой получившейся паре рёбер противоположную направленность.
Чтобы перейти от ориентированного графа к неориентированному (получить его неориентированный двойник), надо пренебречь направлением дуг орграфа. Обозначается операция пренебрежения направлением дуг следующим образом: .