И код направления подготовки
жүктеу/скачать 341.63 Kb.
|
- Бұл бет үшін навигация:
- Определение.
- Определение
- Транспортные сети.
- 1. Транспортные сети.
- Комбинаторика. Правила суммы, произведения. Размещения и сочетания
| Гамильтоновы графы
Определение. Гамильтонова цепь (путь, цикл, контур) − простая цепь (путь, цикл, контур), проходящая через все вершины. Определение. Цикл называется гамильтоновым, если он проходит через каждую вершину графа (за исключением крайней) в точности один раз. Определение. Цепь называется гамильтоновой, если она проходит через каждую вершину графа в точности один раз. Замечание. Гамильтонов цикл и гамильтонова цепь всегда являются простыми. Они могут не содержать всех ребер графа. Определение. Граф называется гамильтоновым, если он обладает гамильтоновым циклом. Определение. Граф называется квазигамильтоновым, если он обладает гамильтоновой цепью. Вопросы для закрепления: Что представляет эйлеров граф? Что представляет собой гамильтонов граф? Литература: Основная [1] стр.171- 177, [2] стр. 263-270]; дополнительная [1],[2]; Интернет ресурсы [1]-[4] Тема 12 Транспортные сети. Количество часов 1 Основные вопросы/план темы: Транспортные сети. Поток в транспортной сети. Разрез, пропускная способность разреза. Алгоритм Форда-Фалкерсона построения максимального потока. Тезисы лекции* 1. Транспортные сети. Рассматриваемые здесь сети возникли как математические модели реальных коммуникационных и транспортных сетей. Сеть можно представлять себе как систему, транспортирующую определенный продукт из одной точки в другую и имеющую ограничения на пропускные способности. Такими сетями являются нефте и газопроводы, железнодорожные и автомобильные сети. Математическая модель сети определяется следующим образом. Задан взвешенный ориентированный граф , веса на дугах которого являются целыми положительными числами и называются пропускными способностями дуг. В графе выделены две вершины: , называемая источником, и , называемая стоком. Допустимым потоком из s в t величины F называется заданная на дугах графа неотрицательная функция , удовлетворяющая следующим условиям для всех . Говоря неформально, поток рождается в вершине s и исчезает в вершине t, а во всех остальных вершинах сети количество входящего потока равно количеству выходящего. Кроме того, на каждой дуге поток не превосходит её пропускной способности. Вопросы для закрепления: Что представляет собой транспортные сети? Что такое разрез, пропускная способность разреза? Что представляет собой алгоритм Форда-Фалкерсона построения максимального потока? Литература: Основная [1],[2]; дополнительная [1],[2]; Интернет ресурсы [1]-[4] Тема 13 Комбинаторика. Правила суммы, произведения. Размещения и сочетания Количество часов 1 Основные вопросы/план темы: Задачи комбинаторики, типы выборок. Основные правила комбинаторики (правила суммы, произведения). Формула включений и исключений. Примеры задач на размещения с повторениями, размещения без повторений, перестановки без повторений, перестановки с повторениями, сочетания без повторений, сочетания с повторениями. Тезисы лекции* жүктеу/скачать 341.63 Kb. Достарыңызбен бөлісу:
|