|
ru.algorithms
- RU.ALGORITHMS ----------------------------------------------------------------
From : Dmitry V. Liseev 2:5020/400 27 Mar 2002 21:32:45
To : All
Subject : Максимально возможное кол-во путей в графе
--------------------------------------------------------------------------------
Hi,All!
Hужно обрабатывать громадные графы в базе данных.
Соответственно возникают задачки оценки затрат
процессорного времени, оперативной и дисковой
памяти сервера для разных алгоритмов.
Задача (оценка сверху):
Дано множество вершин M.
а) Hадо предложить способ соединить их ребрами
в ориентированный граф без образования контуров,
чтобы получилось максимально возможное число путей.
б) Hайти зависимость максимально возможного
числа путей в ориентированном графе без контуров
от числа вершин. Есть надежда, что это порядка M^3.
Пример для маленьких графов:
для 2 вершин - 1 путь
для 3 вершин - 4 пути (3 пути из одного ребра + 1 путь из 2 ребер)
для 4 вершин - 11 путей (6 путей из одного ребра +
4 пути из двух ребер + 1 путь из 3 ребер)
____________________________
С уважением, Лисеев Дмитрий.
http://private.peterlink.ru/dimik/
PGP key fingerprint: 09 28 74 28 6C 39 62 29 2E CB 95 03 4F 04 33 73
--- ifmail v.2.15dev5
* Origin: Peterlink News System (2:5020/400)
Вернуться к списку тем, сортированных по: возрастание даты уменьшение даты тема автор
|
