Графы: основные понятия

Дискретная математика ГРАФЫ. Основные понятия Преподаватель: Шилова З.В. Происхождение графов 1. Исторический аспект. Л. Эйлер (1736 г.). Задача о кенигсбергских мостах. «Четыре части города Кенигсберга (а, b, с, d на рис.1) соединены семью мостами. Необходимо определить, можно ли, выйдя из любой части города и пройдя по каждому мосту ровно один раз, вернуться в исходное место.» Рис.1. Задача о кенигсбергских мостах 2. Определение графа Графом G называется пара множеств G = (X, Е), где X — непустое множество вершин {х1, х2, ..., хn}, а элементами множества Е являются некоторые двухэлементные подмножества X, т. е. Е = {(хi, хj)}. Эти двухэлементные подмножества называются ребрами. Пример. Рис. 2. Петля G = ({Х1, Х2, Х3, Х4}, {(Х1, Х1), (Х1, Х2), (Х1, Х3), (Х2, Х3), (Х3, Х4)}) 3. Задание графа Матрица смежности графа. Номера строк и столбцов этой матрицы совпадают с номерами вершин графа, а ее элемент αij есть число ребер, соединяющих вершины хi и хj. Мультиграф. Пример. 0 2  A  1  0  0 Рис. 3. Мультиграф 2 1 4 4 1 0 0  1  0 0    Ориентированные графы 1. Определение. Ориентированным (или орграфом) D, называется пара D = (Х,А), где X — произвольное множество вершин и А — множество упорядоченных пар вершин, называемых дугами AXX В паре (хi,хj) первая вершина хi называется началом дуги, а вторая хj — концом дуги. 2. Пример (дуги изображаются стрелками). Рис. 4. Ориентированный граф Ориентированный граф и бинарные отношения Пример (отношение порядка). На ориентированном графе D(X, А) задано отношение порядка, если для любых двух вершин хi и хj, удовлетворяющих условию хi≥хj существует путь из хi в хj. На рис.8 представлено изображение графа, на котором определено отношение порядка «хi не больше хj». Рис. 8. Интерпретация свойств бинарных отношений с позиции теории графов Рефлексивность отношения «быть не больше» означает истинность условия Хi  Хi. Следовательно, вершина Хi не больше самой себя, т. е. имеется путь из Хi в Хi , что обусловливает допустимость петли для вершины хi. Антисимметричность (Хi  Хj) /\ (Хj  Хi) → (Хi ≡ Хj) показывает, что если на графе имеется путь из Хi в Хj, то имеется и путь из Хj в Хi. Таким образом, в графе имеется контур. Транзитивность означает истинность выражения (Хi  Хj) /\ (Хj Хк) → (Хi  Хк). Это эквивалентно тому, что вершины хi, хj, хк последовательно встречаются на одном и том же пути. Отношение строгого порядка антирефлексивно и асимметрично, поэтому его можно задать на графе без петель и без контуров. 4. Матрица инциденций. Номера строк матрицы инциденций равны номерам вершин, а номера столбцов — номерам дуг. Если дуга выходит из вершины хi, то соответствующий элемент матрицы инциденций αij равен —1. Если же дуга аj входит в вершину хk, то элемент αkj равен +1. Все другие элементы столбца j равны нулю. Пример. 0  0 1 1 0 1 0 0 1 1   A  1 0 0   1 1    0 1 0 1 0  Рис. 4. Взвешенные графы Приписывание ребрам и дугам некоторых количественных значений, качественных признаков или характерных свойств, называемых весами. В простейшем случае это может быть порядковая нумерация ребер и дуг, указывающая на очередность при их рассмотрении (приоритет или иерархия). Вес ребра или дуги может означать длину (пути сообщения), количество набранных очков (турниры), характер отношений между людьми (сын, брат, отец, подчиненный, учитель) и т.п. Вес вершины означает любую характеристику соответствующего ей объекта (цвет изображаемого вершиной предмета, возраст человека и т.п.) Маршруты 1. Определение. Пусть дан неориентированный граф G(X, E). Маршрутом длины m называется некоторая последовательность m ребер графа G(X, E), такая, что вершины двух соседних ребер последовательности совпадают. 2. Примеры маршрутов. Последовательности ребер (а1, а6, а5, а1, а3) и (а2, а1, а4, а6). Первый из них проходит последовательно, через вершины х1, х2, х3, х2, х1, х3, соединяя х1 с х3. Второй, проходя через вершины х2, х1, х2, х3, х2, образует замкнутый маршрут, так как приводит в ту же вершину, из которой и начался. Виды маршрутов Маршрут, не содержащий повторяющихся дуг, называется путем. Путь, не содержащий повторяющихся вершин, называется простым путем. Замкнутый путь называется контуром. Простой контур — контур, не имеющий повторяющихся вершин. Если в графе содержится хотя бы один контур, то это контурный граф. 3. Виды графов Связный граф Цепь: простая цепь, цикл Простой цикл Эйлеров цикл Гамильтонов цикл