2.13. Графы

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

Рис. 2.29. Пример графа.

Это множество обозначается следующим образом: Отношение задается множеством пар вершин, которые оно связывает. Например:

Если отношение симметрично (что предполагается для графа, представленного на рис. 2.29), пары вершин из не ориентированы и называются ребрами. В противном случае

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

Определения

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

Путем от вершины а к вершине на графе называют конечную последовательность вершин графа такую, что принадлежит Если является неориентированным графом, достаточно, чтобы в приведенном выше определении либо пара либо пара принадлежала тогда говорят о цепи от а к

Контуром (циклом) называют путь, который заканчивается на своей начальной вершине

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

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

В гл. 4, 5 и 8 рассмотрены многочисленные примеры полезности использования графов и их больших возможностей при моделировании.