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

Пусть V – произвольное множество, V2 – множество всех его двухэлементных подмножеств, т.е. множество неупорядоченных пар {а, b}, где а, b Î V. Пара (V, E), где Е – произвольное подмножество V2, называется графом (неориентированным графом).

В дальнейшем рассматриваются только конечные графы, т.е. множество E предполагается конечным. Число | V(G) | вершин называется его порядком и обозначается через |G|. Если |G| = п, |E(G)| = т, то G называют (п, т)-графом.

Говорят, что две вершины u и v смежны, если множество {u, v} является ребром, и не смежны в противном случае. Если е = {u, v} – ребро, то вершины u и v называют его концами. В этом случае также говорят, что ребро е соединяет вершины u и v. Такое ребро обозначается символом uv .

Два ребра называются смежными, если они имеют общий конец.

Вершина е и ребро v называются инцидентными, если v является концом ребра е, и не инцидентными в противном случае.

Графы удобно изображать в виде рисунков, состоящих из точек и линий, соединяющих некоторые из этих точек. При этом точки соответствуют вершинам графа, а соединяющие пары точек линии – ребрам. В качестве иллюстрации рассмотрим граф G, изображенный на рис. 2.1.

Это (5, 6)-граф, V(G) = {1, 2, 3, 4, 5}, E(G) = {{1, 2}, {1, 5}, {2,3}, {2, 4}, {2, 5}, {4, 5}}. Вершины 1и 2 смежны, а 1 и 3 не смежны. Вершина 1 и ребро {1, 2} инцидентны.

Иногда в графах допускается наличие петель, т.е. ребер {а, а} (рис. 2.2), и кратных ребер, т.е. ребро {а, b} учитывается несколько раз (рис. 2.3). Мы будем рассматривать графы без петель и кратных ребер.

Ориентированный граф – это пара (V, А), где V – множество вершин, А – множество ориентированных ребер (или дуг), т.е. упорядоченных пар (u, v), где u, v Î V. При этом и называется началом дуги, v – концом. На рисунке дуги отмечаются стрелками, указывающими направление от начала к концу (рис. 2.4).