Предложение 1 (лемма "о рукопожатиях"). Для любого псевдографа G
Предложение 2. Для любого ориентированного псевдографа G
Определение.Маршрутом (путем), соединяющим вершины v1 и vk+1 (из v1 в vk+1) в графе (орграфе) G =(V, E) называется последовательность вида
v1e1v2e2v3… ekvk+1 (*)
(где k ³1, vi Î V, i =1, …, k +1, ej Î E, j =1, …, k), в которой вершины и ребра (дуги) и для каждого j =1, …, k ребро (дуга) ej имеет вид { vj, vj+1} ((vj, vj+1)). При этом v1 называется начальной, а vk+1 – конечной вершинами указанного маршрута (пути), а остальные вершины – внутренними. Говорят, что (*) – (v1, vk+1)-маршрут (путь).
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав!Последнее добавление