Инструменты пользователя

Инструменты сайта


examination:diskretka:question11

Вопрос №11. Маршруты (пути), цепи и циклы в графе

Маршруты, цепи, циклы в неорграфе

Пусть G-неорграф с множеством вершин V и множеством ребер E.

Маршрутом в графе G называется произвольная последовательность вида

…V0e1V1…Vm-1emVm

где для ∀k Vk∈V,ek∈E, причем для ∀k ребро ek инцидентно вершинам Vk-1, Vk.

Замечание:

  1. Многоточие по обе стороны записи означают, что не исключен тот случай, когда указанная последовательность продолжается неограниченно влево или вправо, или в обе стороны.
  2. Маршрут называется конечным, если указанная последовательность конечна, в противном случае называется бесконечным.

Рассмотрим конечные маршруты V0e1V1…Vm-1emVm:

Вершина V0- начало маршрута, а Vm- конец.

Неотрицательное число m - длина маршрута.

О самом маршруте говорят, что он соединяет точку V0 с точкой Vm.

Что касается бесконечных маршрутов, то они, очевидно, разделяются на 3 вида:

  • Маршруты бесконечные вправо (∃V0, но не ∃Vm );
  • Маршруты бесконечные влево (∃Vm, но не ∃V0 );
  • Маршруты бесконечные в обе стороны (не ∃V0 и не ∃Vm ).

У бесконечных маршрутов длина не определена или формально равна бесконечности.

Тривиальны маршрут - это маршрут нулевой длины (т.е. V0=Vm ) .

Определение: Пусть имеется 2 маршрута такие, что 1-ый маршрут вкладывается во 2-ой в виде некоторого отрезка последовательности, тогда говорят, что 1-ый маршрут является участком или фрагментом второго.

Определение: Вершина V некоторого маршрута называется внутренней или промежуточной вершиной, если этот маршрут содержит фрагмент вида e`V e``.

Определение: Маршрут называется цепью, если он не содержит одинаковых ребер.

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

Определение: Если в конечном маршруте начало и конец совпадают, то такой маршрут называется циклическим.

Определение:Циклом в графе называется циклический маршрут являющийся цепью.

Цикл называется простым, если он является простой цепью.

Граф маршрутов фиксированной длины

Пусть G-неорграф с множеством вершин V и множеством ребер E.

Зададим произвольное неотрицательное целое число m. Построим еще один неорграф , который будем называть графом маршрутов длины m в графе G.

В качестве множества вершин графа маршрутов возьмем тоже самое множество V, а ребрами этого графа объявим всевозможные маршруты длины, соединяющие вершины исходного графа. (маршруты рассматриваются с точность до полиндромии).

Теорема Построенный нами граф маршрутов длины m канонически изоморфен графу Gm относительно композиции.

Следствие: матрица смежности графа маршрутов длины m- есть m-ая степень матрицы смежности графа G.

Пути, цепи и циклы в орграфе

Все понятия связанные с путями, цепями и циклами в оргафе определяются аналогично неорграфу.

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

examination/diskretka/question11.txt · Последние изменения: 2014/01/15 12:14 (внешнее изменение)