Теоретико-множественное определение графа

Введение

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

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

Теоретико-множественное определение графа

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

Пусть задано непустое множество . Обозначим через множество всех пар (упорядоченных или неупорядоченных) его различных элементов.

Графом называется пара , где . Элементы из называются вершинами графа, а элементы из – его ребрами. Если – множество упорядоченных пар, то граф называется ориентированным (орграфом) (рис. 1, а), в противном случае – неориентированным (рис. 1, б). Элементы множества , то есть пары вершин, для неориентированного графа, называются ребрами, а для ориентированного – дугами. В случае когда в орграфе необходимо пренебречь направленностью дуг, то неориентированный граф, соответствующий , обозначается как и называется неориентированным дупликатом (или неориентированным двойником).

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

Граф, не имеющий ребер (), называется пустым или нуль-графом. Все вершины пустого графа изолированные. Граф, в котором каждая пара вершин соединена ребром, называется полным. Полный -вершинный неориентированный граф обозначается ; для каждой его вершины имеем (рис. 2). Для полного графа , а число ребер равно .

Граф с кратными ребрами называют мультиграфом. Если в мультиграфе имеются петли, то он называется псевдографом. Граф без петель и кратных ребер называется простым графом. В большинстве приложений теории графов можно отбрасывать петли и заменять кратные ребра одним ребром.

Важнейшими количественными характеристиками графа являются: число вершин , определяющее порядок графа, и число ребер . Граф с вершинами и ребрами называется -графом.

Часто описание орграфа состоит в задании множества вершин и соответствия , которое показывает как между собой связаны вершины. Соответствие называется отображением множества в , а граф в этом случае обозначается парой .

Для графа на рис. 1, а имеем , т. е. вершины и являются конечными вершинами дуг, у которых начальной вершиной является ; ; ; ; .

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

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

Очевидно, что для неориентированного графа .

Когда отображение действует на множество вершин , то под понимают объединение . Для графа на рис. 1, а , .

Отображение записывается как . Аналогично «тройное» отображение записывается как и т. д. Для графа на рис.1, а имеем:

,

и т. д. Аналогично понимаются обозначения , и т. д.