Графы

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

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

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

Связанные определения

Основные определения, необходимы для использования описания онтологий в виде графов:

• вершины и рёбра графа называются также элементами графа, число вершин в графе |V| — порядком, число рёбер |E| — размером граф;
• вершины u и v называются концевыми вершинами (или просто концами) ребра e={u,v};
• две концевые вершины одного и того же ребра называются соседними;
• два ребра называются смежными, если они имеют общую концевую вершину;
• два ребра называются кратными, если множества их концевых вершин совпадают;
• ребро называется петлёй, если его концы совпадают, то есть e={v,v};
• граф без петель и кратных рёбер называется простым;
• степенью deg V вершины V называют количество инцидентных ей рёбер (при этом петли считают дважды);
• вершина называется изолированной, если она не является концом ни для одного ребра, висячей (или листом), если она является концом ровно одного ребра.

Ориентированный граф

Ориентированный граф (орграф) — (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках и просто рёбрами. Формально, орграф D=(V,E) состоит из множества V, элементы которого называются вершинами, и множества E упорядоченных пар вершин u,v. Дуга (u,v) инцидентна вершинам u и v. При этом говорят, что u — начальная вершина дуги, а v — конечная вершина.

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

Взвешенный граф

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