Основные понятия и определения теории графов

Введение

Теория графов.

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

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

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

Настоящая глава посвящена первоначальному знакомству с некоторыми направлениями в теории графов.

Прежде чем приступить к точным определениям, поясним их наглядно. Любое конечное множество точек (вершин), некоторые из которых соединены попарно стрелками (в теории графов эти стрелки называются дугами), можно рассматривать как граф (рис. 1). Например, граф может изображать сеть улиц в городе, вершины графа — перекрестки, стрелками обозначены улицы с разрешенным направлением движения. (Улицы могут быть с односторонним и двусторонним движением.) Отметим здесь два момента. Во-первых, не любой граф можно изобразить на плоскости так, чтобы дуги пересекались только в вершинах (рис. 2). Во-вторых, две вершины могут быть соединены несколькими дугами, идущими в одном направлении (например, таким свойством может обладать схема железных дорог). Такие дуги будем называть кратными, а граф, содержащий кратные дуги, часто называют мультиграфом (рис. 3). Если подчеркивается, что в данном графе нет кратных дуг, то он называется графом без кратных дуг.

Рис. 2

Рис. 1

Определение 1:Мультиграфом или просто графом называется пара объектов: , где - конечное множество вершин, а - конечное подмножество прямого произведения . При этом называется множеством вершин, а - множеством дуг графа . Число указывает на количество дуг (кратность).

Рис. 3

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

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

. (*)

Отметим, что при нумерации дуг не требуется, чтобы были использованы все номера, начиная с единицы и до числа дуг между данными вершинами. Например, граф на рис. 1 может быть описан так:

. (**)

Графы, заданные соотношениями (*) и (**), будем считать различными. Для формализации «идентичности» этих графов вводится ниже понятие изоморфизма.

Как уже сказано в определении 1, элементы множества называются дугами.

Определение 2: Дуга вида называется петлей.

На рис. 3 присутствует петля . Несколько сложнее понятие ребра. Иногда на графе в какой-либо прикладной задаче нет необходимости задавать направление связи между вершинами и . При изображении в этом случае связь рисуют без стрелки и говорят о ребре, соединяющем и (рис. 4, а). Будем считать такие ребра объединением дуг и с одинаковыми номерами.

Определение 3:Ребром называется подмножество вида .

Иллюстрацией может служить рис. 4, б. Видно, что если на графе две вершины связываются дугами с противоположными направлениями, то эти две дуги могут быть заменены одним ребром.

Определение 3: Граф называется симметрическим, если для любых номеров из того, что дуга следует, что дуга .

Рис. 4

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

В дальнейшем, допуская вольность речи в случаях, где это не может привести к разночтениям. Вместо слов «ребро » будем говорить «ребро ».

Определение 4: Полностью неориентированным графом называется пара объектов , где - конечное множество вершин, а - конечное подмножество прямого произведения , состоящее из элементов вида , где содержит ровно два элемента.

У полностью неориентированных графов все дуги – есть ребра (нет направляющих стрелок ни на одной дуге).

Дадим формальное определение графа без кратных дуг.

Определение 5:Графом без кратных дуг называется граф , удовлетворяющий условию: для любых существует самое большее один элемент такой, что .

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

Определение 5*: Графом без кратных дуг называется пара объектов , где - конечное множество, а .

Покажем, что граф без кратных дуг определяет некоторое отображение (которое также будем обозначать буквой ) . Каждому элементу сопоставим подмножество следующим образом. Считаем, что тогда и только тогда, когда . Верно и обратное: любое отображение определяет граф. Можно дать ещё одно эквивалентное определение.

Определение 5**: Графом без кратных дуг называется пара объектов , где — конечное множество, а — отображение.

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

Определение 6: Дугу и вершину назовем инцидентными, если или (вершина является либо первой, либо второй проекцией дуги ). Ребро и вершину назовем инцидентными, если инцидентны дуга и . Дугу , такую, что , назовем исходящей из , а если , то входящей в . Две вершины и называются смежными, если существует дуга, соединяющая либо с , либо с .

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

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

Пусть теперь - симметрический граф.

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

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

Определение 9: Граф называется суграфом графа , если . Граф называется подграфом графа , если . Наконец, граф называется частью графа , если .

Таким образом, суграф получается из графа удалением некоторого числа дуг (с сохранением вершин). Подграф получается из графа удалением некоторого числа вершин вместе со всеми дугами, инцидентными удаленной вершине. Часть графа получается из графа применением конечного числа обеих описанных операций.

Определение 10: Наименьший симметрический граф такой, что является суграфом , называется симметризованным графом графа .

Определение 11: Граф называется сильно связным, если для любых двух вершин ,существует путь такой, что .

Определение 12: Симметрический граф называется связным, если он сильно связен. Произвольный граф называется связным, если связен его симметризованный граф .

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

Определение 13: Подграф графа называется компонентой связности графа , если а) связен, б) обладает свойством максимальности, т. е. если - некоторый другой связный подграф и , то графы и совпадают.

Определение 14: Будем говорить, что ребро является перешейком в симметрическом графе , если при удалении этого ребра количество компонент связности графа увеличивается на единицу.

Очевидно, что ребро является перешейком тогда и только тогда, когда не существует простого цикла, содержащего это ребро.

Определение 15: Полустепенью исхода вершины называется число исходящих из нее дуг. Полустепенью захода вершины называется число входящих в нее дуг. Степенью вершины называется число .

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

Определение 16: Ребро симметрического графа называется тупиком, если степень одной из его вершин равна единице (здесь степень вершины определяется как число инцидентных ей ребер).

Определение 17: Пусть — граф, . Матрицей смежности называется матрица , в которой элемент равен количеству дуг из вида .

Определение 18: Графы и называются изоморфными, если существуют взаимно однозначные отображения , такие, что .

Пример. Графы и , изображенные на рис. 5, изоморфны; их изоморфизм определяется подстановкой второго порядка:

.

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

Дата добавления: 2014-01-03