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

Говоря нестрого, граф— это множество точек (вершин) и соединяющих их криволинейных отрезков (ребер). Типичный пример графа — схема каких-либо транспортных путей, например, автомобильных дорог. Пункты назначения — это вершины графа, а соединяющие их дороги — ребра. Возникают задачи поиска пути в графе, обладающего тем или иным свойством. Например, можно требовать, чтобы каждое ребро проходилось не более одного раза; можно — чтобы каждая вершина. Можно каждому ребру сопоставить положительное число (длина дороги), и заниматься поисками кратчайшего пути от одного пункта до другого.

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

Рис. 1 Рис. 2

На рис.1 изображен неориентированный граф, вершины которого обозначены римскими цифрами, а ребра — арабскими. Ребра 3 и 4 являются кратными — они соединяют вершины II и III. Ребро 5 является петлей. Вершина IX — изолированная. Заметим, что ребра 2 и 1, 9 и 8 пересекаются на рисунке, но точки их пересечения не являются вершинами графа. (Вопрос о том, можно ли изобразить на плоскости граф так, чтобы его различные ребра не пересекались, будет рассмотрен в § 14). На рисунке 2 изображен ориентированный граф. Он также имеет кратные ребра (1 и 2), петлю (3), изолированную вершину (VI).

Дадим теперь точные определения.

Графом называется пара (V, Е), где V — множество вершин, Е — множество ребер. Мы будем рассматривать только конечные графы, то есть множества V и Е будем считать конечными. Если ребро е соединяет вершины v₁ и v₂, то будем говорить, что е инцидентно вершинам v₁ и v₂, и наоборот, что каждая из вершин v₁, v₂ инцидентна ребру е. Иногда ребро е, соединяющее вершины v₁ и v₂, удобно обозначать парой (v₁, v₂), причем, если граф ориентирован, то пара (v₁, v₂) считается упорядоченной, вершина v₁ называется началом ребра, а v₂ — концом. Если же граф не ориентирован, то порядок элементов в паре (v₁, v₂), обозначающей ребро, не существенен.

Граф H называется частью графа G, если множество вершин H содержится во множестве вершин G, а множество ребер H — во множестве ребер G. Если при этом множество вершин H совпадет с множеством вершин G, то H называется суграфом или остовом графа G. Если H содержит все ребра графа G, соединяющие вершины, принадлежащие множеству вершин H, то H называется подграфом графа G.