кто-нибудь шарит в k-связных графах и около?

KuKat32

а именно хотелось бы в идеале для данных n, k, l строить ориентированный граф с n вершинами, такой что для любых вершин существовал бы связывающий их путь длины не больше l (такая ужесточенная сильная связность) и при удалении произвольных k вершин граф оставался бы сильно связным, ну и при этом минимальный по числу ребер (а то можно просто все со всем соединить) — о как
может кто-нибудь литературу подскажет?

KuKat32

апнем разок
где дискретчики-графоманы? можно высказываться не только про литературу

griz_a

Задача не вполне понятна, что именно нужно делать с графом? Аналитически построить минимальный граф с этими свойствами для каждого n,l,k или алгоритмически?

KuKat32

для начала — хоть как-нибудь
можно и условия ослабить

Xephon

Аналитически построить минимальный граф

А что значит "аналитически построить граф"?

griz_a

Типа берем граф с такими-то ребрами.
А можно. Берем полный граф и выкидываем ребра, пока не....

seregaohota

Как условия на граф проверять? Перебором? Вылезет проклятье факториала, за разумное время при больших n не переберёшь. Вряд ли n>15 посчитаешь.
Книги по теории графов читай. Оре вспоминается. Ещё есть Липский "Комбинаторика для программистов", там по графам есть алгоритмы.

griz_a

Почему перебором. Гипотетически нужно строить граф, такой что у него эти условия будут выполняться и уменьшать его. Если бы я знал как конкретно, то уже бы написал. Пока я понимаю задачу.
Оставить комментарий
Имя или ник:
Комментарий: