Элементы теории графов. Графом называется совокупность двух множеств V и X, между элементами которых установлено отношение инцидентности

Графом называется совокупность двух множеств V и X, между элементами которых установлено отношение инцидентности.

Элементы множества Х называются ребрами; V – вершинами. Каждому элементу из множества Х соответствует пара элементов из множества V.

Отношение инцидентности – это соответствие между элементами множества Х и некоторыми парами элементов множества V.

Обозначаем графы G(V,X).

Например граф с ребрами: имеет вид:

V₂

х₁

V₁

х₂

V₃

Если , то граф называется неориентированным, то есть порядок вершин не имеет значения.

Если , то граф называется ориентированным вершина - начало, - конец ребра .

Если множество х содержит элемент = , то такое ребро называется петлей.

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

Если каждой паре вершин соответствует не более одного ребра, то граф называется простой.

Если множество Х пустое, то граф называется нульграфом.

Множество вершин не может является пустым.

Если каждая пара вершин связана ребром, то граф называется полным и обозначается G_n.

Для каждого графа G существует граф который называется дополнением к G до G_n.

Графы G и состоит из одних и тех же вершин, но множества Х графа G и Х графа в пересечении дают пустое множество, т.е. Æ.

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

Кроме чертежа, граф можно задавать как бинарное отношение определенное на множестве элементов v.