Примером неориентированного графа является карта дорог.
Глава 6. графы
Во многих прикладных задачах изучаются системы связей между различными объектами. Объекты называются вершинами и отмечаются точками, а связи между вершинами называются дугами и отмечаются стрелками между соответствующими точками. Такие системы образуют граф. Граф может изображать сеть улиц в городе: вершины графа – перекрестки, а дуги – улицы с разрешенным направлением движения (электрические цепи, географические карты, таможенные пункты и пр.). Использование математического аппарата теории графов позволяет, например, найти кратчайший объездной путь или спланировать оптимальный маршрут.
Теория графов родилась в Санкт-Петербурге, ее отцом является Леонард Эйлер, опубликовавший в 1736 году решение задачи о кенигсбергских мостах. Следующие шаги в развитии теории графов были сделаны Г. Кирхгофом, применившим ее в 1847 году к теории электрических цепей, и А. Кэли, разработавшим в 1857 году теорию деревьев. Сам термин «граф» ровно на 200 лет моложе. Он введен в употребление в 1936 году венгерским математиком Д. Кенигом.
Теория графов достаточно быстро развивается, поскольку задачи на графах удобно переводить на языки программирования, то есть решать с использованием современной вычислительной техники.
Основные определения теории графов
Рассмотрим непустое конечное множество точек V={v1, v2,…, vn} и конечное множество линий P={p1, p2, …, pk}, соединяющих некоторые пары точек из множества V.
Определение. Элементы множества V назовём вершинами (узлами), то есть viÎV, i=1,2,…, n – вершины.
Определение. Элементы множества P назовём рёбрами, если линии piÎP неориентированы, то есть направление линий не выделяется.
Определение. Элементы множества P назовём дугами, если линии piÎ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 содержит только рёбра, назовём неориентированным. В этом случае обозначим pi через ei и множество линий P через E, то есть E={e1, e2, …, ek} – множество ребёр, и тогда G=(V,E) – обозначение для неориентированного графа.
Примером неориентированного графа является карта дорог.
Определение. Граф G=(V,P), у которого множество линий P содержит только дуги, назовём ориентированным (орграф). В этом случае обозначим pi через xi и множество линий P через X, то есть X={x1, x2, …, xk} – множество дуг, и тогда 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.