Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

IV. Решение некоторых типовых заданий





Доверь свою работу кандидату наук!
1500+ квалифицированных специалистов готовы вам помочь

III. Самостоятельная работа 8.

1.Найти кратчайший путь из вершины в вершину в заданном графе.

 

 

2.Найти кратчайший путь из вершины в вершину во взвешенном графе.

 

1. Найти кратчайший путь из вершины в вершину в заданном графе.

Решение. Используем алгоритм задачи о нахождении кратчайшего пути из А в В в смысле наименьшего количества ребер.

1. Вершине А припишем индекс 0.

2. Всем вершинам, смежным с вершиной А, припишем индекс 1.

3. Всем вершинам, смежным с вершинами индекса 1 и не имеющим индекса, припишем индекс 2.

4. Всем вершинам, смежным с вершинами индекса 2 и не имеющим индекса, припишем индекс 3. В нашем случае, в этот момент вершина В также получит индекс 3.

Процесс останавливаем (несмотря на то, что остались непомеченные вершины).

Таким образом, мы нашли длину кратчайшего пути.

Построим сам путь.

5. Вершина В имеет индекс 3. Среди смежных с ней вершин есть вершина индекса, на единицу меньшего, чем 3, то есть, индекса 2. Перейдём из Вк этой вершине ( в нашем случае такая вершина одна).

6. Среди вершин, смежных с найденной вершиной индекса 2 есть вершина индекса, на единицу меньшего, то есть, индекса 1 (такая вершина также в нашем случае единственна). Перейдём к ней.

7. Вершина индекса 1 смежна с вершиной А. Переходя от неё к А, заканчиваем построение кратчайшего пути в заданном невзвешенном графе.

 

V. Расчётно-графическая работа. Задание 1.

Поможем в написании учебной работы
Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой




Дата добавления: 2014-11-25; Просмотров: 905; Нарушение авторских прав?;


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



ПОИСК ПО САЙТУ:


studopedia.su - Студопедия (2013 - 2022) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.016 сек.