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

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

(см. скан)

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

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

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

Если — ребро, а вершины такие, что говорят, что ребро инцидентно каждой из вершин и обратно. Все остальные вершины рассматриваются как не инцидентные ребру Вершины, инцидентные ребру, называются его граничными точками. Иногда говорят, что они соединяются ребром

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

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

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

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

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