 |
Глава 1. Граф. Общее представление
|
|
|
|
В математической теории графов и информатике граф — это совокупность объектов со связями между ними.
Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра. Для разных областей применения виды графов могут различаться направленностью, ограничениями на количество связей и дополнительными данными о вершинах или рёбрах.
Многие структуры, представляющие практический интерес в математике и информатике, могут быть представлены графами.
Неориентированный граф с шестью вершинами и семью рёбрами
Граф или неориентированный граф G — это упорядоченная пара G: = (V,E), для которой выполнены следующие условия:
V это множество вершин или узлов, E это множество пар (в случае неориентированного графа — неупорядоченных) вершин, называемых рёбрами. V (а значит и E) обычно считаются конечными множествами. Многие хорошие результаты, полученные для конечных графов, неверны (или каким-либо образом отличаются) для бесконечных графов. Это происходит потому, что ряд соображений становятся ложными в случае бесконечных множеств.
Вершины и рёбра графа называются также элементами графа, число вершин в графе | V | — порядком, число рёбер | E | — размером графа.
Вершины u и v называются концевыми вершинами (или просто концами) ребра e = {u,v}. Ребро, в свою очередь, соединяет эти вершины. Две концевые вершины одного и того же ребра называются соседними.
Два ребра называются смежными, если они имеют общую концевую вершину.
Два ребра называются кратными, если множества их концевых вершин совпадают.
Ребро называется петлёй, если его концы совпадают, то есть e = {v,v}.
Степенью degV вершины V называют количество рёбер, для которых она является концевой (при этом петли считают дважды).
|
|
|
Вершина называется изолированной, если она не является концом ни для одного ребра; висячей (или листом), если она является концом ровно одного ребра.
Ориентированный граф (сокращённо орграф) G — это упорядоченная пара G: = (V,A), для которой выполнены следующие условия:
V это множество вершин или узлов,
A это множество (упорядоченных) пар различных вершин, называемых дугами или ориентированными рёбрами.
Дуга — это упорядоченная пара вершин (v, w), где вершину v называют началом, а w — концом дуги. Можно сказать, что дуга v w ведёт от вершины v к вершине w.
Формально, орграф D=(V, E) есть множество E упорядоченных пар вершин 
.
Дуга {u, v} инцидентна вершинам u и v. При этом говорят, что u — начальная вершина дуги, а v — конечная вершина.
Орграф, полученный из простого графа (Простой граф — граф, в котором нет кратных рёбер и петель.) ориентацией ребер называется направленным. В отличие от последнего, в произвольном простом орграфе две вершины могут соединяться двумя разнонаправленными дугами.
Направленный полный граф называется турниром. Полный граф — простой граф, в котором каждая пара различных вершин смежна. Полный граф с n вершинами имеет n(n − 1) / 2 рёбер и обозначается Kn. Является регулярным графом степени n − 1.
Связность
Маршрутом в орграфе называют чередующуюся последовательность вершин и дуг, вида v0{v0,v1}v1{v1,v2}v2…vn (вершины могут повторяться). Длина маршрута — количество дуг в нем.
Путь есть маршрут в орграфе без повторяющихся дуг, простой путь — без повторяющихся вершин. Если существует путь из одной вершины в другую, то вторая вершина достижима из первой.
Контур есть замкнутый путь.
Для полумаршрута снимается ограничение на направление дуг, аналогично определяются полупуть и полуконтур.
Орграф сильно связный, или просто сильный если все его вершины взаимно достижимы; односторонне связный, или просто односторонний если для любых двух вершин, по крайней мере одна достижима из другой; слабо связный, или просто слабый, если при игнорировании направления дуг получается связный (мульти)граф;
|
|
|
Максимальный сильный подграф (Подграф исходного графа — граф, содержащий некое подмножество вершин данного графа и все рёбра, инцидентные данному подмножеству. (ср. Суграф-частичный граф исходного графа — граф, содержащий все вершины исходного графа и подмножество его рёбер)) называется сильной компонентой; (Орграф называется сильно связным (strongly connected), если любые две его вершины сильно связаны. Две вершины s и t любого графа сильно связаны, если существует ориентированный путь из s в t и ориентированный путь из t в s. Сильно связными компонентами орграфа называются его максимально сильно связные подграфы). Односторонняя компонента и слабая компонента определяются аналогично.
Конденсацией орграфа D называют орграф D*, вершинами которого служат сильные компоненты D, а дуга в D* показывает наличие хотя бы одной дуги между вершинами, входящими в соответствующие компоненты.
|
|
|
