Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Маршруты, цепи и циклы.

Читайте также:
  1. Воспроизводственные циклы. Основные характеристики эк цикла.
  2. ТЕРМИЧЕСКИЕ ЦИКЛЫ.

Пусть G(V,Е) – неориентированный граф. Рассмотрим конечную последовательность рёбер такую, что любые два соседние ребра имеют одну общую инцидентную вершину . Эту последовательность называется маршрутом графа.

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

Определение. Длиной маршрута называется число ребер в нём с учётом повторений.

Определение. Замкнутым называется маршрут, начало и конец которого находятся в одной вершине. Иначе маршрут называется открытым.

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

Определение. Циклом называется замкнутый маршрут с различными ребрами.

Определение. Простыми называются цепь и цикл с различными вершинами.

Пример. В графе, диаграмма которого приведена на рисунке 3 пункта 2:

последовательность является открытым маршрутом длиной 3; последовательность является простой цепью длиной 3; последовательность является простым циклом длиной 3.

(Рис. 3)


Дата добавления: 2015-10-13; просмотров: 92 | Нарушение авторских прав


<== предыдущая страница | следующая страница ==>
ТЕОРИЯ ГРАФОВ| Дымковская игрушка

mybiblioteka.su - 2015-2024 год. (0.005 сек.)