четверг, 06 декабря 2012
23:13

Построить граф и задать его матрицей расстояний

все записи пользователя в сообществе Juksound
Добрый день! Помогите пожалуйста с решением задачи по САПР
Условие: Постройте граф и задайте его матрицей расстояний G(X,V) X={a,b,c,s,e} V={ab, ac, ae, be, ec, es, cs}.
Граф я построил (приложил файликом-картинкой), но откуда взять расстояния между точками графа и начать составлять матрицу расстояний??

@темы: Матрицы

URL
Комментарии
06.12.2012 в 23:22

Дилетант
На плечах гигантов, на спинах электронов
А матрица D - это что такое?..
По-моему это она и есть...
URL
06.12.2012 в 23:37

Дилетант
На плечах гигантов, на спинах электронов
Кстати вот еще какой вопрос. Граф у вас не ориентирован? Если да, то всё правильно, если нет, то расставьте стрелки, и матрица тогда будет несимметрична.
Расстояние (если не задан вес на дугах считается просто как длина пути между вершинами).
URL
07.12.2012 в 00:04

Juksound
Что такое матрица Д не знаю, мы так на парах обозначали... Стрелок тоже не расставляли... Примеры решений приложил картинкой (не могу понять откуда цифры берутся над рёбрами?)

URL
07.12.2012 в 00:08

Гость
не могу понять откуда цифры берутся над рёбрами?
Это не часть условия?
URL
07.12.2012 в 00:11

Juksound
Вот и я не помню =( Но условие задачи в первом посте и там никакихчисловых значений нет только ab, ac, ae... и т.д. Может кто сталкивался и знает откуда эти цифры и что перед ними за значок...
URL
07.12.2012 в 00:13

konetz
какое растояние от a до b?
URL
07.12.2012 в 00:28

Juksound
Не знаю - условие дословно написано в первом посте. это всё...
URL
07.12.2012 в 10:30

Дилетант
На плечах гигантов, на спинах электронов
konetz, а что там на 708 странице? Алгоритм Флойда-Уоршолла?
в моем Кормене он не там)
Но у меня другое издание...

Juksound, веса на дугах либо задаются по условию, либо вам преподаватель должен был объяснить какой-нибудь алгоритм их задания. Т.е. нет таких универсальных принципов, откуда можно было бы их узнать.
На ваших картинках D это и есть матрица расстояний. По ней потом можно найти радиус и диаметр графа, ну и еще всяческие показатели.
URL
07.12.2012 в 14:21

konetz
;) Начало главы с этим алгоритмом
URL
07.12.2012 в 19:48

Juksound
Спасибо всем! Буду пытаться искать истину) Графы у меня строятся по электрическим схемам. Точки - это сверловки под радиоэлементы, а дуги - дорожки, их соединяющие, как-то так... Они применяются далее в P-CAD при разработке эл. схем.
URL
07.12.2012 в 21:34

Дилетант
На плечах гигантов, на спинах электронов
Juksound, тогда у вас и впрямь должны быть геометрические графы с длинами на ребрах...
Но все равно это входные данные.
URL
17.02.2016 в 07:05

Гость
Владелец дневника видит IP-адреса пользователей, оставивших комментарии!
URL