3.4. Части графа

Граф Н = (W, F) называется подграфом графа G = (V, E), если W  V, F  E и обе вершины, инцидентные любому ребру из F, принадлежат W. Подграф Н графа G называется его остовным подграфом, если W = V. Если F является множеством всех ребер графа G, все концы которых содержатся в множестве W, то подграф Н = (W, F) называется подграфом, порожденным множеством W.

Любая последовательность вида v₁, e₁, v₂, e₂, … , e_k, v_k + 1, где v₁, v₂, … , v_k + 1 – вершины некоторого графа, а e₁,  e₂, … , e_k – его ребра, причем e_i = v_iv_i + 1 (i = 1, 2, … , k), называется маршрутом. Маршрут может быть конечным либо бесконечным. Одно и то же ребро может встречаться в маршруте не один раз. Длиной маршрута называется количество входящих в него ребер, причем каждое ребро считается столько раз, сколько оно встречается в данном маршруте.

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

Маршрут v₁, e₁, v₂, e₂, … , e_k, v₁ называется циклическим. Циклическая цепь называется циклом. Простой цикл – это циклическая простая цепь.

Любую цепь и любой цикл графа можно рассматривать как его подграф.

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

Связный граф называется гамильтоновым, если в нем существует цикл, проходящий по каждой вершине ровно один раз (гамильтонов цикл).