Модели знаний на графах
Граф – это система, которая интуитивно может быть рассмотрена как множество кружков и множество соединяющих их линий (геометрический способ задания графа – см. рисунок 1). Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – рёбрами. Граф, в котором направление линий не выделяется (все линии являются ребрами), называется неориентированным; граф, в котором направление линий принципиально (линии являются дугами) называется ориентированным. Язык графов оказывается удобным для описания многих физических, технических, экономических, биологических, социальных и других систем. Вершины в графе могут отличаться друг от друга тем, скольким рёбрам они принадлежат. МАРШРУТЫ, ЦЕПИ, ЦИКЛЫ ________________________________________ Маршрутом в графе называется чередующаяся последовательность вершин и рёбер, в которой любые два соседних элемента инцидентны: v0, e1, v1, e2, v2,...,ek, vk. Путём называется последовательность дуг (в ориентированном графе), такая, что конец одной дуги является началом другой дуги.
Простой путь – путь, в котором ни одна дуга не встречается дважды. Контур – путь, у которого конечная вершина совпадает с начальной вершиной. Длиной пути (контура) называется число дуг пути (или сумма длин его дуг, если последние заданы). Цепь цепь – последовательность смежных вершин.
Замкнутая цепь называется циклом. Можно определить простые и элементарные цепи.