Обыкновенным графом (сетью) G=(V,E) называется упорядоченная пара множеств (см. рис. 4.1): конечного непустого множества V, элементы которого называются вершинами графа G, и произвольного подмножества E Í <V V>, элементы которого называются ребрами этого графа (сети).
Основные свойства обыкновенного графа:
1) множество ребер конечно;
2) ребра графа неориентированы;
3) в графе отсутствуют петли, т.е. ребра вида l = (v1,v1);
4) в графе G отсутствуют кратные ребра, (т.е. (v1, v2) = (u1, u2), если v1=u1 и v2=u2, или v1=u2 и v2=u1).
Два крайних случая обыкновенных n -вершинных графов:
1) безреберный граф On; E =Æ;
2) полный граф Kn; E=<V V>, т.е. любые две его вершины смежные.