Реферат: Элементы комбинаторики. Правила умножения и сложения

Связный ориентированный граф без циклов называется ориентированным деревом.

Если дерево имеет п вершин, то оно имеет п-1 ребро

Если какую-либо пару несмежных вершин дерева соединить ребром, то полученный граф будет содержать ровно один цикл, и следовательно, уже не будет являться деревом.

Очевидно, что любое ребро дерева является перешейком, после его удаления граф распадается на две компоненты связности.

Остовом или каркасом графа G называется подграф G , содержащий те же вершины, что и G, но не имеющий циклов. Вообще говоря

С - лес, который на любой связной компоненте графа G образует дерево. Если G - связный граф, то остов G является деревом, которое будем называть остовным деревом графа G.

Граф может иметь несколько остовов.

Обратим внимание, что ВСЕ ОСТОВЫ одного графа имеютОДИНАКОВОЕ ЧИСЛО РЁБЕР, НО ИХ ВЕС НИ ЯВЛЯЕТСЯ ВеличинойПОСТОЯННОЙ ДЛЯ ДАННОГО ГРАФА, ЗАВИСИТ ОТ ВЕСОВ ВЫЬРАнНЫХ ребер.

23. Жадный алгоритм.

Требуется проложить сеть телеграфных линий вдоль железнодорожной сети так, чтобы все 6 станций были связаны между собой телеграфной сети и общая протяжённость сети была наименьшей.

Один из эффективных способов решения поставленной задачи —реш ение с помощью алгоритма Краскала или «жадного алгоритма».

Жадный алгоритм:

1. Необходимо упорядочить множество весов
2. выбрать ребро наименьшего веса и инцидентные ему вершины и включит их в остовное дерево.
3. Исключить выбранное ребро из списка рёбер
4. повторяем шаг 2 и3 пока не построим все вершины
5. посчитать все полученного остовного дерева.

24. Алгоритм Прима.

Требуется проложить сеть телеграфных линий вдоль железнодорожной сети так, чтобы все 6 станций были связаны между собой телеграфной сети и общая протяжённость сети была наименьшей.

Один из эффективных способов решения поставленной задачи —решение с помощью алгоритма Краскала или «жадного алгоритма».

Алгоритм Прима или, как его ещё называют, алгоритм ближайшего соседа.

Анализируем матрицу весов. Начинаем с произвольной вершины v_i

Шаг 1. Изучая i-ю строку матрицы весов, выбираем ребро, инцидентное v_i и имеющее наименьший вес. Выбранное ребро ( v_i v_j - первое ребро остова. Удаляем его из матрицы весов.

Шаг 2. Изучая i-ю и .j-ю строки матрицы весов, выбираем ребро минмального веса, инцидентное одной из двух вершин. Присоединяем выбранное ребро к остову и удаляем из матрицы весов.

И так далее. Процесс повторяется до тех пор, пока в остов не будут включены все вершины графа.

25. Алгоритм Дейкстры.

Алгоритм Дейкстры позволяет, решить задачу о нахождении кратчайшего пути в графе.

Особенностью алгоритма Дейкстры является то, что он позволяет найти кратчайшее расстояние от начальной вершины графа до всех остальных, что очень удобно, например, при моделировании сети дорог.

26. Понятие потока в сети.

Примеры сетей и потоков в них: потоки автом транспорта в сети автодорог, поток грузов по железнодорожн сети, поток телегр сообщений в сети связи и т.д. Все эти сети имеют огранич ресурс( поток ограничен сверху).

Ориентир граф называется сетью, если он удовлетвор след условиям:

1. он связный граф без петель
2. существует ровно одна вершина, степень входа которой равна нулю(источник)
3. существует ровно одна вершина, степень выхода которой равна нулю(сток)
4. каждой дуге поставлено в соответствие неотриц число, называемое пропускной способностью

Функция φ, определенная на множестве дуг сети, называется допустимым потоком, если:

для любой дуги e_i выполнено условие 0≤φ≤с(e_i )

т.е. для любой дуги допустимый поток не превышает её пропускной способности.

2. для любой промежуточной величины выполнено условие баланса (условие сохранения потока): сумма потоков, втекающих в вершину, равна сумме вытекающих потоков, т.е. в промежуточных вершинах потоки не создаются и не исчезают.