Абстрактные графы

Для облегчения общего определения графа введем понятие неупорядоченного произведения множества S само на себя. Напомним, что упорядоченным или декартовым (прямым) произведением множества само на себя (которое обозначается S ´ S) называется множество всех упорядоченных пар (s, t), где sÎ S и tÎ S. Здесь (s, t) и (t, s) рассматриваются как различные элементы, исключая случай s = t.

Аналогично, символом (s& t) будем обозначать неупорядоченную пару элементов множества S, а множество всех различных неупорядоченных пар будет обозначаться как S & S и называться неупорядоченным произведением множества S само на себя. В данном случае
(s & t) и (t & s) эквивалентны и так же, как при декартовом произведении, допускается совпадение элементов пары, т. е. s = t. Заметим, что если s имеет k элементов, то S ´ S состоит из k² упорядоченных пар, а S & S – из k(k+1)/2 различных неупорядоченных пар.

Абстрактный граф или просто граф можно определить теперь следующим образом.

Граф есть совокупность непустого множества V, изолированного от него множества E (возможно пустого) и отображения F множества E на V & V. Элементы множеств V и E называются вершинами и ребрами графа соответственно, а F называется отношением инцидентности графа.

Если eÎ E - ребро, а vÎ V и wÎV - вершины такие, что F(e)= v&w, говорят, что ребро e инцидентно каждой из вершин v и w и обратно. Все остальные вершины рассматриваются как не инцидентные ребру e. Вершины, инцидентные ребру, называются его граничными точками. Иногда говорят, что они соединяются ребром e.

Хотя отношение инцидентности является фундаментальным в понятии графа, отображение F часто можно не задавать в явном виде. В таких случаях, если v и w - граничные точки ребра e, то это обозначается e~(v& w) и читается «e соединяет вершины v и w».

Будем обозначать граф через G или (V, E, F) или (V, E). Последнее обозначение используем, когда отношение инцидентности определяется неявно. Заметим, что множество E (но не V) может быть пустым. Говорят, что граф вырожденный тогда и только тогда, когда он не имеет ребер. Хотя графы, не имеющие ребер, сами по себе не интересны, их рассмотрение иногда оказывается полезным, например, при работе с процедурами разборки графа, основанными на последовательном удалении ребер.

Если V и E - конечные множества (пустое множество рассматривается как конечное), то G называется конечным графом. В противном случае говорят, что граф не является конечным.

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