2.13. Графы
Обобщение символического представления выражений в виде деревьев приводит к понятию графа. Граф 
есть множество объектов х (называемых вершинами), на котором задано бинарное отношение.
Рис. 2.29. Пример графа.
Это множество обозначается следующим образом: 
Отношение 
задается множеством пар вершин, которые оно связывает. Например:
Если отношение 
симметрично (что предполагается для графа, представленного на рис. 2.29), пары вершин из 
не ориентированы и называются ребрами. В противном случае
порядок расположения вершин и и 
в паре 
изъявляется существенным, и такие пары вершин называются дугами. Наиболее естественной интерпретацией графа представляется схема связей между точками, например телефонная или дорожная сеть (в общем случае являются неориентированными), или электрические сети (являются ориентированными в случае использования постоянного тока).
Определения
Граф 
называется частичным (или партитивным) графом графа 
если и только если 
Он является подграфом, если и только если 
с X и если 
причем 
где 
или 
. В этом случае из 
удалено некоторое множество вершин вместе со всеми инцидентными им дугами. Если 
принадлежит 
то х называется начальной вершиной и, а у — конечной вершиной и и соответственно х есть вершина, предшествующая вершине у, а у — вершина следующая за х. Степенью вершины называют число соседних с ней вершин, т. е. число вершин, которые являются предшествующими и последующими по отношению к рассматриваемой вершине.
Путем от вершины а к вершине 
на графе 
называют конечную последовательность вершин графа 
такую, что 
принадлежит 
Если 
является неориентированным графом, достаточно, чтобы в приведенном выше определении либо пара 
либо пара 
принадлежала 
тогда говорят о цепи от а к 
Контуром (циклом) называют путь, который заканчивается на своей начальной вершине 
Если для каждой пары вершин 
из 
существует цепь от а к 
то граф 
называют связным (или сильно связным, если существует путь).
Использование графов позволяет представлять многочисленные различные ситуации (в том числе, уже упоминавшиеся выше различные сети). С их помощью можно моделировать основные формы связи и подобные им отношения, материальные или информационные потоки, химические формулы, символьные выражения в общем случае, так как деревья являются частным случаем графов (графики функций в математическом анализе также являются частным случаем, поскольку они являются графическими изображениями множеств точек 
В гл. 4, 5 и 8 рассмотрены многочисленные примеры полезности использования графов и их больших возможностей при моделировании.
