Своеобразие русской архитектуры: Основной материал – дерево – быстрота постройки, но недолговечность и необходимость деления...
Типы сооружений для обработки осадков: Септиками называются сооружения, в которых одновременно происходят осветление сточной жидкости...
Топ:
Процедура выполнения команд. Рабочий цикл процессора: Функционирование процессора в основном состоит из повторяющихся рабочих циклов, каждый из которых соответствует...
История развития методов оптимизации: теорема Куна-Таккера, метод Лагранжа, роль выпуклости в оптимизации...
Отражение на счетах бухгалтерского учета процесса приобретения: Процесс заготовления представляет систему экономических событий, включающих приобретение организацией у поставщиков сырья...
Интересное:
Что нужно делать при лейкемии: Прежде всего, необходимо выяснить, не страдаете ли вы каким-либо душевным недугом...
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Уполаживание и террасирование склонов: Если глубина оврага более 5 м необходимо устройство берм. Варианты использования оврагов для градостроительных целей...
Дисциплины:
2017-10-16 | 552 |
5.00
из
|
Заказать работу |
|
|
Пусть G - неориентированный граф. Маршрутом или цепью в G называется такая последовательность (конечная или бесконечная) вершин и ребер v0, x1, v1, x2, v2,...,vn-1, xn, vn,..., что каждые соседние два ребра xi и xi+ 1имеют общую инцидентную вершину vi. Одно и то же ребро и/или вершина могут встречаться в маршруте несколько раз. Маршрут полностью задается последовательностью ребер (x1, x2,..., xn,...) или последовательностью вершин (v0, v1, v2,.. vn,..). В конечном маршруте (x 1, x 2,... xn) имеется первое ребро x 1и последнее ребро xn. Вершина v 0, инцидентная ребру x 1, но не инцидентная ребру x 2, называется началом маршрута, а вершина vn, инцидентная ребру xn, но не инцидентная ребру xn- 1, называется концом маршрута.
Длиной (или мощностью) маршрута называется число ребер, входящих в маршрут, причем каждое ребро считается столько раз, сколько оно входит в данный маршрут.
Пример 4.6. В изображенном на рис. 4.3 графе рассмотрим два маршрута из вершины v 1в вершину v 4: M 1= (x 1, x4, x 6) и M 2= (x 1, x 3, x 5, x 6). Длина маршрута M 1 равна 3, а длина маршрута M 2 равна 4
Рис.4.3
Замкнутый маршрут называется циклом.
Маршрут (цикл), в которой все ребра различны, называется простой цепью (циклом). Маршрут (цикл), в которой все вершины, (кроме первой и последней), различны, называется элементарной цепью (циклом). Гамильтонова цепь (цикл) − простая цепь (цикл), проходящая через все вершины. Эйлерова цепь (цикл) − цепь (цикл), содержащая все ребра графа по одному разу.
Пример 4.7. В приведенном на рис 4.3 графе выделим следующие маршруты:
(x 1, x 4, x 6) – простая элементарная цепь длины 3, т.к. все ребра и вершины попарно различны;
(x 1, x 3, x 2) – простой элементарный цикл, т.к. это замкнутый маршрут, у которого все ребра и вершины, кроме первой и последней, различны;
|
(x 1, x 3, x 5, x 4)– цепь, которая является простой, но не элементарной;
(x 1, x 3, x 3) – цепь длины 3, не являющаяся ни простой, ни элементарной цепью, т.к. ребро x 3и вершина v 2 встречаются дважды;
(x 1, x 3, x 5, x 6) – Гамильтонова цепь.
Пути, контуры в ориентированном графе
Понятия пути, контура в ориентированном графе аналогичны понятиям цепи, цикла в неориентированном графе.
Путем ориентированного графа называется последовательность дуг, в которой конечная вершина всякой дуги, отличной от последней, является начальной вершиной следующей дуги. Число дуг пути называется длиной пути.
Путь называется контуром, если его начальная вершина совпадает с конечной вершиной.
Путь (контур), в котором все дуги различны, называется простым. Путь (контур), в котором все вершины, кроме первой и последней, различны, называется элементарным. Гамильтонов путь (контур) − простой путь (контур), проходящий через все вершины. Эйлеров путь (контур) − путь (контур), содержащий все дуги графа по одному разу. Путь из vi в vj называется кратчайшим, если он содержит наименьшее число дуг по сравнению со всеми другими путями из vi в vj.
Отметим, что понятиям ребра, маршрута, цепи, цикла в неориентированном графе соответствуют понятия дуги, пути, ориентированной цепи, контура в ориентированном графе.
Пример 4.8. В приведенном на рис 4.4 орграфе выделим следующие пути:
(v 1, v 2, v 3, v 4) – простой элементарный путь, т.к. каждая вершина и каждая дуга используются не более одного раза;
Рис. 4.4
(v 2, v 5, v 6, v 7, v 2) – простой элементарный контур, т.к. это замкнутый путь, в котором все дуги и вершины, кроме первой и последней, различны;
(v 1, v 2, v 3, v 4, v 5, v 6) – Гамильтонов путь.
|
|
Типы оградительных сооружений в морском порту: По расположению оградительных сооружений в плане различают волноломы, обе оконечности...
Архитектура электронного правительства: Единая архитектура – это методологический подход при создании системы управления государства, который строится...
Двойное оплодотворение у цветковых растений: Оплодотворение - это процесс слияния мужской и женской половых клеток с образованием зиготы...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!