Подграф, маршрут, цепь, цикл

Граф называется подграфом графа , если . Подграф, не совпадающий с графом G и не являющийся пустым, называется собственным подграфом графа G. Подграф, содержащий все вершины графа, называется остовным. Маршрутом (путём) длины называется последовательноcть вершин и рёбер где ребро соединяет вершины и , , – начало пути, – конец. Если , то маршрут называется замкнутым. Если , то маршрут называется открытым. Открытый маршрут, в котором все вершины различны, называется цепью. Маршрут, в котором все рёбра различны, называется простым. Замкнутый (простой) маршрут называется циклом (простой цикл или элементарный). Если существует маршрут, соединяющий две вершины, то из рёбер этого маршрута можно построить цепь (для этого следует выбрать маршрут минимальной длины из рёбер данного). Длина кратчайшей цепи, соединяющей вершины a и b,называется расстоянием между этими вершинами . Если рёбра a и b не соединены цепью, то .

Свойства расстояния:

(1)

(2) ;

(3) .

Пусть S – некоторое непустое множество вершин V графа , а – совокупность рёбер графа, обе вершины которых . Подграф графа G называется подграфом, порождённым S.