ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Ayur Rinchinov                       2:5008/36.4    21 Jun 2001  22:40:33
 To : Sergey Voronin
 Subject : Графы
 -------------------------------------------------------------------------------- 
 

 
 13 Июн 01 13:16, Sergey Voronin написал All:
 
  SV>    Hу неужели никто не может помочь? Пожалуйста, помогите найти
  SV> алгоритм для нахождения толщины графа. Перерыл кучу книг, но так и не
  SV> нашёл ничего. :(
  SV> ------------------------[ начало цитаты ]-------------------------
  SV> Толщина графа(Thickness of a graph)
  SV> - наименьшее число планарных частичных графов (подграфов в слабом
  SV> смысле) графа G, объединение которых дает исходный граф G. Очевидно,
  SV> что толщина планарного графа равна 1.
  SV> ------------------------[ конец цитаты ]--------------------------
 
 думаю в твоем случае надо искать в сторону электронной трассировки (укладка
 планарного графа на плоскость), конкретнее алгоритм "гамма", подробнее в книге
 Емеличева, Абрайтиса.
 
 в общем идея заключается в том, чтобы найти все мосты, если возможно то уложить 
 максимальное количество мостов в одну плоскость, оставшиеся ложить в следующий
 слой "пирога" и.т.д.
 Правда для критерия минимальности видимо надо будет перебрать все возможные
 варианты укладки мостов, может быть кто-то знает более лучший вариант.
  With best wishes, Ayur.                 E-Mail: coda@yandex.ru | ICQ 79144338
 
 ---
  * Origin: Ориджин как ориджин, ничего необычного. (2:5008/36.4)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    Графы   Sergey Voronin   13 Jun 2001 13:16:35   Re: Графы   Yurij Zabelyshynskij   13 Jun 2001 19:50:30   Графы   Maxim Ushakov   14 Jun 2001 11:27:30   Re: Гpафы   Alex Svetlov   24 Jun 2001 01:31:00   Графы   Ayur Rinchinov   21 Jun 2001 22:40:33