Дискретная математика

Лекция 1 Графы

Понятие графа.

Смежность.

Виды графов.

2) Если допустить, что элементами множества Е являются пары с одиночными вершинами, то такое ребро называе6тся петлей, а граф – псевдографом.
3) Если допустить, сто V является не множеством, а набором элементов, то есть допустимо наличие одинаковых элементов, то у нас могут появиться кратные ребра, а граф будет мультиграфом.
4) Если множество Е содержит элементы, состоящие более чем из двух вершин, то такой граф называется гиперграфом.

Изоморфизм.

Инварианты.
Графы характеризуются некоторыми параметрами: число вершин, ребер, степень вершины и так далее. Параметры, которые не меняются с преобразованием графа, называются инвариантами.
Рассмотрим следующее утверждение:
Если при преобразовании количество вершин, ребер и степень вершины являются инвариантами, то преобразование - изоморфизм.
Однако наше предложение не является теоремой. В этом нас убеждает граф 3, у которого перечисленные характеристики совпадают с характеристиками графа 1 , но эти графы не изоморфны.
Пока неизвестен набор инвариантов, позволяющий определить изоморфны ли графы.

Подграфы.

Маршруты. Цепи. Циклы.

Расстояние.

Связность.
13
13.

Задание графа.

БГТУ им. В.Г. Шухова
Кафедра информационных технологий
Спасибо за внимание!

Лекция 2 Графы

Метод математической индукции:
Мы заметили некоторую закономерность в значениях изучаемой последовательности. Проверяем эту закономерность для n=1. Предполагаем, что формула справедлива при некотором n и доказываем, что она справедлива для n=n+1. Подставляем в формулу n+1 и получаем формулу, которой соответствует (n+1) – ый член. Затем получаем (n+1) – ый член, исходя из общего принципа построения последовательности. Получим формулу для n+1. Если эти формулы совпадают, то закономерность считается доказанной.

Двудольные графы.

Взвешенный граф.
Пусть задан граф G(V,E). Если каждому ребру этого графа поставлено в соответствие некоторое число, то граф называется взвешенным.
При задании взвешенных графов в матрицу смежности (или список) заносятся веса.

Задача о кратчайшем пути.

Алгоритм Форда.

Задача о максимальном потоке.

Теорема Форда – Фолкерсона.

Связность в графах.
Пусть задан граф G, у которого р – вершин и q – ребер. Если для двух вершин существует цепь, то они называются связными. Граф называется связным, если у него все вершины связны. Если граф может быть задан в виде объединения нескольких подграфов, то каждый такой подграф называется компонентой связности, а количество компонент обозначается буквой k.

Циклы.
Цепь, в которой начальная и конечная вершины совпадают, называется циклом. Для циклов вводится понятие циклонического числа z= q-р+ k.
Если z=0, то граф не имеет циклов. Если же z=1, то граф имеет один цикл. Для мультиграфа z выражает число циклов.
Например: при р=4, q=8 и k=1: z= q-р+ k=8-4+1=5.

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

Деревья.
В деревьях обычно одну из вершин выделяют и называют корнем.
Вершины, удаленные от корня на одно и то же расстояние образуют ярус. V0- нулевой ярус, V1, V2 – первый ярус, V3, V4, V7, V8, V9 – второй ярус, V5, V6, V15, V16, V17, V18, V19 - третий ярус, V10, V11, V12, V13, V14 – четвертый ярус.
Вершины, степень которых равна 1 (висячие) называются концевыми, или листьями. На рис. 33 – это вершины , V10, V11, V12, V13, V14V15, V16, V17, V18, V19 .
Упорядоченное объединение непересекающихся деревьев называется лесом. Ясно, что лес является несвязным графом.
Остовом связного графа называется подграф, содержащий все его вершины и являющийся деревом. Такое дерево называют покрывающим граф.
Каждая вершина дерева называется узлом.

Задача о минимальном остовном дереве.

Жадный алгоритм Краскала построения кратчайшего остова.
Пусть задан связный граф, имеющий р вершин и с различными длинами своих ребер. На первом шаге находим ребро наименьшей длины и помещаем его в будущий остов. Получили подграф. Затем из оставшихся ребер находим второе ребро наименьшей длины и помещаем его в подграф - будущий остов. Затем из оставшихся ребер находим ребро наименьшей длины, не образующее цикла с ранее выбранными ребрами, и помещаем его в подграф. Продолжаем этот процесс до тех пор, пока есть ребра, не образующие цикл в подграфе. Т.к. граф связный, то в подграф попадут все вершины, т.е. подграф будет содержать р вершин. Следовательно, полученный в конечном итоге подграф будет остовным. Т.к. он ацикличен, то он дерево. А т.к. в него включались ребра наименьшей длины, то оно и будет искомым остовом.

Ориентированные деревья.
Орграф называется ориентированным деревом (ордеревом), если:
существует единственный узел, полустепень захода которого равна 0 (корень),
полустепень захода остальных узлов равна 1,
все узлы достижимы из корня.

Ориентированные деревья.
Свойства ордеревьев:
1.Если q – число дуг, а p – число узлов ордерева, то q = p -1.
2. Если в ордереве отменить ориентацию ребер, то получится свободное дерево.
3. Для каждого узла существует единственный путь из корня.
4. В ордереве нет контуров.
5. Если в свободном дереве любую вершину назначить корнем, то получится ордерево.

Упорядоченные деревья.
Если в качестве корня в ордереве выбрать какой-нибудь узел v, то множество узлов, достижимых из v образует орграф с корнем v (поддерево).
Если относительный порядок поддеревьев установлен, то ордерево называется упорядоченным.
Ордеревья и упорядоченные деревья часто используются в программировании. Например, для представления выражений, вложенных блоков, для представления иерархической структуры операторов, структуры вложенности каталогов и файлов, скобочные структуры и т.д.

Бинарные деревья.

Эйлеровы циклы.

Эйлеровы циклы.

Гамильтоновы графы.