Примером неориентированного графа является карта дорог.

Глава 6. графы

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

Теория графов родилась в Санкт-Петербурге, ее отцом является Леонард Эйлер, опубликовавший в 1736 году решение задачи о кенигсбергских мостах. Следующие шаги в развитии теории графов были сделаны Г. Кирхгофом, применившим ее в 1847 году к теории электрических цепей, и А. Кэли, разработавшим в 1857 году теорию деревьев. Сам термин «граф» ровно на 200 лет моложе. Он введен в употребление в 1936 году венгерским математиком Д. Кенигом.

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

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

Рассмотрим непустое конечное множество точек V ={ v ₁, v ₂,…, v_n } и конечное множество линий P ={ p ₁, p ₂, …, p_k }, соединяющих некоторые пары точек из множества V.

Определение. Элементы множества V назовём вершинами (узлами), то есть v_i Î V, i =1,2,…, n – вершины.

Определение. Элементы множества P назовём рёбрами, если линии p_i Î P неориентированы, то есть направление линий не выделяется.

Определение. Элементы множества P назовём дугами, если линии p_i Î P снабжены стрелками, то есть направление линий принципиально.

Рёбра и дуги иногда обозначают так. Если v, w Î V, то { v, w } – ребро, а (v, w) – дуга, соединяющая вершины v и w из P. При этом если e ={ v, w }Î P - ребро, то v и w − концы ребра, а если x =(v, w)Î P - дуга, то v − начало, w – конецдуги.

Определение. Граф G – это совокупность двух конечных множеств V и P. Обычно граф обозначают как G= (V, P).

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

Определение. Если множество P =Æ, то такой граф G= (V, P) называется пустым.

Определение. Граф G= (V, P), у которого множество линий P содержит только рёбра, назовём неориентированным. В этом случае обозначим p_i через e_i и множество линий P через E, то есть E ={ e ₁, e ₂, …, e_k } – множество ребёр, и тогда G= (V, E) – обозначение для неориентированного графа.

Примером неориентированного графа является карта дорог.

Определение. Граф G= (V, P), у которого множество линий P содержит только дуги, назовём ориентированным (орграф). В этом случае обозначим p_i через x_i и множество линий P через X, то есть X ={ x ₁, x ₂, …, x_k } – множество дуг, и тогда D= (V, X) – обозначение для орграфа.

Определение. Граф G= (V, P), у которого множество линий P состоит и из ребёр, и из дуг называется смешанным.

Определение. Если множеству P принадлежат пары вершин, для которых v = w, то такие ребра { v, v } (дуги (v, v)) называют петлями.

Определение. Пара вершин v, w Î V может быть соединена двумя или более ребрами (или дугами одного направления). Такие рёбра (или дуги) называются кратными.

Определение. Граф G= (V, P), в котором есть петли и (или) кратные рёбра (дуги), называется псевдографом.

Определение. Псевдограф G= (V, P) без петель называется мультиграфом.

Определение. Простой граф -это граф, не содержащий петель и кратных рёбер (дуг).

Определение. Вершина v Î V и ребро е Î Е неориентированного графа G= (V, E) (дуга x Î X орграфа D= (V, X)) называются инцидентными, если вершина v является концом ребра е (началом или концом дуги х).

Определение. Степенью (порядком) вершины называется число сходящихся в ней ребер.

Конечнымграфом называется граф с конечным числом ребер.

Заметим, что степень вершины можно подсчитать по числу концов рёбер, входящих в эту вершину или выходящих из неё. Поскольку петля и входит в вершину, и выходит из неё, её вклад в степень вершины равен 2.