67601
Задача поиска маршрутов в графе (путей в орграфе)
Задача
Математика и математический анализ
Исходя из некоторой вершины всегда следовать по тому ребру которое не было пройдено или было пройдено в противоположном направлении. 3 Для всякой вершины отмечать ребро по которому в вершину попали в первый раз 4 Исходя из некоторой вершины идти по первому заходящему в ребру лишь тогда когда нет других...
Русский
2014-09-12
362.5 KB
11 чел.
Лекция №10
Задача поиска маршрутов в графе (путей в орграфе)
Алгоритм Тэрри поиска маршрута в связном графе, соединяющего вершины и .
Правила.
1) Идя по произвольному ребру всегда отмечать направление его прохождения.
2) Исходя из некоторой вершины всегда следовать по тому ребру, которое не было пройдено или было пройдено в противоположном направлении.
3) Для всякой вершины отмечать ребро по которому в вершину попали в первый раз
4) Исходя из некоторой вершины идти по первому заходящему в ребру лишь тогда, когда нет других возможностей.
Замечание: из полученного пути можно выделить простую цепь.
Утверждения:
1) каждый минимальный путь (маршрут) является простой цепью
Доказательство.
Пусть минимальный путь в орграфе D, не являющийся простой цепью. Тогда i и j такие, что и vi=vj. Рассмотрим путь . Его длина меньше, чем , что противоречит предположению.
2) (о минимальности подпути минимального пути). Пусть - минимальный путь (маршрут) в орграфе D (в графе G). Тогда для i и j таких, что путь (маршрут) тоже является минимальным.
Доказательство. Предположим, что не является оптимальным, тогда т.ч. он короче чем . Тогда заменив на в можно найти более короткий, чем путь не является минимальным. Пришли к противоречию.
Пусть орграф - некоторая вершина .
Обозначим - образ вершины ;
- прообраз вершины ;
- образ множества вершин V1 ;
прообраз множества вершин V1.
Для неориентированного графа образ и прообраз совпадают.
Пусть граф .
Обозначим - образ вершины ;
- образ множества вершин V1.
Пусть орграф с n2 вершинами и v,w (vw) заданные вершины из V
Алгоритм поиска минимального пути из в в орграфе D
(алгоритм фронта волны).
1) Помечаем вершину индексом 0, затем помечаем вершины образу вершины индексом 1. Обозначаем их FW1 (v). Полагаем k=1.
2) Если или k=n-1, и одновременно то вершина не достижима из . Работа алгоритма заканчивается.
В противном случае продолжаем:
3) Если , то переходим к шагу 4.
В противном случае мы нашли минимальный путь из в и его длина =k. Последовательность вершин
есть этот минимальный путь. Работа завершается.
4) Помечаем индексом k+1 все непомеченные вершины, которые принадлежат образу множества вершин c индексом k. Множество вершин с индексом k+1 обозначаем . Присваиваем k:=k+1 и переходим к 2).
Замечания
Множество называется фронтом волны kго уровня.
Вершины могут быть выделены неоднозначно, что соответствует случаю, если несколько min путей из в .
Пример 1. Дана матрица смежности. Найти минимальный путь из v1 в v6.
Исх\вход |
||||||
0 |
0 |
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
1 |
1 |
1 |
|
1 |
1 |
0 |
1 |
1 |
1 |
|
0 |
1 |
1 |
0 |
1 |
0 |
|
1 |
1 |
1 |
1 |
0 |
0 |
|
1 |
1 |
1 |
1 |
1 |
0 |
|
0 |
2 |
2 |
1 |
1 |
3 |
,
Пример 2. Дан орграф.
Задание. Найти минимальный путь из v1 в v6.
Матрица смежности
Исх\вход |
||||||
0 |
0 |
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
0 |
1 |
1 |
|
1 |
1 |
0 |
1 |
1 |
1 |
|
0 |
1 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
0 |
0 |
0 |
0 |
0 |
|
0 |
2 |
|
1 |
1 |
3 |
Расстояния в графе
Пусть - граф (или псевдограф).
Расстоянием между вершинами наз. min длина пути между ними. .
Расстояние в графе удовл. аксиомам метрики
1) ,
2) (не орграф)
3)
4) в связном графе ( в орграфе, если не пути).
Пример
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
1 |
1 |
0 |
0 |
21 |
0 |
2 |
0 |
0 |
1 |
0 |
0 |
0 |
3 |
0 |
0 |
0 |
0 |
0 |
1 |
4 |
1 |
1 |
0 |
0 |
0 |
0 |
5 |
0 |
0 |
1 |
1 |
0 |
0 |
6 |
0 |
1 |
0 |
0 |
0 |
0 |
Из 1 |
0 |
1 |
2 |
2 |
1 |
3 |
Из 2 |
|
0 |
1 |
|
|
2 |
Из 3 |
|
2 |
0 |
|
|
1 |
Из 4 |
1 |
1 |
2 |
0 |
2 |
3 |
Из 5 |
2 |
3 |
1 |
1 |
0 |
2 |
Из 6 |
|
1 |
2 |
|
|
0 |
опр || Пусть связный граф (или псевдограф).
Величина - называется диаметром графа G.
Пусть .
Величина - называется максимальным удалением (эксцентриситетом) в графе G от вершины .
Радиусом графа G наз. величина
Любая верш. такая, что наз. центром графа G.
Матрица смежности
0 |
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
0 |
|
0 |
1 |
0 |
1 |
0 |
|
0 |
1 |
1 |
0 |
1 |
|
0 |
0 |
0 |
1 |
0 |
Матрица расстояний
0 |
1 |
2 |
2 |
3 |
|
1 |
0 |
1 |
1 |
2 |
|
2 |
1 |
0 |
1 |
2 |
|
2 |
1 |
1 |
0 |
1 |
|
3 |
2 |
2 |
1 |
0 |
Центры в вершинах 2,3,4
Примеры.
Матрица смежности
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
0 |
1 |
0 |
0 |
1 |
0 |
2 |
1 |
0 |
0 |
1 |
0 |
1 |
3 |
0 |
0 |
0 |
0 |
1 |
1 |
4 |
0 |
1 |
0 |
0 |
1 |
0 |
5 |
1 |
0 |
1 |
1 |
0 |
0 |
6 |
0 |
1 |
1 |
0 |
0 |
0 |
Матрица расстояний
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
0 |
1 |
2 |
2 |
1 |
2 |
2 |
1 |
0 |
2 |
1 |
2 |
1 |
3 |
2 |
2 |
0 |
2 |
1 |
1 |
4 |
2 |
1 |
2 |
0 |
1 |
2 |
5 |
1 |
2 |
1 |
1 |
0 |
2 |
6 |
2 |
1 |
1 |
2 |
2 |
0 |
, центр - все вершины
А также другие работы, которые могут Вас заинтересовать | |||
29247. | Феномены русской, российской, советской культуры | 52.5 KB | |
Проблема самосознания русской культуры. Этапы становления русской идеи. Формирование русской национальной культуры на протяжении веков проходило в русле этнического разнообразия преодоления разобщенности в условиях интенсивного воздействия извне: соединение Запада и Востока наслоение различных этнических и региональных культурных типов временных компонентов конфессиональных общностей. | |||
29248. | Понятие культурной самоидентичности | 32 KB | |
Современные глобальные проблемы есть следствие логическое продолжение глубокой структурной несогласованности человеческой субъективности кризиса его самоидентичности. Распад социальной системы начинается с распада социальных связей и разрушения социальных субъектов кризиса их личностных ценностных ориентации и утраты самоидентичности. Проблема самоидентичности является стержнем ядром всей социальной проблематики. | |||
29249. | Символ. Смысловая структура символа | 53.5 KB | |
Языком культуры в широком смысле этого понятия называются те средства знаки символы тексты которые позволяют людям вступать в коммуникативные связи друг с другом ориентироваться в пространстве культуры. Язык культуры это универсальная форма осмысления реальности в которую организуются все вновь возникающие или уже существующие представления восприятия понятия образы и другие подобного рода смысловые конструкции носители смысла. Основной структурной единицей языка культуры с точки зрения семиотики являются знаковые системы.Любой... | |||
29250. | Культура как смысловое поле человеческой жизнедеятельности и способ реализации творческих возможностей человека | 60.5 KB | |
Речь не о какомто единственном и едином способе деятельности а о целом их ансамбле таком же сложном как и система созидательных способов деятельности деятельность распредмечивания изоморфносимметрична деятельности опредмечивания. Но и зеркально симметричным и возвращает нас к исходному пункту деятельности человеку. Какими качествами он должен обладать чтобы выполнить эту функцию Человек субъект деятельности. | |||
29251. | КУЛЬТУРА ЗАПАДНОЕВРОПЕЙСКОГО СРЕДНЕВЕКОВЬЯ | 53.5 KB | |
В этом исторически длительном социокультурном процессе развития феодального общества вырабатывался своеобразный тип отношений человека к миру качественно отличающий его как от культуры античного общества так и от последующей культуры Нового времени эпохи буржуазного производства. Именно христианство стало основной осью складывающегося с V века в Западной Европе мира которая влияла на все стороны жизни человека его духовные приоритеты устои общества. Следование этому образцу становилось смыслом жизни каждого человека так как... | |||
29252. | Строение культуры | 38 KB | |
Кагану Человек общество культура являются системными объектами. Культура понимается как система высшего уровня сложности. Изоморфность филогенеза и онтогенеза свидетельствуют о том что культура есть целостновсесторонний способ очеловечивания человека и человеческого рода и отдельного его представителя в процессе обретения им таких качеств которые природе неизвестны и порождаются преобразованием биологической формы бытия в социокультурную. Таким образом первичная форма существования культуры физическая культура. | |||
29253. | Мейнстрим, субкультура и контркультура | 34 KB | |
Малые культурные миры называют субкультурами. Субкультура это подкультура или культура в культуре. а субкультура отличается лишь однойдвумя чертами. | |||
29254. | СУБЪЕКТ и ОБЪЕКТ КУЛЬТУРЫ | 27 KB | |
Субъект культуры в культурологическом понимании какаялибо социальная общность или конкретный индивид реализующий в практической деятельности культуросозидающее начало потребление и духовное освоение объектов культуры воспроизводство себя как человека определенной исторической эпохи. В культурологическом понимании объект культуры элемент фрагмент бытия культуры являющийся сферой реализации активности и историческим результатом практической деятельности субъекта культуры. | |||
29255. | ипология культуры (типы культур) | 36 KB | |
Типология культур строится на основании нескольких критериев: связь с религией культуры религиозные и светские; региональная принадлежность культуры культуры Востока и Запада средиземноморская латиноамериканская; региональноэтническая особенность русская французская; принадлежность к историческому типу общества культура традиционного индустриального постиндустриального общества; хозяйственный уклад культура охотников и собирателей огородников земледельцев скотоводов индустриальная культура; сфера общества или вид... | |||