 |
|
Модераторы: Poseidon |
 
|
|
[ДескрМат] матрицы смежностей, посчитать сколько возможных путей. 
| KatrinIceLand |
|
|||
 Бывалый  Профиль Группа: Участник Сообщений: 166 Регистрация: 16.3.2006 Репутация: нет Всего: нет |
Объясните мне пожалуйста (до меня никак не доходит
 ) когда считаем число возможных путей (paths) используя матрицу смежности надо умножать или возводить в степень или как это число высчитывается (почему 0 = 8).Например, (пример из книги): дана матрица: (a,b,c,d) 0110 1001 1001 0110 Значит число возможных путей длинной 4 от a до d равно: 8008 А4 0880 0880 8008 Значит 8 путей возможных. Как это считается? И какую роль играют данный вершины (a,d) будет ли разница если данные точки будут другими или вообще не будут указаны? Представляю насколько это элементарно, но мне нужно объяснение  --------------------
[... кто изобрел математику? А зачем?... |
|||
|
||||
Загрузка ...
| devyshko |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 67 Регистрация: 2.12.2007 Репутация: нет Всего: нет |
Ну даж не знаю как тут получили 8 путей. Как по мне, то их тут два
. Нарисовала по матрице граф и посчитала. |
|||
|
||||
| KatrinIceLand |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 166 Регистрация: 16.3.2006 Репутация: нет Всего: нет |
Нет, в книге все правильно, даже если по графу считать, все равно 8 получается: e.g. {a,b,a,b,d}, {a,b,a,c,d}, {a,b,d,c,d}, {a,c,a,b,d} ну и так далее, в общем 8. Но как по матрице считать, ведь граф на экзамене будет совсем не так прост. Надо понять как по матрице считать  --------------------
[... кто изобрел математику? А зачем?... |
|||
|
||||
| devyshko |
|
|||
|
Шустрый Профиль Группа: Участник Сообщений: 67 Регистрация: 2.12.2007 Репутация: нет Всего: нет |
Нас учили так! В начальную точку возвращаться нельзя и из конечной тоже. А тут все эти правила нарушены
любопытно |
|||
|
||||
| KatrinIceLand |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 166 Регистрация: 16.3.2006 Репутация: нет Всего: нет |
Если вершины не повторяются в "пути", то это простой "путь", а если повторяются, то сложный. Ну во всяком случае по английски это звучит так: Simple path and not simple path if repits its vertices. Странно, я думала это очень просто, но никто не может объяснить  --------------------
[... кто изобрел математику? А зачем?... |
|||
|
||||
| KatrinIceLand |
|
|||
|
Бывалый Профиль Группа: Участник Сообщений: 166 Регистрация: 16.3.2006 Репутация: нет Всего: нет |
А вот конкретное задание:
дана матрица: R S T U R 0 0 3 2 S 0 0 1 0 T 3 1 0 4 U 2 0 4 0 Посчитать сколько макс возможных путей длинной 3 между S and U используя матрицу. Помогите, не понимаю как решать Это сообщение отредактировал(а) KatrinIceLand - 25.2.2008, 14:13 --------------------
[... кто изобрел математику? А зачем?... |
|||
|
||||
|
|
| Правила форума "Центр помощи" | |
|
|
ВНИМАНИЕ! Прежде чем создавать темы, или писать сообщения в данный раздел, ознакомьтесь, пожалуйста, с Правилами форума и конкретно этого раздела.
Более подробно с правилами данного раздела Вы можете ознакомится в этой теме. Если Вам помогли и атмосфера форума Вам понравилась, то заходите к нам чаще! С уважением, Poseidon, Rodman |
| 1 Пользователей читают эту тему (1 Гостей и 0 Скрытых Пользователей) | |
| 0 Пользователей: | |
| « Предыдущая тема | Центр помощи | Следующая тема » |
[ Время генерации скрипта: 0.0862 ] [ Использовано запросов: 21 ] [ GZIP включён ]
Реклама на сайте Информационное спонсорство
|
|
По вопросам размещения рекламы пишите на vladimir(sobaka)vingrad.ru
Отказ от ответственности Powered by Invision Power Board(R) 1.3 © 2003 IPS, Inc. |