СПРАВКА

Граф

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

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

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

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

Каждому ребру в соответствие можно поставить число, которое принято называть весом. Если это число действительное, его вполне можно интерпретировать, как «длину» ребра. Правда, гарантировано изобразить граф из N вершин (число N называют порядком графа) с сохранением длин всех M рёбер (число M - размер) можно лишь в пространстве с числом измерением не меньшим, чем K=N/M; K может составлять, к примеру, и (N-1)/2. Для графа с действительными весами можно ввести и понятие минимального остова - остовного дерева, сумма длин всех рёбер которого минимальна.

Задача нахождения минимального остова не обязательно имеет одно решение, однако существуют быстрые и надёжные алгоритмы для нахождения хотя бы одного такого решения.


ВЕРНУТЬСЯ К СТАТЬЕ