Сводка основных понятий и определений

Содержание занятия

Вступительная часть

Теория графов – тот редкий раздел математики, о котором доподлинно известно, когда он родился, и кто был его основоположником. Родилась теория графов в Санкт-Петербурге. Ее создателем является Л. Эйлер, который в 1736 году опубликовал решение задачи о Кенигсбергских мостах. С тех пор поток задач с применением графов нарастал подобно снежной лавине. Наряду с многочисленными головоломками и играми на графах, рассматривались важные практические проблемы, многие из которых требовали тонких математических методов. Уже в середине XIX века Кирхгоф применил графы для анализа электрических цепей, а Кэли исследовал важный класс графов для выявления и перечисления изомеров насыщенных углеводородов (1857 г.). Однако теория графов как математическая дисциплина сформировалась только в середине 30-х годов XX века, благодаря работам таких математиков как Кенинг Г., Понтрягин Л.С., Зыков А.А., Визинг В.Г. и др.

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

Сводка основных понятий и определений

Определение 1. Граф G - это совокупность двух конечных множеств: множества V, содержащего n точек (вершин графа) и множества W, содержащего линии (дуги, ребра) произвольной формы, связывающие вершины. Граф обозначают как пару множеств: G=(V, W).

Естественно, что множество вершин графа не может быть пустым, т.е.V¹ Æ, в то время как множество дуг может быть пустым.

Графы бывают двух типов – неориентированные и ориентированные. В приложениях чаще используются ориентированные графы.

Определение 2. Ориентированным графом (орграфом) называется тройка G=(V, W, f), где V- множество вершин графа, W – множество дуг, а f - отображение W®V´ V, называемое отображением инцидентности.

Таким образом, в орграфе каждой дуге lÎ w однозначно отвечает упорядоченная пара точек x, yÎ V, в то время как в неориентированном графе порядок точек x и y роли не играет.

Говорят также, что дуга l соединяет точки x и y, а точки x и y называют концевыми вершинами. Дуги, имеющие одинаковые концевые вершины и одинаково направленные, называются параллельными (кратными); противоположно направленные – противоположными. Вершина и дуга называются инцидентными друг другу, если вершина является для этой дуги концевой точкой.

Две вершины, являющиеся концевыми для некоторой дуги, называются смежными. Две дуги, инцидентны одной и той же вершине, называются смежными дугами.

Определение 3. Степенью вершины называется число дуг, инцидентных ей. Вершина степени 1 называется висячей. Вершина степени 0 называется изолированной.

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

Путь для неориентированных графов называют также маршрутом.

Если для данных вершин u и u ’ существует путь p из вершины u в вершину u ’, то говорят, что вершина u ’ достижима из вершины u по пути p.

Ребро, граничными вершинами которого является одна и та же вершина, называется петлей.

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

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

Если множество дуг W=0, то граф называется пустым или нуль-графом. Простой граф, в котором любые две вершины соединены ребром, называется полным. Если множество вершин V простого графа допускает разбиение на два непересекающихся подмножества V_i и V₂ (V₁ V₂=Æ), так что не существует ребер, соединяющих вершины одного и того же подмножества, то он называется двудольным или биграфом:

Определение 5. Маршрут, все ребра которого различны, называется цепью, а маршрут, для которого различны все вершины, называется простой цепью. Замкнутая цепь называется циклом, а простая цепь – простым циклом.

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

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

Граф G¢ = (V¢, W¢) является частью графа G = (V, W), если V¢ Ì V и W¢ Ì W, то есть граф содержит все вершины и ребра любой его части. Часть графа, которая наряду с некоторым подмножеством ребер содержит и все инцидентные им вершины, называется подграфом. Часть, которая наряду с некоторым подмножеством ребер графа содержит все вершины графа (V¢ =V, W¢ Ì W), называется суграфом:

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

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

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

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

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

Специфичным для орграфа является понятие сильной связности. Орграф называется сильно связным, если для любой пары его вершин x _i и x _j существует путь из x _i в x _j и из x _j и x _i.

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

Вопросы для проверки готовности к занятию

1. Когда зародилась теория графов? Кто является ее основоположником? В каких областях человеческой деятельности используется теория графов? В чем суть задачи о Кенигсбергских мостах?

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

3. Дать определение пути (маршрута) в графе.

4. В чем различие понятий простого графа, мультиграфа, псевдографа? Что представляют собой нуль-граф, полный граф, двудольный граф?

5. Что называется цепью (простой цепью), циклом (простым циклом)? Что такое контур графа?

6. Определить понятия части графа, подграфа, суграфа.

7. Дать определение взвешенного (нагруженного) графа.

8. Привести определения матрицы инцидентности графа, матрицы смежности графа.

9. Дать определение списочного представления графа.

10. Какой способ представления графов является наиболее эффективным с точки зрения экономии памяти ЭВМ?

Ответы на указанные вопросы целесообразно иллюстрировать примерами и рисунками