Общие понятия

Граф G задается множеством вершин (точек) Х = {х₁, ..., х_n} и множеством ребер (линий) А = {а₁, .., а_n}, соединяющих между собой все или часть этих вершин. Таким образом, граф G полностью определяется заданием двух множеств (Х, А).

Другое часто употребляемое описание графа состоит в задании множества вершин X и соответствия (отношения) G, которое показывает, как ме­жду собой связаны вершины. То есть граф задается следующим об­разом.

Пусть дано множество элементов X (вершин) графа и закон G, позволяющий установить соответст­вие между каждым элементом х множества X и некоторыми его подмножествами G(x). Тогда граф полностью определяется множест­вом X и соответствием G, то есть граф обозначается парой (X,G). Удобно исполь­зовать обозначение G(X) по аналогии с функцией.

Пример. Для графа, изображенного на рис. 3.1: множество вершин X = {х₀,х₁,х₂,х₃,х₄,х₅} и закон соот­ветствия между вершинами:

G(x ₀) = {x₁, x₂},

G(x₁) = {x₀, x₂, x₄},

G(x₂) = {x₀, x₁, x₅},

G(x₃) = {x₄},

G(x₄) = {x₁, х₃},

G(x₅) = {x₂},

G(x₆) = Æ.

Рис. 3.1. Пример задания графа

Ребра графа – линии, соединяющие вершины, указывают на соответствие между вершинами в графе.

Запись g = (x_i, x_j) говорит, что ребро g инцидентно вершинам х_i и x_j, а вершины х_i, x_j инцидентны ребру g. Две вершины х_i, x_j назы­ваются смежными, если они определяют ребро графа. Два ребра графа называются смежными, если их концы имеют общую верши­ну.

Вершина, не инцидентная никакому ребру графа, называется изолированной. Если граф состоит из изолированных вершин, его называют ноль-графом.