Граф G задается множеством точек (вершин) X={x1,..xn} и множеством линий (ребер) A={a1,..,a m}, соединяющих между собой все или часть этих точек. Таким образом, граф G полностью задается парой (X,A).
Другое, чаще употребляемое описание графа, состоит в задании множества вершин X и соответствия G, которое показывает, как между собой связаны вершины. То есть граф задается следующим образом.
Пусть дано множество X, состоящее из элементов (назовем их вершинами графа) и закон G, позволяющий установить соответствие между каждым элементом x множества X и некоторыми его подмножествами G(x) тогда граф полностью определяется множеством X и соответствием G, то есть граф обозначается парой (X,G). Удобно использовать обозначение G(x) по аналогии с функцией.
Пример (рис.2.1). Множество вершин X = {x0, x1, x2, x3, x4, x5} и соответствия между вершинами
G(x0) = {x1, x2},
G(x2) = {x0, x1, x5},
G(x3) = {x4},
G(x4) = {x1, x3},
G(x5) = {x2},
G(x6) = Æ.
Ребра графа – линии, соединяющие вершины, указывают на соответствие между вершинами в графе.
Запись g(xi, xj) говорит, что ребро g инцидентно вершинам xi, xj и вершины xi, xj инцидентны ребру g. Две вершины xi, xj называются смежными, если они определяют ребро графа. Два ребра графа называются смежными, если их концы имеют общую вершину.
|
|
Вершина, не инцидентная никакому ребру графа, называется изолированной. Если граф состоит из изолированных вершин, его называют ноль-графом.