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

Пусть G — неориентированный граф.

Маршрутом, или цепью, в G называется такая последовательность (конечная или бесконечная) ребер ах, а2, ..., ап, что каждые соседние два ребра а, и а,+1 имеют общую инцидентную вершину.

Одно и то же ребро может встречаться в маршруте несколько раз. В конечном маршруте (а,, а2,..., а„) имеется первое ребро а{ и последнее ребро ап. Вершина^, инцидентная ребру аь но не инцидентная ребру а2, называется началом маршрута, а вершина хп, инцидентная ребру а„, но не инцидентная ребру ап _ |, называется концом маршрута.

Длиной, или мощностью, маршрута называется число ребер, входящих в маршрут, причем каждое ребро считается столько раз, сколько оно входит в данный маршрут. Замкнутый маршрут называется циклом.

Пример 3.7. В изображенном на рис. 3.25 графе рассмотрим два маршрута из вершины в вершину х4: Граф (пример 3.7)

Рис. 3.25. Граф (пример 3.7)

Длина маршрута равна 3, а длина маршрута М2 равна 4.

Маршрут (цикл), в котором все ребра различны, называется простой цепью (циклом). Маршрут (цикл), в котором все вершины, кроме первой и последней, различны, называется элементарной цепью (циклом).

Пример 3.8. В приведенном на рис. 3.26 графе выделим следующие маршруты:

Граф (пример 3.8)

Рис. 3.26. Граф (пример 3.8)

  • ь а3, а4) — простая элементарная цепь длины 3, так как все ребра и вершины попарно различны;
  • • (а2, аА, «•{) — простой элементарный цикл, так как это замкнутый маршрут, у которого все ребра и вершины, кроме первой и последней, различны;
  • • (а1; а2, «4, « )) — цепь, которая является простой, но не элементарной, так как все ребра различны, но вершина х2 встречается дважды;
  • • (flj, а2, а2) — маршрут длины 3, не являющийся ни простой, ни элементарной цепыо, так как ребро а2 и вершина х2 встречаются дважды.
 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ     След >