Основные понятия и определения теории графов

Обыкновенным графом (сетью)G=(V,E) называется упорядоченная пара множеств (см. рис. 4.1): конечного непустого множества V, элементы которого называютсявершинами графаG, и произвольного подмножества E Í <V V>, элементы которого называютсяребрамиэтого графа (сети).

Основные свойства обыкновенного графа:

1) множество ребер конечно;

2) ребра графа неориентированы;

3) в графе отсутствуют петли, т.е. ребра вида l = (v₁,v₁);

4) в графе G отсутствуют кратные ребра, (т.е. (v₁, v₂) = (u₁, u₂), если v₁=u₁ и v₂=u₂, или v₁=u₂ и v₂=u₁).

Два крайних случая обыкновенных n-вершинных графов:

1) безреберный граф O_n; E=Æ;

2) полный граф K_n; E=<V V>, т.е. любые две его вершины смежные.