|
Denisska |
|
|
|
Прошу подсказать к какому разделу теории графов относится данная тема.
Почему то не могу найти, смотрел в Емеличев И.Ф. "Лекции по теории графов". Возможно есть другое название?
|
|
|
|
 |
|
gris |
|
|
|
Экстремальные сети. Экстремальные задачи на графах.
Обычно экстремальным графом называют минимальный связный плюс максимальный без циклов на заданном множестве вершин.
Погуглите. Вот навскидку:
Экстремальные задачи на графах.
Задача о минимальном остове (кратчайшей связывающей сети). Алгоритмы Краскала и Прима. Динамическая задача о кратчайшем пути. Алгоритм Дейкстры. Прямо-двойственный метод. Алгоритм Дейкстры с позиций прямо-двойственного метода.
Задача о назначениях: условия оптимальности, описание алгоритма. Алгоритм решения задачи о назначениях с позиций прямо-двойственного метода.
Задача нахождения паросочетания максимального веса. Теорема Бержа. Подход к решению задачи, основанный на теории двойственности, формулировка вспомогательной задачи, описание алгоритма ее решения и доказательство его конечности.
Упрощения в алгоритме в случае единичных весов ребер.
Задачи китайского почтальона и покрытия графа ребрами; их сводимость к задаче отыскания паросочетания максимального веса.
Где-нибудь и рекомендованная литература есть.
|
|
|
|
|
|
Denisska |
|
|
|
Большое спасибо.
Данные темы мне встречались.
И все же еще вопрос. Мне необходимо подготовить конспект по данной теме. Что следует включить в конспект? Будет ли правильно, если я по теме "Части графов с экстремальными свойствами" подготовлюсь по приведенным выше темам?
|
|
|
|
|
