АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

Пример 8.

В данном графе последовательности дуг

а₃, а₆, а₁₁ (1)

а₁₁, а₃, а₄, а₇, а₁, а₁₂, а₉ (2)

а₃, а₄, а₇, а₁₀, а₉, а₁₁ (3)

являются замкнутыми путями.

Пути (1) и (3) являются контурами, т. к. в них любая вершина используется только один раз (за исключением начальной и конечной, которые совпадают), а путь (2) не является контуром, т. к. вершина x₁ используется в нём дважды.

Контур, проходящий через все вершины графа, имеет особое значение и называется гамильтоновым контуром. Например, контур (3) из примера 8 является гамильтоновым контуром. Не все графы обладают гамильтоновыми контурами.

§ 2.7.3. Классификация маршрутов.

Обобщённое представление всех описанных типов маршрутов на графах можно изобразить в виде условного графа.

Эйлеровы циклы Гамильтоновы контуры

§ 2.11. Деревья

§ 2.11.1. Типы деревьев

Опр.6. Неориентированное дерево – это:

1. связанный (n,m)- граф, причём m=n-1;

2. связанный граф, не имеющий циклов;

3. граф, в котором каждая пара вершин соединена одной и только одной простой цепью

Все эти определения равнозначны. Убедимся в этом.

Любая иерархическая структура представляется неориентированным деревом.

Опр.7 Пусть G=(V,E) – неориентированный граф с n вершинами. Остовным деревом (или остовом) графа G называется всякий остовной подграф графа G, являющийся деревом.

Дата добавления: 2015-09-27 | Просмотры: 352 | Нарушение авторских прав