2.1 Определение графа
Рассмотрим множество Х, состоящее из соединенных некоторым образом точек. Элементы - вершины графа. Граф G=G(X) с множеством вершин Х есть некоторое семейство сочетаний или пар вида
указывающие, какие вершины считаются соединенными.
В соответствии с геометрическим представлением графа каждая конкретная пара называется ребром (дугой) графа, и - концевые точки.
Можно определить понятие графа иначе, если представить себе некоторое множество точек плоскости Х, называемых вершинами, и множество направленных отрезков D, соединяющих все или некоторые из вершин и называемых дугами. Т.е. математически граф G можно определить как пару множеств G=(X, D). Примерами графа может являться карта автомобильных или железных дорог, схемы соединения электрических цепей и т.п.
Можно считать, что множество направленных дуг D, соединяющих элементы множества Х, отображают это множество само в себя. Поэтому можно считать граф заданным, если дано множество его вершин Х и способ отображения Г множества Х в Х. Таким образом, граф G есть пара (Х, Г), состоящая из множества Х и отображения Г, заданного на этом множестве.
G=(Х, Г). 2.1
Так, рис. 2.1 изображен граф, вершинами которого являются точки a, b, c, d, e, g, h, а дугами – отрезки (a, a), (c, b), (c,d), (c, e), (d, c), (d, d), (e, d), (g, h). Отображение приведенного графа будет определяться следующим образом: Га=а; Гb=; Гс={b, d, e}; Гd={d,c}; Ге=d; Гg=h; Гh=.
Рис. 2.1
Нетрудно видеть, что данное определение графа полностью совпадает с определением отношения на множестве.
В определении ребра можно принимать или не принимать во внимание порядок расположения двух его концов. Если этот порядок несуществен, т.е. если , то D есть неориентированное ребро, если же порядок существен, то D называют ориентированным ребром, и при этом хi –начальная вершина, – конечная вершина.
Граф называется ориентированным, если ориентированы все его ребра.
неориентированный граф ориентированный граф
Рис. 2.2
В ряде случаев имеет место смешанные графы.
Как в случае ориентированного, так и неориентированного ребра говорят, что ребро D=(хi, xj) инцидентно вершинам xi и xj, а также, что xi и xj инцидентны ребру D. Вершина, не инцидентная никакому ребру, называется изолированной. Часто имеет смысл учитывать только неизолированные вершины.
Граф, состоящий только из изолированных вершин, называется нуль-графом.
Наиболее важным случаем является полный граф G=(X, D), ребрами которого являются всевозможные пары ( ) для двух различных вершин хi и xj из Х. На рис. 2.3 приведены полные графы.
Рис. 2.3
В ориентированном полном графе имеются пары ребер, по одному в каждом направлении, соединяющие любые две различные вершины xi и xj. Ребра, у которых обе концевые точки совпадают L=(a, a) называются петлей.
(См. рис. 2.1 вершины “а”, “d”). Петля обычно считается неориентированной. Можно расширить полный граф до полного графа с петлями, добавляя петлю в каждой вершине.
Допускается, чтобы пара вершин соединялась несколькими различными ребрами.
Для каждого ориентированного графа существует обратный граф G*, получаемый изменением ориентации каждого из ребер графа G на противоположное.
Для каждого ориентированного графа существует также соотнесенный неориентированный граф Gu, ребрами которого являются ребра графа G, но уже без ориентации. Иногда удобно превратить неориентированный граф G в ориентированный граф Gd при помощи процесса удвоения, состоящего в замене каждого ребра G парой ребер с теми же вершинами и приписыванием им (ребрам) противоположных ориентаций.
Граф называется плоским если он может быть изображен на плоскости так, что все пересечения ребер являются вершинами G.
Подграфом GA графа G=(X, Г) называется граф, в который входит лишь часть вершин графа G, образующих множество А, вместе с дугами, соединяющими эти вершины. Например, очерченная пунктиром область на рис. 2.1. Математически это записывается следующим образом:
GA=(A, ГА), 2.2
где
2.3
Частичным графом G по отношению к графу G=(X, Г) называется граф, содержащий только часть дуг графа G, т.е. определяемый условием
G=(X, ), 2.4
где
Например, если G=(Х, Г) – карта автомобильных дорог России, тогда карта дорог Нижегородской области представляет собой подграф, а карта главных автомагистралей России – частичный граф.
Путем в графе G называют такую последовательность дуг d=(u1, u2, …uk), в которой конец каждой предыдущей дуги совпадает с началом следующей. Путь d, последовательными вершинами которого являются вершины a, b, c, … m обозначается через d=(a, b, c, … m).
Длиной пути d=(u1, u2, … uk) называют число l(d)=k, равное числу дуг, составляющих путь d. Иногда каждой дуге ui приписывают некоторое число l(ui), называемое длиной дуги. Тогда длина пути определяется как сумма длин дуг, составляющих путь
. 2.5
Путь, в котором никакая дуга не встречается дважды, называется простым. Путь, в котором никакая вершина не встречается дважды, называется элементарным.
Контур – это конечный путь d=(x1, x2, … xk), у которого начальная вершина х1 совпадает с конечной xk. При этом контур называется элементарным, если все его вершины различны (за исключением начальной и конечной, которые совпадают). Контур единичной длины, образованный дугой вида (а, а), называется петлей. Так, на рис. 2.1 (e, d, c, b) – путь, (с, e, d, c) – контур, (d, d) –петля.
Для неориентированного графа соответственно вводятся понятия цепи и цикла. Цепь (цикл) называется эйлеровой, если она проходит через все ребра по одному разу. Цепь (цикл) называется гамильтоновой, если она проходит через все вершины графа по одному разу.
- 1. Элементы теории множеств
- 1.1 Понятие множества. Основные определения
- Способы задания множества
- Равенство множеств
- Подмножество
- Операции над множествами
- Предварительные замечания
- Объединение множеств
- 1.5.3 Пересечение множеств
- 1.5.4 Разность множеств
- 1.5.5 Симметрическая разность
- 1.5.6 Универсальное множество
- 1.5.7 Дополнение множества
- Принцип двойственности в алгебре множеств
- Тождества алгебры множеств
- Разбиение множества
- Упорядочение элементов и прямое произведение множеств
- Упорядоченное множество
- Прямое произведение множеств
- 1.9.3 Проекция множества
- 1.10 Соответствия
- 1.10.1 Обратное соответствие
- 1.10.2 Композиция соответствий
- 1.10.3 Отображения и функции
- 1.10.4 Основные свойства отображений
- 1.11 Функция
- 1.11.1 Способы задания функции
- 1.11.2 Сужение функции
- 1.11.3 Обратная функция
- 1.11.4 Функция времени
- 1.11.5 Понятие функционала
- 1.11.6 Понятие оператора
- 1.12 Отношения
- 1.12.1 Задание бинарных отношений
- Свойства отношений
- 1.12.3 Отношение эквивалентности
- 1.12.4 Отношение порядка
- 1.13 Конечные и бесконечные множества
- 1.13.1 Счётные и несчётные множества
- 1.13.2 Свойства счетных множеств
- 1. Всякое подмножество счетного множества конечно или счетно.
- 2. Объединение любого конечного или счетного множества счетных множеств есть снова счетное множество.
- 3. Всякое бесконечное множество содержит счетное подмножество.
- 1.13.3 Эквивалентность множеств
- 1.13.4 Теорема г. Кантора
- 1.13.5 Теорема Кантора – Бернштейна
- 1.13.6 Верхняя и нижняя границы множества
- 1.13.7 Теорема о верхних и нижних границах подмножества
- 1.13.8 Понятие мощности множества
- 2. Основные положения теории графов
- 2.1 Определение графа
- 2.2 Матричные представления графа
- 2.3. Достижимость
- 2.4. Неориентированные графы
- 2.5. Изоморфизм графов
- 2.6. Отношение порядка и отношение эквивалентности на графе
- 2.7. Характеристики графов
- 2.8 Операции над графами
- 2.9. Определение путей экстремальной длины
- 2.9.1. Задача о кратчайшем пути между двумя вершинами (ориентированного графа
- 2.9.2 Задача о нахождении пути максимальной длины между двумя фиксированными вершинами ориентированного графа
- Номера работ обозначены числами в кружке.
- Литература