double arrow

Общие понятия. Граф G задается множеством вершин (точек) Х = {х1, , хn} и множеством ребер (линий) А = {а1, .., аn}


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

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

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

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

G(x 0) = {x1, x2},

G(x1) = {x0, x2, x4},

G(x2) = {x0, x1, x5},

G(x3) = {x4},

G(x4) = {x1, х3},

G(x5) = {x2},

G(x6) = Æ.

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

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

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

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


Сейчас читают про: