Понятия смежности, инцидентности, степени
Если x ={ v, w } - ребро, то v и w − концы ребра x.
Если x =(v, w) - дуга ориентированного графа, то v − начало, w – конец дуги.
Вершина v и ребро x неориентированного графа (дуга x ориентированного графа) называются инцидентными, если v является концом ребра x (началом или концом дуги x).
Вершины v, w называются смежными, если { v, w }Î X.
Степенью вершины v графа G называется число d(v) ребер графа G, инцидентных вершине v.
Вершина графа, имеющая степень 0 называется изолированной, а степень 1 – висячей.
Полустепенью исхода (захода) вершины v ориентированного графа D называется число d+(v) (d-(v)) дуг ориентированного графа D, исходящих из v (заходящих в v).
Следует заметить, что в случае ориентированного псевдографа вклад каждой петли инцидентной вершине v равен 1 как в d+(v), так и в d-(v).
Маршруты и пути
Последовательность v 1 x 1 v 2 x 2 v 3… x k v k+1, (где k ³1, v iÎ V, i =1,…, k +1, x iÎ X, j =1,…, k), в которой чередуются вершины и ребра (дуги) и для каждого j =1,…, k ребро (дуга) x j имеет вид { vj, vj +1} (для ориентированного графа (vj, vj +1)), называется маршрутом, соединяющим вершины v 1 и vk +1 (путем из v 1 в vk +1).
Пример
В графе, изображенном на рис.4, v 1 x 1 v 2 x 2 v 3 x 4 v 4 x 3 v 2 – маршрут, v 2 x 2 v 3 x 4 v 4 – подмаршрут;
маршрут можно восстановить и по такой записи x 1 x 2 x 4 x 3;
если кратности ребер (дуг) равны 1, можно записать и так v 1 v 2 v 3 v 4 v 2.
Цепь − незамкнутый маршрут (путь), в котором все ребра (дуги) попарно различны.
Цикл − замкнутая цепь (в неориентированном графе).
Контур − замкнутый путь (в ориентированном графе).
Простой путь (цепь) − путь (цепь, цикл, контур), в котором ни одна дуга/ребро не встречается дважды.
Простой цикл (контур) − цикл (контур), в котором все вершины попарно различны.
Гамильтонова цепь (путь, цикл, контур) − простая цепь (путь, цикл, контур), проходящая через все вершины.
Эйлерова цепь (путь, цикл, контур) − цепь (путь, цикл, контур), содержащая все ребра (дуги) графа по одному разу.
Длина маршрута (пути) − число ребер в маршруте (дуг в пути).
Утверждение 1. Для того чтобы связный псевдограф G обладал Эйлеровым циклом, необходимо и достаточно, чтобы степени всех его вершин были четными.
Утверждение 2. Для того чтобы связный псевдограф G обладал Эйлеровой цепью, необходимо и достаточно, чтобы он имел ровно 2 вершины нечетной степени.
Дата добавления: 2015-09-27 | Просмотры: 487 | Нарушение авторских прав
|