Главная » Файлы » Методички » Экстремальные задачи [ Добавить материал ]

Экзаменационные вопросы по курсу "Экстремальные задачи на графах" 2010

  1. Ориентированный граф (орграф)

    Начало дуги, конец дуги, понятие инцидентности, смежность дуг и вершин, петля.

    Ориентированный мультиграф, симметричный граф, полный граф.

    Полустепень захода (исхода) вершины, степень вершины, предшественники и потомки вершины, голая и изолированная вершины.

    Вход (выход) графа, путь из вершины A в вершину B, простой путь, s-t путь, достижимость вершины.

    Односторонняя и сильная связность графа, эйлеров путь, гамильтоновый путь, контур (простой, эйлеровый, гамильтоновый), длина пути, контура.

    Неориентированный граф, мультиграф, смежность вершин, инцидентность, степень вершины, цепь, цикл, понятия: простоты, эйлеровости, гамильтоновости, связности.

    Смотреть ответ на первый вопрос

  2. Частичный граф, суграф, подграф.
  3. Дерево, эквивалентные определения.
  4. Расстояние между вершинами в дереве,эксцентриситет,радиус, центральная вершина, центр дерева.
  5. Ориентированное дерево, бинарное дерево, m-арное дерево.
  6. Каркас (остов) графа. Теорема о существовании каркаса.
  7. Полный n-вершинный граф Kn, клика, двудольный граф.
  8. Матрица смежности графа, матрица инцидентности, матрица достижимости.
  9. Способы задания графов.
  10. Алгоритм обхода графа.
  11. Покрывающее дерево графа, компонент графа, разрез, простой разрез.
  12. Алгоритм построения покрывающего дерева. Свойства алгоритма.
  13. Алгоритм построения минимального покрывающего дерева.
  14. Алгоритм поиска кратчайшего пути (Дейкстра).
  15. Алгоритм поиска кратчайшего пути (Форда).
  16. Транспортная задача (классическая постановка).
  17. Эквивалентная сеть транспортной задачи (задача Хитчкока-Купманса).
  18. Ограничения на пропускную способность, модель с промежуточными пунктамо.
  19. Задача выбора кратчайшего пути.
  20. Задача замены оборудования.
  21. Задача планирования капиталовложений.
  22. Задача о назначениях.
  23. Календарное планирование. Пример одевания.
  24. Алгоритм топологической сортировки.
  25. Алгоритм расчета наиболее ранних сроков наступления событий.
  26. Понятие резерва времени (полный резерв, свободный резерв, независимый резерв)
  27. Схема соответствия прямой и двойственной задачи.
  28. Потоковые алгоритмы. Классификация дуг. Максимальная  величина доп. потока.
  29. Задача поиска увеличивающей цепи.
  30. Алгоритм поиска максимального потока.
  31. Понятие разреза. Пропускная способность разреза.
  32. Модификация алгоритма поиска максимального потока (без ограничения на целочисленность потока).
  33. Алгоритм поиска потока максимальной стоимости (Форд-Фалкерсон).
  34. Алгоритм дефекта. Формулировка прямой и двойственной задачи.
  35. Таблица дефектов.
  36. Алгоритм дефекта.
  37. Алгоритм дефекта. Основные условия допустимости решения в прямой и двойственной задаче.
  38. Пример работы алгоритма дефекта.
  39. Геометрическая интерпретация дефектов.
  40. Решение транспортной задачи алгоритмом дефекта.
  41. Решение задачи о назначении алгоритмом дефекта.
  42. Определение максимального потока  алгоритмом дефекта.
  43. Решение задачи о кратчайшей цепи алгоритмом дефекта.
  44. Решение задачи о дереве кратчайших цепей алгоритмом дефекта.
  45. Решение задачи о перевозках алгоритмом дефекта.
  46. Паросочетания и покрытия. Типы задач.
  47. Теорема о связи паросочетание --- покрытие.
  48. Задача почтальона.
  49. Задача почтальона для неориентированного графа (граф четный)
  50. Задача почтальона для неориентированного графа (граф нечетный)
  51. Задача коммивояжера: постановка, пример, теорема об условиях существования решения.
  52. Задача коммивояжера: метод ветвей и границ.
  53. Задачи размещения. Определения и примеры.
  54. Задачи размещения. Центр графа.Алгоритм.
  55. Задачи размещения. Главный центр графа.Алгоритм.
  56. Задачи размещения. Абсолютный центр графа.Алгоритм.
  57. Задачи размещения. Главный абсолютный центр графа.Определение.
  58. Определения для задачи размещения: медиана, гл.медиана, абсол. медиана, гл. абсол. медиана.
Похожие материалы:

Добавил: IGGGORRREKKK (29.05.2010) | Категория: Экстремальные задачи
Просмотров: 3493 | Загрузок: 0 | Рейтинг: 0.0/0 |
Теги: ПОАС, экстремальные задачи, Дворянкин, Граф
Комментарии (1)
0   Спам
1. Sidius   30.05.2010   22:53
Жесть, просто жесть. 64 вопроса о-0. Это ж повернуться можно. Больше даже по физике и матану не было о-0

Имя *:
Email *:
Код *: