Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 11.05.2008, 12:56
AstaroT

 
Сообщений: n/a

Синтез графа
Поставлена задача: Синтез графа заданным множеством фундаментальных разрезов или циклов. Для решения предлагается использовать алгоритмы упоминающиеся в работах Майеды или Биксби и Вагнера.
Главная проблема в том что мне не удалось найти ни один из вышеуказанных алгоритмов.
Ценна будет любая помощь: ссылки, мысли, реализации на любых языках программирования.
Заранее спасибо.
  #2  
Старый 15.03.2009, 20:42
Даниил Ярославцев

 
Сообщений: n/a

Здравствуйте! Предлагаю взаимопомощь по этой задаче
Я пишу по ней курсовую работу, и над этой темой работал мой преподаватель дискретной математики Ротко Владимир Федорович. В 1 номере журнала "Кибернетика" за 1986г сохранилась статья из 6 страниц с названием "Эффективные алгоритмы синтеза графов с заданным множеством фундаментальных разрезов или циклов" (полное название смотрите ниже, в списке литературы). Советую вам ее поискать.
Некоторое подобие данной статьи, судя по всему, укороченное, я нашел и отфотографировал - http://s1.filesdump.com/file/5bb3ee6...hotos.rar.html

Я предлагаю вам решить задачу так:

За исходные данные для программы примем цикломатическую матрицу или матрицу циклов графа. Назовем ее В. Данная матрица представляет любой граф с точностью до изоморфизма, так что как выходные данные нам достаточно получить матрицу инцидентности для неорграфа, или матрицу смежности для орграфа.

1. Для неорграфа:
Если B – транспонированная матрица инцидентности, а С – матрица циклов графа G, то С*B = 0(mod 2), т.е., произведение этих матриц равно нулевой матрице. Таким образом, зная С, мы можем программно найти В, наши выходные данные.

2. Для орграфа:
Для любого неорграфа матрица смежности А выражается через матрицу инцидентности В следующим образом:
А = В*X - diag[d1,...,dn]
где di - степень i-ой вершины, X - транспонированная матрица В, diag[d1,...,dn] - матрица размерности n*n с элементами d1,...,dn на главной диагонали. Т.е., сначала получим матрицу инцидентности для графа (см. пункт 1), а затем - преобразуем в матрицу смежности на основании этого свойства.

Подробнее о свойствах 1 и 2 можно прочитать здесь:
http://www.adeptis.ru/russman/articles/157.pdf

Библиография по теме:
1. Басакер Р., Саати Г. Конечные графы и сети. — М: Наука. ГРФМЛ, 1974. —
368 с.
2. Кристофидес Н. Теория графов: алгоритмический подход. - М: Мир. 1978.
3. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М: Мир, 1984. 455с.
4. Зыков А.А. Основы теории графов. — М.: Паука. ГРФМЛ. 1987. — 384 с.
5. Rixby R. Wagner D.K. An almost linear time algorithm for graph realization // Mathematics of Operations Research. — v. 13. N 1. February 1988. — p. 99- 123.
6. Ротко В.Ф. Эффективные алгоритмы синтеза графов с заданным множеством фундаментальных разрезов или циклов // Кибернетика. — № 1. — 1986. — С. 39-45.
7. Лекции по теории графов /Емеличев 13.А., Мельников О.И . Сарванов В.И., Тышкевич Р.И. — М: Наука, ГРФМЛ, 1990. — 384 с.
8. Робертс Ф.С. Дискретые математические модели с приложениями к социальным, биологическим и экономическим задачам. - М.: Наука. ГРФМЛ. 1986. —496 с.
9. Лефгрен Л. Решение проблем реализуемости неизбыточными булевыми схемами // Кибернет. сб. — № 5. - 1962. — С. 60-101.

Поскольку я еще пишу курсовую работу на эту тему, буду рад обменяться информацией по ней (мой срок сдачи - до мая 2008 года). Пишите в ICQ 399640705 или на extremal.demon@gmail.com. Пока мне и самому нужна помощь с этой задачей - программы еще нет
  #3  
Старый 25.03.2009, 03:04
гость

 
Сообщений: n/a

Н
Нашлась полная версия соответствующей статьи из журнала "Кибернетика", содержащая все что нужно для изучения метода решения, алгоритма, и т.д. Обращайтесь в icq.
  #4  
Старый 12.05.2009, 09:52
гость

 
Сообщений: n/a

Задача, решена)
Тема закрыта
  #5  
Старый 02.04.2010, 13:10
гость

 
Сообщений: n/a

Помогите с курсовой работой, которую мне дал Ротко
  #6  
Старый 02.04.2010, 14:48
гость

 
Сообщений: n/a

а вы собственно кто? что за курсовая?

вы - автор этой тема что ли? тогда почему вам до сих пор неуд не поставили?
 


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Редактор графа на С++ Builder Irensik Реализация, исходники, языки 1 06.04.2008 22:28
связность графа гость Графы 4 24.02.2008 20:35
Преобразование графа. гость Графы 1 13.01.2008 03:30
диаметр графа незарегистрированный Графы 3 06.06.2007 21:33
связывание графа RiV Математические алгоритмы 1 29.01.2007 10:33