Неориентированные графы. 
Геометрическая теория графов

Абстрактное определение графа

Строгое абстрактное определение графа можно дать в терминах теории множеств.

Пусть X — произвольное непустое множество и ХхХ — его декартов квадрат, т. е. множество всех упорядоченных пар (х/, хг) из элементов множества X. Если множество X — конечно и состоит из п элементов, то его декартов квадрат ХхХ содержит п пар, и пары (xj, X2) и (x2, xj) являются различными элементами множества ХхХ при хI&C2- Иногда множество ХхХ называют упорядоченным произведением множества X на себя.

Рассмотрим теперь так называемое неупорядоченное произведение Х&Х множества X на себя, которое определяется как множество всех неупорядоченных пар из элементов множества X. Элементы из Х&Х будем обозначать (xj &Х2). Ясно, что во множестве Х&Х пары (xj &х₂) и (Х2 &xi) не различимы. Если множество X — конечно и состоит из п элементов, то множество Х&Х содержит ^ элементов.

Графом G (V, Е, f) называется совокупность непустого множества V, изолированного от него произвольного множества Е и отображения f: Е V&V множества Е в V&V, которое каждому элементу из Е ставит в соответствие некоторый элемент из V&V. При этом множества V и Е называются соответственно множеством вершин и множеством ребер графа G (V, Е, Д, а отображение / называется отображением инциденции

этого графа. Граф называется конечным, если множества V и Е содержат конечное число элементов.

Рассмотрим пример. Пусть множество V состоит из 7 точек, V-{A, B, C, D, F, H, P}, а множество Е — из 10 линий, E={a, b, c, d, e, fg, h, p, l} (см. рис. 4). Тогда отображение f: Е —> V&V, определяемое по закону.

является отображением инциденции для графа G (V, Е, f). Этот граф имеет 7 вершин и 10 ребер.

В некоторых случаях, если отображение инциденции явно не задано, для графа G (V, Е, f) будем использовать обозначение G (V, Е). В случаях, когда множества вершин и ребер известны из контекста задачи, граф G (V, Е, J) будем обозначать через G. Заметим, что часто вершины и ребра графа объединяются одним общим термином — элементы графа.

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