Элементы Комбинаторики
Реферат, 26 Марта 2014, автор: пользователь скрыл имя
Краткое описание
Комбинаторика
раздел математики, в котором изучаются задачи выбора элементов из заданного множества и расположения их в группы по заданным правилам, в частности задачи о подсчете числа комбинаций (выборок), получаемых их элементов заданного множества. В каждой из них требуется подсчитать число возможных вариантов осуществления некоторого действия, ответить на вопрос: «Сколькими способами?» Многие комбинаторные задачи могут быть решены с помощью следующих 2х важных правил, называемых соответственно правилами умножения и сложения.
Прикрепленные файлы: 1 файл
Реферат по математике.docx
— 106.78 Кб (Скачать документ)Шаг 2. Изучая i-ю и .j-ю строки матрицы весов,
выбираем ребро минмального веса, инцидентное
одной из двух вершин. Присоединяем выбранное
ребро к остову и удаляем из матрицы весов.
И так далее. Процесс повторяется до тех
пор, пока в остов не будут включены все
вершины графа.
Алгоритм
Дейкстры
Алгоритм Дейкстры позволяет, решить задачу
о нахождении кратчайшего пути в графе.
Особенностью алгоритма Дейкстры является
то, что он позволяет найти кратчайшее
расстояние от начальной вершины графа
до всех остальных, что очень удобно, например,
при моделировании сети дорог.
Понятие
потока в сети
Примеры сетей и потоков в них: потоки
автомобильного транспорта в сети автодорог,
поток грузов по железнодорожной сети,
поток телегр сообщений в сети связи и
т.д. Все эти сети имеют огранич ресурс(
поток ограничен сверху).
Ориентир граф называется сетью, если
он удовлетвор. след условиям:
он связный граф без петель
существует ровно одна вершина, степень входа которой равна нулю(источник)
существует ровно одна вершина, степень выхода которой равна нулю(сток)
каждой дуге поставлено в соответствие неотриц. число, называемое пропускной способностью
Функция φ, определенная на множестве
дуг сети, называется допустимым потоком,
если:
для любой дуги ei выполнено условие 0≤φ≤с(ei)
т.е. для любой дуги допустимый поток
не превышает её пропускной способности.
2. для любой промежуточной величины выполнено
условие баланса (условие сохранения потока):
сумма потоков, втекающих в вершину, равна
сумме вытекающих потоков, т.е. в промежуточных
вершинах потоки не создаются и не исчезают.
Величина
называется остаточной пропускной
способностью дуги.
Дуга ei называется насыщенной, если
(если допустимый поток равен пропускной
способностью)
Суммарный поток, вытекающий из источника,
равен суммарному потоку, втекающему в
сток. Этот поток будем называть потоком
в сети.
Полный
и максимальный потоки в сети
Поток называется полным, если путь из источника
в сток содержит хотя бы одну насыщенную
дугу.
Поток называется максимальным, если он
принимает максимальное значение по сравнению
с остальными потоками в сети.