- Ориентированный граф (орграф)
Начало дуги, конец дуги, понятие инцидентности, смежность дуг и вершин, петля.
Ориентированный мультиграф, симметричный граф, полный граф.
Полустепень захода (исхода) вершины, степень вершины, предшественники и потомки вершины, голая и изолированная вершины.
Вход (выход) графа, путь из вершины A в вершину B, простой путь, s-t путь, достижимость вершины.
Односторонняя и сильная связность графа, эйлеров путь, гамильтоновый путь, контур (простой, эйлеровый, гамильтоновый), длина пути, контура.
Неориентированный граф, мультиграф, смежность вершин, инцидентность, степень вершины, цепь, цикл, понятия: простоты, эйлеровости, гамильтоновости, связности.
Смотреть ответ на первый вопрос
- Частичный граф, суграф, подграф.
- Дерево, эквивалентные определения.
- Расстояние между вершинами в дереве,эксцентриситет,радиус, центральная вершина, центр дерева.
- Ориентированное дерево, бинарное дерево, m-арное дерево.
- Каркас (остов) графа. Теорема о существовании каркаса.
- Полный n-вершинный граф Kn, клика, двудольный граф.
- Матрица смежности графа, матрица инцидентности, матрица достижимости.
- Способы задания графов.
- Алгоритм обхода графа.
- Покрывающее дерево графа, компонент графа, разрез, простой разрез.
- Алгоритм построения покрывающего дерева. Свойства алгоритма.
- Алгоритм построения минимального покрывающего дерева.
- Алгоритм поиска кратчайшего пути (Дейкстра).
- Алгоритм поиска кратчайшего пути (Форда).
- Транспортная задача (классическая постановка).
- Эквивалентная сеть транспортной задачи (задача Хитчкока-Купманса).
- Ограничения на пропускную способность, модель с промежуточными пунктамо.
- Задача выбора кратчайшего пути.
- Задача замены оборудования.
- Задача планирования капиталовложений.
- Задача о назначениях.
- Календарное планирование. Пример одевания.
- Алгоритм топологической сортировки.
- Алгоритм расчета наиболее ранних сроков наступления событий.
- Понятие резерва времени (полный резерв, свободный резерв, независимый резерв)
- Схема соответствия прямой и двойственной задачи.
- Потоковые алгоритмы. Классификация дуг. Максимальная величина доп. потока.
- Задача поиска увеличивающей цепи.
- Алгоритм поиска максимального потока.
- Понятие разреза. Пропускная способность разреза.
- Модификация алгоритма поиска максимального потока (без ограничения на целочисленность потока).
- Алгоритм поиска потока максимальной стоимости (Форд-Фалкерсон).
- Алгоритм дефекта. Формулировка прямой и двойственной задачи.
- Таблица дефектов.
- Алгоритм дефекта.
- Алгоритм дефекта. Основные условия допустимости решения в прямой и двойственной задаче.
- Пример работы алгоритма дефекта.
- Геометрическая интерпретация дефектов.
- Решение транспортной задачи алгоритмом дефекта.
- Решение задачи о назначении алгоритмом дефекта.
- Определение максимального потока алгоритмом дефекта.
- Решение задачи о кратчайшей цепи алгоритмом дефекта.
- Решение задачи о дереве кратчайших цепей алгоритмом дефекта.
- Решение задачи о перевозках алгоритмом дефекта.
- Паросочетания и покрытия. Типы задач.
- Теорема о связи паросочетание --- покрытие.
- Задача почтальона.
- Задача почтальона для неориентированного графа (граф четный)
- Задача почтальона для неориентированного графа (граф нечетный)
- Задача коммивояжера: постановка, пример, теорема об условиях существования решения.
- Задача коммивояжера: метод ветвей и границ.
- Задачи размещения. Определения и примеры.
- Задачи размещения. Центр графа.Алгоритм.
- Задачи размещения. Главный центр графа.Алгоритм.
- Задачи размещения. Абсолютный центр графа.Алгоритм.
- Задачи размещения. Главный абсолютный центр графа.Определение.
- Определения для задачи размещения: медиана, гл.медиана, абсол. медиана, гл. абсол. медиана.
Добавил: IGGGORRREKKK (29.05.2010) | Категория: Экстремальные задачи
Просмотров: 5573 | Загрузок: 0
| Рейтинг: 0.0/0 |
Теги: |
Жесть, просто жесть. 64 вопроса о-0. Это ж повернуться можно. Больше даже по физике и матану не было о-0