Графы. Основные понятия.

Графом G наз. пара мн-в: G=(N,U). Эл. N наз. вершинами, а U – рёбрами. U представляет собой некоторое мн-во неупорядоченых пар вершин.

Есл мн-во N конечно, то граф наз. конечным. Рёбра вида (i,j) и (j,i) наз. паралельными, а рёбра вида (i,i) наз. петлёй. Граф наз. простым, если он не имеет параллельных рёбер и петель (Если имеет параллельные рёбра, то U – мульти мн-во). Вершины, связаные ребром наз. смежными. Если в графе имеется (i,j), то вершины i, j наз. инцедентными этому ребру и наоборот, ребро наз. инцедентным этим вершинам. Два ребра, имеющие общую вершину наз. смежными. Если в графе имеется ребро (i,j), то i, j – концевые вершины ребра (i,j). Число рёбер, инцедентных вершине наз. степенью вершины (deg(i)). Вершиа нулевой степени наз. изолированой, вершина первой степени наз. висячей. Граф, все вершины к-го имеют нулевую степень, наз. пустыми. Граф, любые две вершины к-госмежны наз. полным.

Два графа G и W наз. изоморфными : G W, если  взаимно однозн. соотв. между их вершинами, сохр. cмежность.

Очевидно что ni=1­­­deg(i)=2m, где n – число вершин, m – число рёбер.

Подграфом D графа G (DG) наз. граф, такой, что MN; WU.

Граф D наз. остовным подграфом графа G, если M=N. Пусть G=(N,U) и TN.

Вершинопорждённым подграфом графа G с порождающим мн-вом T: G(T), наз. подграфом графа G с мн-вом рёбер W: G(T)=(T,W) такой, что две вершины G(T) смежны тогда и только тогда, когда они смежны в исходном графе.