Граф

Graph

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

Граф - неформально - схема, состоящая из точек и соединяющих эти точки отрезков прямых или кривых.

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

Дерево

Tree

Дерево - граф с одной вершиной (корневой вершиной), в которую нет входящих ребер, а в каждую другую вершину входит только одно ребро.

Дуга

Дуга - в теории графов - ориентированное ребро графа. На рисунках направление перехода по дуге, обозначается стрелкой.

Лист

Leaf

Лист - в теории графов - вершина в корневом ориентированном дереве без исходящих из нее ребер.

Маршрут

Маршрут - в теории графов - путь между вершинами графа, проходящий вдоль ребер.

Ориентированный граф

Ориентированный граф - граф, вершины которого соединены направленными ребрами (дугами).

Петля

Петля - в теории графов - ребро, начинающееся и кончающееся в одной и той же вершине.

Связный граф

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

Сеть

Сеть - в теории графов - связный ориентированный граф.

Соседние вершины

Смежные вершины

Соседние вершины - в теории графов - вершины графа, соединенные ребром.

Теория графов

Теория графов - область дискретной математики, объектом изучения которой являются графы.