Понятие цепи

Пусть - некоторый граф. Последовательность попарно инцидентных между собой вершин и ребер графа называется цепью.

и - концевые вершины цепи.

Длина цепи - число ребер, образующих цепь ( и - концевые вершины цепи).

Цепь называется составной, если она содержит повторяющиеся ребра. Цепь называется сложной, если она содержит повторяющиеся вершины за исключением, быть может, первой и последней. Цепь, которая не является ни составной, ни сложной называется простой. Цепь называется циклом, если концевые вершины цепи совпадают. Циклы также бывают простые, составные и сложные. - простой цикл, состоящий из ребер. Пусть и - некоторые вершины графа. Тогда расстояние между вершинами . Введенное таким образом понятие расстояния является метрикой на графах:

1) ;
2) ;
3) .

Диаметром графа называется величина .

Пример

(целая часть числа).