IPB
ЛогинПароль:

> Правила раздела!

1. Заголовок или название темы должно быть информативным !
2. Все тексты фрагментов программ должны помещаться в теги [code] ... [/code] или [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ" и используйте ПОИСК !
4. НЕ используйте форум для личного общения!
5. Самое главное - это раздел теоретический, т.е. никаких задач и программ (за исключением небольших фрагментов) - для этого есть отдельный раздел!

 
 Ответить  Открыть новую тему 
> Методы задания графов.
Altair
сообщение 29.05.2005 20:09
Сообщение #1


Ищущий истину
******

Группа: Модераторы
Сообщений: 4 824
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


Кто знает какие-нибудь методы заданя графа, не описанные выше, пишите сюда.

Итак,
1. Матрица смежности.

M[1..N,1..N], где N-число вершин.
Строки и столбцы-номера вершин,на пересечении вес ребра соединяющегоэти вершины или бесконечность (машинная) если ребра нет. (нули по диагонали).

2. Список ребер.

M[1..R,1..2], где R -число ребер.

Список ребер (строки матрицы), 1 и 2 столбец это соответсвенно соединяемые ребром вершины.

3. Матрица инцедентности.

M[1..N, 1..R], где N- кол-во вершин, R-кол-во ребер.

(номера строк матрицы - номера ребер, номера столбцов-номера вершин.)
На пересечении 1 или 0 взависимости принадлежит ли вершина ребру или нет.


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Altair
сообщение 29.05.2005 20:21
Сообщение #2


Ищущий истину
******

Группа: Модераторы
Сообщений: 4 824
Пол: Мужской
Реальное имя: Олег

Репутация: -  45  +


volvo указал материал:

4. Матрица достижимости

5. Матрица контрдостижимостей


--------------------
Помогая друг другу, мы справимся с любыми трудностями!
"Не опускать крылья!" (С)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Atos
сообщение 30.05.2005 11:56
Сообщение #3


Прогрессор
****

Группа: Модераторы
Сообщений: 602
Пол: Мужской
Реальное имя: Михаил

Репутация: -  9  +


6. Список смежности

Каждой вершине ставится в соответствие список указателей на смежные ей вершины.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
zeus
сообщение 4.09.2007 17:38
Сообщение #4


Новичок
*

Группа: Пользователи
Сообщений: 10
Пол: Мужской

Репутация: -  0  +


Цитата(Atos @ 30.05.2005 11:56) *

6. Список смежности

Каждой вершине ставится в соответствие список указателей на смежные ей вершины.


а кто нибудь знает о FO и MFO-представлении графа?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Fanat
сообщение 17.09.2007 21:40
Сообщение #5


Fanat
***

Группа: Пользователи
Сообщений: 261
Пол: Мужской
Реальное имя: Сергей

Репутация: -  5  +


Цитата(zeus @ 4.09.2007 18:38) *

а кто нибудь знает о FO и MFO-представлении графа?



FO-Есть массив А, такой что, первая цифра это количество вершин,за ней до 0 вершины сменжные с первой, после 0 смежные со второй,
и так далее, в конце ставиться 0. Требует 2*число рёбер+число вершин ячеек помяти.

MFO-нечто похожее,вместо разделитилей-0ей,есть второй массив, который на i-ом месте содержит номер элемента в массиве A на котором заканчиваються вершины смежные с i-ой вершиной.
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
2ral
сообщение 21.12.2007 11:13
Сообщение #6


Новичок
*

Группа: Пользователи
Сообщений: 22
Пол: Мужской
Реальное имя: Neymanov Tural

Репутация: -  0  +


Есть еще цепная запись. вершина показывает на те с которыми она соеденина, каждая из следующих показывает на "свои вершины" и т.д. один из самых эффективных но сложный вариантов.


--------------------
Смейся и весь мир будет смеяться вместе с тобой, плачь и ты будешь плакать в одиночестве (Old Boy)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Atos
сообщение 21.12.2007 11:16
Сообщение #7


Прогрессор
****

Группа: Модераторы
Сообщений: 602
Пол: Мужской
Реальное имя: Михаил

Репутация: -  9  +


Цитата(2ral @ 21.12.2007 8:13) *

Есть еще цепная запись. вершина показывает на те с которыми она соеденина, каждая из следующих показывает на "свои вершины" и т.д. один из самых эффективных но сложный вариантов.

А чем это отличается от списка смежности?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
Michael_Rybak
сообщение 21.12.2007 13:08
Сообщение #8


Michael_Rybak
*****

Группа: Модераторы
Сообщений: 1 046
Пол: Мужской
Реальное имя: Michael_Rybak

Репутация: -  32  +


Цитата(Atos @ 21.12.2007 10:16) *

А чем это отличается от списка смежности?


Очень похоже на обычное дерево:)
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 

 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 



- Текстовая версия 28.03.2024 23:33
Хостинг предоставлен компанией "Веб Сервис Центр" при поддержке компании "ДокЛаб"