АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Определения. Маршрутом в графе G(V,E) называется чередующаяся последовательность вершин и ребер v1, e1, v2, e2,

Читайте также:
  1. I. Открытые способы определения поставщика.
  2. III. Используемые определения и обозначения
  3. Алгоритм определения предпочтительной организационной структуры управления диверсифицированной фирмы
  4. АНКЕТА ОПРЕДЕЛЕНИЯ ВОЛЕВЫХ КАЧЕСТВ У УЧАЩИХСЯ 12-16 ЛЕТ
  5. АНКЕТА ОПРЕДЕЛЕНИЯ ВОЛЕВЫХ КАЧЕСТВ У УЧАЩИХСЯ 16 ЛЕТ И СТАРШЕ И СТУДЕНТОВ
  6. АНКЕТА ОПРЕДЕЛЕНИЯ ВОЛЕВЫХ КАЧЕСТВ У УЧАЩИХСЯ 7-12 ЛЕТ
  7. Базовые параметры радиационных свойств горных пород и методы их определения
  8. Базовые параметры электромагнитных свойств горных пород и методы их определения.
  9. Бальнеология. Понятия и определения
  10. БИАС-тест определения репрезентативных систем
  11. Более результативной с точки зрения определения победите-
  12. Верный способ определения ГПЗ зоны в помещении

Маршрутом в графе G(V,E) называется чередующаяся последовательность вершин и ребер v1, e1, v2, e2,...,vk,ek,vk+1, в которой любые два соседних элемента инцидентны.

Это определение подходит также для псевдо-, мульти- и орграфов. Для «обычного» графа достаточно указать только последовательность вершин или только последовательность ребер.

Если v1=vk+1, то маршрут замкнут, иначе открыт.

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

Замкнутая цепь называется циклом; замкнутая простая цепь называется простым циклом.

Число циклов в графе G обозначается z(G) (является инвариантом). Граф без циклов называется ациклическим.

Для орграфов цепь называется путем, а цикл - контуром.

Пример

В графе, диаграмма которого приведена на рис. 3.10:

 

1. v1,v3,v1,v4 - маршрут, но не цепь;

2. v1, v3, v5, v2, v3, v4 - цепь, но не простая цепь;

3. v1, v4, v3, v2, v5 - простая цепь;

4. v1, v3, v5, v2, v3, v4, v1- цикл, но не простой цикл;

5. v1,v3,v4 - простой цикл.


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

Две вершины графа называются связанными, если существует маршрут, соединяющий эти вершины. Граф называется связным, если любая пара его вершин связанна.

Граф называется деревом, если он связен и не содержит циклов.


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.003 сек.)