рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

Орциклы и циклы

Орциклы и циклы - Лекция, раздел Образование, Введение в теорию графов 1. Лекция: Графы и способы их представления Особую Группу Составляют Замкнутые Пути. Путь A1, A2, ....

Особую группу составляют замкнутые пути. Путь a1, a2, ...,aq называется замкнутым, если в нем начальная вершина a1 и конечная вершина aq совпадают. Так, например, для графа на рис. 8.3 можно составить несколько замкнутых путей:

М1: a3, a6, a11,

М2: a11, a3, a4, a7, a1, a12, a9 ,

М3: a3, a4, a7, a10, a9, a11.

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

Контур, проходящий через все вершины графа, имеет особое название – гамильтонов контур. Путь М3 является гамильтоновым контуром. Он показан штриховой линией на рис. 8.3.

 


Рис. 8.3. Орциклы в графе

Для неориентированного графа замкнутым маршрутом является неориентированный двойник замкнутого пути, т. е. замкнутым маршрутом является маршрут, в котором совпадают начальные и конечные вершины.

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

Эйлеровым циклом в графе называется цикл, содержащий все ребра графа. Граф, содержащий эйлеров цикл, называется эйлеровым графом.

Основная теорема о существовании эйлерова цикла формулируется так.

ТЕОРЕМА. Связный неориентированный граф G содержит эйлеров цикл тогда и только тогда, когда число вершин нечетной степени равно нулю 0 или 2.

Эйлер первым в своей знаменитой задаче о Кенигсбергских мостах поставил вопрос о существование такого цикла.

На реке Преголя в Кенигсберге было два острова. Они соединялись между собой и с берегами реки семью мостами, как схематично показано на рис. 8.4. Задача заключалась в том, чтобы за одну прогулку обойти все семь мостов, проходя по каждому мосту только один раз, и вернуться в исходное место.

Если каждый берег реки и острова считать вершинами графа, а каждый мост – ребром, то карту рис. 8.4,а можно представить в виде графа на рис. рис. 8.4,б и ответ на поставленный вопрос зависит теперь от существования эйлерова цикла в этом графе. Эйлер установил, что указанный граф не содержит эйлерова цикла, и этот результат ознаменовал рождение теории графов.

 


Рис. 8.4. а – схема Кенигсбергских мостов; б – эквивалентный граф

 

 

 


 

 

Развернуть
Открыть в широком формате

– Конец работы –

Эта тема принадлежит разделу:

Введение в теорию графов 1. Лекция: Графы и способы их представления

Введение в теорию графов Лекция Графы и способы их представления... Приводятся начальные сведения о графах и основные понятия и определения такие как орграф смешанный граф дубликат графа дуга петля полустепени...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: Орциклы и циклы

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

Основные определения
Граф задается множеством точек или вершин х1, х2, ..., хn и множеством линий или ребер a1, a2, ... , am, соеди

Прямые отображения
Прямым отображением 1-го порядка вершины хi является множество таких вершин графа, для которых существует дуга (хi, xj), т. е Г1( х

Обратные отображения
Обратным отображением 1-го порядка для вершины хiявляется множество элементов xjтаких, что существует дуга(xj, хi), принадлежащая множеству дуг графа, т.

Прямое транзитивное замыкание
Прямым транзитивным замыканием некоторой вершины хi – T+( хi )является объединение самой вершины хiс прямыми отображениями 1-го поря

Обратное транзитивное замыкание
Обратным транзитивным замыканием некоторой вершины хi –T-( хi )является объединение этой вершины с обратными отображениями 1-го, 2-го и т. д. n

Нахождение транзитивных замыканий по матрице смежности
Рассмотрим метод нахождения прямого транзитивного замыкания по матрице смежности, показанной на рис. 3.3,а для вершины х2графа, изображенного на рис. 3.3,б. На 1-м шаге итерации заносим

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

Нахождение множества вершин, входящих в путь
Если необходимо узнать о вершинах графа, входящих в эти пути, то следует вспомнить определения прямого и обратного транзитивных замыканий. Так как T+(xi) – это множество верши

Матричный метод нахождения путей в графах
Матрица смежности полностью определяет структуру графа. Возведем матрицу смежности в квадрат по правилам математики. Каждый элемент матрицы А2 определяется по формуле a(2)

Доказательство
1. Необходимость. Поскольку множество X разбивается на две части Xа и Xb , то Xа Xb = X и Xа Xb = Ø . Пусть существ

Лекция: Виды подграфов
    Пусть дан граф G = (X, A), где X = {хi}, i = 1, 2, ..., n – множество вершин, A = { ai }, i = 1, 2, ..., m – множество дуг. Подграфом

Сильно связные графы и компоненты графа
Кроме классификации типов графов данной в п. 3.1 графы могут быть классифицированы по связности: сильно связные, односторонне связные, слабо связные и несвязные. Орграф называется

Метод Мальгранжа
Пусть дан граф G=(X, A), где X={ хi }, i =1, 2, ... , n – множество вершин, а A={ ai }, i =1, 2, ..., m – где множество дуг, описанных матрицей смежности. Алгоритм разбиени

Пути и маршруты
Путем в орграфе называется последовательность дуг, в которой конечная вершина всякой дуги, кроме последней, является начальной вершиной следующей дуги. Например, для г

Вес и длина пути
Иногда дугам графа сопоставляют числа ai сi , называемые весом или длиной, или стоимостью или ценой. В каждом конкретном случае выбирается то слово, которое ближе подходит по

Лекция: Алгоритм Дейкстра поиска кратчайших путей в графе
  Наиболее эффективный алгоритм решения задачи о кратчайшем пути первоначально дал Дейкстра . В общем случае этот метод основан на приписывании вершинам временных пометок, причем поме

Превращение пометки в постоянную
Ш А Г 3. Среди всех вершин с временными пометками найти такую, для которой L(x*i)=min[L(xi)]. Ш А Г 4. Считать пометку вершины x*i

Первая итерация
Ш А Г 2. Найдем прямое отображение для текущей рассматриваемой вершины: Г(р) = Г(х1) = { х2, х7, х8, х9 }. Все вершины, входящие в прямое отоб

Вторая итерация
Граф с текущими значениями меток вершин показан на рис. 9.3   Рис. 9.3. Пометки в конце первой итерации Ш А Г 2. Находим Г(х7) = { х

Третья итерация
Граф с текущими значениями меток вершин показан на рис. 9.4.   Рис. 9.4. Пометки в конце второй итерации Ш А Г 2. Находим Г(х2) = {х

Четвертая итерация
Ш А Г 2. Находим Г(х8) = { х1, х5, х6, х9 }. Метки вершин х5, х6 и х9 временные, следовательно, пересчитываем

Пятая итерация
Ш А Г 2. Находим Г(х4) = { х3, х5, х6, х7 }. Метки вершин х3, х5 и х6 временные, следовательно, пересчитываем

Шестая итерация
Ш А Г 2. Находим Г(х9) = {х1, х2, х6, х7, х8}. Метка вершины х6 временная, следовательно пересчитываем ее значение:

Седьмая итерация
Ш А Г 2. Находим Г(х5) = { х4, х6 }. Метка вершины х6 временная, следовательно, пересчитываем ее значение: L(х6)= min [17, 12 + 10 ]

Восьмая итерация
Ш А Г 2. Находим Г(х6) = { х3, х5, х7, х8, х9 }. Метка вершины х3 временная, следовательно, пересчитываем ее значение:

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги