Основные определения

ГРАФЫ

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

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

Замечание. Необходимо отличать изображение графа на плоскости от его схематического представления (в последнем случае допускается пересечение линий соответствующим ребрам).

На рис.1 приведен пример изображения одного и того же графа на плоскости различными способами.

Рис. 1. Изображение графа на плоскости.

Ребро (v, v) соединяющее вершину v с собой называется петлей.

Если ребра представлены в виде упорядоченных пар (v, w) узлов, то граф называется ориентированным (рис.2); v называется началом, а w — концом ребра (v, w). Если ребра — неупорядоченные пары (множества) различных вершин, также обозначаемые (v, w), то граф называют неориентированным (рис.3).

Смешанный граф G — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными (рис 4). Ориентированный и неориентированный графы являются как бы частными случаями смешанного.

Рис.2. Ориентированный граф. Рис.3. Неориентированный граф Рис.4. Смешанный граф

Граф G=(V, Е) называется простым, если каждая пара вершин (v, w) может соединяться только одним ребром.

Если в ориентированном графе G=(V, Е) пара (v, w) принадлежит множеству ребер Е, то вершина w называется смежной с вершиной v. Говорят, что ребро (v, w) идет из v в w.

Ребро (v, w) и вершина v называются инцидентными друг другу, если вершина v является одним из концов ребра (v, w).

Если (v, w) — ребро неориентированного графа G=(V, Е), то мы считаем, что (v, w)= (w, v), так что (w, v)— то же самое ребро. Вершина w в неориентированном графе называется смежной с вершиной v, если (v, w), а значит, и (w, v)принадлежит Е.

Число ребер инцидентных вершине называются ее степенью, и обозначается S(v). Например на рис.3 степень вершины 3 равна 2, то есть S(3) =2.

Граф называется полным, если для любых двух вершин v, w из множества V, существует ребро (v, w) из множества E (рис.4).

Рис.5. Изображение полного графа на плоскости.
Число ребер в полном графе =n+(n²-n)/2.

Почти полным графом называется полный граф за вычетом петель. Число ребер в почти полном графе =(n²-n)/2.

Дата добавления: 2014-01-20