Автор: Кошка 12.12.2006 0:04
Помогите, пожалуйста, написать программы на Паскале (или на Делфи), решающие задачи:
1)"Построить (если возможно) 1-фактор в двудольном графе." (1- фактор- это паросочетание, покрывающее все вершины графа);
2)"Найти расстояния и построить кратчайший путь во взвешенном орграфе от одной заданной вершины до другой."
Автор: Altair 12.12.2006 19:10
Цитата
"Найти расстояния и построить кратчайший путь во взвешенном орграфе от одной заданной вершины до другой."
Однозначно, алгоритм http://forum.pascal.net.ru/index.php?s=&showtopic=4030&view=findpost&p=42335 наиболее подходящий для данной задачи.
Цитата
Построить (если возможно) 1-фактор в двудольном графе."
Определение: совершенное паросочетание (1-фактор) - паросочетание, покрывающее все вершины графа.
Насколько я знаю, тебе необходим http://litevv.narod.ru/lekcii/diskret/14.html