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

Будем говорить, что этот маршрут соединяет первую и последнюю вершину. Если существует маршрут, то последняя вершина называется достижимой из первой вершины.

Маршрут, в котором нет повторяющихся ребер, называется цепью.

Маршрут, в котором нет повторяющихся вершин (кроме первой и последней), называется простой цепью.

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

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

Эти части называются компонентами связности.

Ребро называется циклическим, если оно входит хотя бы в один цикл графа. В противном случае ребро называется ациклическим.

Утверждение.

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

Связный граф, у которого все ребра ациклические, называется деревом.

Несвязный граф, компонентами связности которого являются деревья, лесом.

Свойства деревьев.

1. Чтобы простой связный граф был деревом, необходимо и достаточно, чтобы число вершин было больше числа ребер на один.

2. Чтобы граф был деревом, необходимо и достаточно, чтобы любые две вершины его соединялись единственным маршрутом.

3. Граф будет деревом тогда и только тогда, когда добавление любого нового ребра приводит к появлению ровно одного цикла.

Лекция 12

Эйлеровы графы

Дан граф. Требуется найти в нем маршрут, проходящий по каждому ребру ровно один раз. Начало и конец – в одной вершине.

Такой маршрут называется Эйлеровым циклом, а граф, в котором он существует, называется Эйлеровым графом.

Степень вершины в графе – это число ребер, инцидентных этой вершине.

Критерий эйлеровости графа.

Для того, чтобы связный граф без петель был Эйлеровым, необходимо и достаточно, чтобы степень его вершины была четным числом.

Планарные графы.

Определение.

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

Сама же укладка графа без пересечения ребер называется плоским графом.

Л юбой граф можно изобразить в трехмерном пространстве без пересечения ребер.

Для любого графа x_i, соединяющего 2 вершины проводим новую плоскость, содержащую эту прямую, а ребро рисуем на плоскости.

Граф будет планарным, если существует его укладка на сфере.

Доказательство следует из взаимно однозначного соответствия точек на сфере с точками плоскости из стереографических проекций.

Следствие. Граф любого выпуклого многогранника планарен.

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

Теорема Эйлера о плоских графах.

Формула Эйлера.

Для плоского графа справедливо соотношение.

M – N + P = 2.

Докажем индукцией по числу граней

P = 1

Если P = 1, то граф – дерево. В нем нет ни одного цикла. У дерева число вершин больше числа ребер на 1.

M = N + 1

N + 1 – N + 1 = 2 – справедливо.

Пусть p = k, и утверждение верно.

Тогда оно верно и при P= k+1

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

N1 = N – 1

P1 = P – 1

M = M

k + 1-1 = k

Для g1 справедливо предположение индукции.

M1 + N1 + P1 = 2

M – N – 1 + K = 2

M – N + K – 1 = 2

M – N + P = 2

Что и требовалось доказать.

Следствие 1.

Для плоского связного простого графа справедливо соотношение

n <= 3*(m-2)

Следствие 2.

Для плоского связного простого графа без треугольных граней справедливо соотношение

n <= 2*(m-2)

Следствие 3.

Граф K5 – непланарен.

m > 2

И если бы он был плоским, то для него было бы справедливо следствие 1.

N <= 3*(m-2)

10 <= 9 – неверно.

Противоречие. Значит, он не может быть нарисован плоским.

Следствие 4.

Граф K3-3 непланарен.

Нет треугольных граней.

Если бы он был плоским, то для него было бы справедливо следствие 2.

9 <= 2*(6-2)

9 <= 8 – неверно.

Противоречие из предположения, что он не может быть плоским.

Операцией разбиения ребра графа называется следующая процедура:

Ребро удаляется из графа, и в граф добавляется новая вершина, соединенная новыми ребрами с концами данного ребра.

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

Теорема Понтрягина – Куратовского.

Чтобы граф был планарным, необходимо и достаточно, чтобы он не содержал гомеоморфных подграфов.

Лекция 13

Сети. Пути в орграфах. Остовы минимальной длины

Определение. Двуполюсной сетью называется связный граф без петель с двумя выделенными вершинами, которые называются полюсами.

Полюса

Двуполюсная сеть называется сильно связанной (связной), если через любое ребро проходит простая цепь, соединяющая полюса. В ней нет повторяющихся вершин.

Параллельная сеть – сеть вида

Последовательная сеть – сеть вида

П (пи) сети – последовательно-параллельные сети

Примеры П-сетей

Такая сеть называется мостиковой.

Контактными схемами называются сильносвязные двуполюсные сети, каждому ребру которой поставлено в соответствие x или NOT(x).

X Not Y

Not Z

Z Not X

Любой контактной схеме (КС) можно поставить в соответствие булеву функцию (функцию проводимости) по правилу:

Для любой простой цепи, соединяющей полюса, записываем ЭК тех переменных, которыми помечены ребра этой цепи.

Затем берем дизъюнкцию всех ЭК. Получим искомую функцию проводимости.

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

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

Чтобы построить минимальную КС, надо выписать минимальную ДНФ для данной функции, упростить путем вынесения за скобки, нарисовать П-сеть, реализующую КС для функции и постараться найти мостиковые соединения.

Минимальные пути в графах

Путем в графе (в орграфе) называется маршрут, движение по которому любого ребра проходит в соответствии с направлением этого ребра.

Контуром в орграфе называется замкнутый путь, в котором вершины не повторяются (кроме первой и последней).

Орграф, в котором нет ни одного контура, называется бесконтурным.

Первая задача о минимальном пути.

Дан граф. Выделено две вершины. Найти путь из одной вершины в другую, состоящий из наименьшего числа ребер.

Введем обозначения

Г(V) – множество вершин, в которые можно попасть из вершины V, пройдя только по одному ребру в его направлении.

Г-1(V) – множество вершин, из которых можно попасть в вершину V, пройдя только по одному ребру.

Алгоритм.

1. Исходной вершине A присваиваем метку 0.

2. Любому Г(А), которые еще не имели меток, присваиваем метку М = 1.

3. Для любой V, принадлежащей Г(А) находим Г(V) и любой V, принадлежащему Г(V), если она не имела метку, даем метку 2.

4. И так далее до тех пор, пока конечная вершина не получит метку.

5. Выбираем путь по Г-1(V).

Может произойти такое, что пути из А в В нет вообще.

Тогда на некотором шаге при обратном ходе нужной вершины нет.

Вторая задача.

Если каждому ребру поставить в соответствие некоторое целое положительное число, называемое его длиной и требуется найти путь из А в В, такой, что _i = minimum. (r или l – длина ребра)

Алгоритм будет следующий.

1. Метка для ребра А 

Для Vi i = +(бесконечность) – очень большое число, большее суммы всех длин ребер всего графа.

L(Vi, Vj) – длина ребра, идущего из вершины Vi в Vj. Направление важно.

1. Для любого ребра из графа проверяем выполнение неравенства.

j - i > L(Vi, Vj) *

Если это неравенство выполняется, то меняем метку j на новую.

j = i + L(Vi, Vj) и так до тех пор, пока выполняется *.

Если * нигде не выполняется, то та метка, которая будет стоять у вершины В и будет равна длине минимального пути из А в В, а сам путь строится движением назад из В в А.