Вопросы

Dmitry Schelkov
Dmitry Schelkov | Репутация: 0 (Без статуса) 29 сентября 2015 в 15:52
О правильности приведённого примера

В лекции 3 часть номер 2 приведён пример нахождения транзитивного замыкания по матрице смежности. Из примера для обратного транзитивного замыкания видно, что путь для достижения вершины х6 в вершину х3 равен 3, а не 2, как показано в табличном примере. Мне кажется, что в лекции ошибка.

Вячеслав Коваленко
Вячеслав Коваленко | Репутация: 0 (Без статуса) 17 мая 2014 в 12:49
Определение пути в графе

В курсе "Введение в теорию графов" в лекции 4 "Достижимость в графарх" дано выражение для нахождения множетсва вершин, входящих в путь из одной вершины графа в другую и по рис.4.2. показан пример нахождения такого множества для пути из вершины х2 в вершину х4 - это множетсво (х2, х3, х4, х5). По рисунку видно что путь не оптимален и для того, чтобы он проходил через все вершины этого множества, через х4 нужно пройти два раза. Правильно ли я понимаю, что данное определение пути дает не всегда оптимальный путь и что определение оптимально (кратчайшего) пути - отдельная задача? Или в примере ошибка?

Юлия Бугрова
Юлия Бугрова 21 августа 2015 в 22:46

На сколько я поняла, нахождение оптимального пути - это уже второй вопрос, в понятии достижимости, главное, что это путь вообще существует.