matan
2 6. Планарные и плоские графы. Изоморфные графы. Полные графы.
Плоский граф – граф который можно изобразить не плоскости так, что никакие ребра не пересекаются между собой.
Планарный граф – граф изоморфный плоскому пространству.
Г раф называется полным, если любая пара вершин соединена одним ребром. Изоморфизм. Два графа называются изоморфными, если существует перестановка вершин, при которой они совпадают. Иначе говоря, два графа называются изоморфными, если существует взаимно-однозначное соответствие между их вершинами и рёбрами, которое сохраняет смежность и инцидентность (графы отличаются только названиями своих вершин).
Yandex.RTB R-A-252273-3Содержание
- 1.Экономико-математическая модель транспортных задач
- 2.Общая формулировка тз
- 3.Теор. (о ранге сис-мы ограниченной закр. Тз) и следствие из нее. Открытая тз
- 4.Оценка свободной клетки, ее экономический смысл, критерий оптимальности базисного распределения поставок.
- 5.Теорема о потенциалах свободных клеток. Вычисление оценок свободных клеток методом потенциалов.
- 6.Понятие об игровых моделях
- 7.Классификация игр.
- 8.Формальное представление игр
- 10.Фундаментальное неравенство для цен антагонистических игр
- 11.Седловая точка. Теорема о седловой точке
- 12.Понятие смешанной стратегии, чистой стратегии, активной стратегии
- 13.Теорема об активной стратегии. Решение игры 2×2 (формулы)
- 14.Графический метод решения игры 2×2
- 15.Доминирующие стратегии, заведомо невыгодные стратегии, упрощение игр.
- 16.Сведение игры m×n к двойственным задачам лп
- 17.Игры с природой: постановка задачи, матрица рисков.
- 18.Критерий принятия решений в условиях риска (Байеса I и II). Лемма (показатели эффективности и неэффективности стратегии). Теорема об эквивалентности критериев Байеса.
- 19.Критерий принятия решений в условиях неопределенности: критерий Лапласа и Сэвиджа
- 20.Критерий принятия решений в условиях неопределенности: критерий Вальда и Гурвица. Показатель оптимизма.
- 21.Общая постановка задачи динамического программирования (дп). Особенности задачи дп
- 22.Принцип оптимальности и уравнения Беллмана
- 23. Задача о распределении средств между n предприятиями (основные уравнения).
- 25. Понятие маршрута, цепи, простой цепи, цикла для графа. Связные, несвязные графы. Дерево, лес.
- 2 6. Планарные и плоские графы. Изоморфные графы. Полные графы.
- 27. Эйлеровы графы. Крит. Сущ-я эйлерова цикла в графе. Полуэйлеров граф. Задача о Кенигсбергских мостах.
- 28. Гамильтонов граф. Достаточные признаки существования гамильтонова цикла (связь с полнотой цикла, теоремы Оре и Дирака). Полугамильтонов граф.
- 29.Орграфы, турниры. Предки и потомки вершин. Алгоритм Фалкерсона разбиения орграфа на слои.
- 30.Комбинаторная постановка задачи коммивояжера.
- 31. Постан-ка зад. Коммивояжера в виде задачи целочисленного программирования. Условие наличия одного цикла.
- 32. Постановка задачи коммивояжера на языке теории графов.
- 33. Теорема о приведения матрицы расстояний в зк. Оценка маршрута снизу (нижняя граница).
- 34. Ветвление, оценки нулевых переходов, уточнение нижней границы маршрута.
- 35. Метод ближайшего соседа: эвристический алгоритм. Верхняя граница маршрута.