26. Лес. Дерево. Остовное дерево. Цикломатическое число графа. Нахождение минимального остовного дерева. Алгоритм Прима.

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

Таким образом дерево характеризуется тремя свойствами:

-неориентированность

-связанность

-отсутствие циклов.

Видимо, деревья это самый важный для приложений вид графов. На них базируются многие алгоритмы для приложений вид графов. На них базируются многие алгоритмы сортировки и поиска базы данных и др.

Вершины дерева степени 1(висящие вершины) называются листьями.

Свойства дерева.

1. Всякие две вершины дерева можно соединять единственной цепью.

2. Если в дереве не менее двух вершин, то у него не менее двух листов.

Остовное дерево — это подграф данного графа, содержащий все его вершины и являющийся деревом. Рёбра графа, не входящие в остов, называются хордами графа относительно остова.

Цикломатическое число указывает на число независимых циклов в графе, например в графе, изображающем молекулу СОХ, оно равно двум, в графе на рис. 6г оно равно трем, указывая на три конечных грани или три независимых цикла. Независимыми являются циклы, которые на данной графе не могут быть образованы линейной комбинацией других циклов. [1]

Цикломатическое число я является разностью числа ветвей связного графа и числа ветвей его дерева. [2]

Цикломатическим числом K ( G) графа G называется величина X ( G) m ( G) - n ( G) x ( G), где п - число вершин, m - число ребер, к - число компонент связности. [3]

Вычисление цикломатического числа осуществляется по переменным, определяемым по максимально связному графу, который получается из исходного графа замыканием дуги из конечной вершины в начальную. [4]

Минимальное остовное дерево (или минимальное покрывающее дерево).Дан взвешенный неориентированный граф с n вершинами и m рёбрами. Требуется найти такое поддерево этого графа, которое бы соединяло все его вершины, и при этом обладало наименьшим возможным весом (т.е. суммой весов рёбер). Поддерево — это набор рёбер, соединяющих все вершины, причём из любой вершины можно добраться до любой другой ровно одним простым путём.

Такое поддерево называется минимальным остовным деревом или просто минимальным остовом. Легко понять, что любой остов обязательно будет содержать n-1 ребро.

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

Алгоритм Прима.Описание алгоритма

Сам алгоритм имеет очень простой вид. Искомый минимальный остов строится постепенно, добавлением в него рёбер по одному. Изначально остов полагается состоящим из единственной вершины (её можно выбрать произвольно). Затем выбирается ребро минимального веса, исходящее из этой вершины, и добавляется в минимальный остов. После этого остов содержит уже две вершины, и теперь ищется и добавляется ребро минимального веса, имеющее один конец в одной из двух выбранных вершин, а другой — наоборот, во всех остальных, кроме этих двух. И так далее, т.е. всякий раз ищется минимальное по весу ребро, один конец которого — уже взятая в остов вершина, а другой конец — ещё не взятая, и это ребро добавляется в остов (если таких рёбер несколько, можно взять любое). Этот процесс повторяется до тех пор, пока остов не станет содержать все вершины (или, что то же самое, n-1ребро).

В итоге будет построен остов, являющийся минимальным. Если граф был изначально не связен, то остов найден не будет (количество выбранных рёбер останется меньше n-1).

27. Основной принцип комбинаторики. Перестановки. Размещения с повторениями. Размещения без повторений. Сочетания без повторений. Биномиальные коэффициенты и их свойства. Сочетания с повторениями. Примеры.

Основной принцип комбинаторики заключается в следующем: если первый

элемент можно выбрать k способами, а второй элемент m способами, то упоря-

доченную пару элементов можно составить km способами.

Сочетания без повторений — комбинаторныесоединения из n элементов по m, составленные из этих элементов и отличающиеся друг от друга только составом.

 

формула для нахождения количества сочетаний без повторений:

 

Сочетания с повторениями — комбинаторныесоединения из n элементов по m, составленные из этих элементов без учета порядка с возможностью многократного повторения предметов.

формула для нахождения количества сочетаний с повторениями: С^k_n=C^k_n+k-1

Пример. Возьмем буквы Б, А, Р. Какие сочетания из этих букв, взятых по две, можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) можно брать по два одинаковые буквы.

Решение.

1. Получатся наборы: БА (БА и АБ - один и тот же набор), АР и РБ

По формуле получаем:  наборов. 

2. Получатся наборы: ББ, БА, БР, АА, АР, РР.

По формуле получаем:  наборов.

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

Пример. Возьмем буквы Б, А, Р. Какие перестановки из этих букв можно получить? Сколько таких наборов получится, если: 1) буквы в наборе не повторяются; 2) буква А повторяется два раза?

Решение.

1. Получатся наборы: БАР, БРА, АРБ, АБР, РАБ, РБА.

По формуле) получаем:   наборов. 

2. Получатся наборы: БАРА, БРАА, БААР, ААРБ, ААБР, АБАР, АРАБ, АРБА, АБРА, РАБА, РААБ, РБАА.

По формуле получаем:   наборов.

Размещения без повторений — комбинаторные соединения, составленные из n элементов по m.  При этом два соединения считаются различными, если они либо отличаются друг от друга хотя бы одним элементом, либо состоят из одних и тех же элементов, но расположенных в разном порядке.

 

формула для нахождения количества размещений  без повторений:

Размещения с повторениями — комбинаторные соединения, составленные из n элементов по m. При этом  каждый из n элементов может содержаться сколько угодно раз или вообще отсутствовать.

 

формула для нахождения количества размещений  с повторениями:

Пример. Возьмем буквы Б, А, Р. Какие размещения из этих букв, взятых по две, можно получить? Сколько таких наборов получиться, если: 1) буквы в наборе не повторяются; 2) буквы могут повторяться?

Решение.

1. Получатся следующие наборы: БА, БР, АР, АБ, РБ, РА.

По формуле получаем:   наборов. 

2. Получатся наборы: ББ, БА, БР, АА, АБ, АР, РР, РБ, РА.

По формуле получаем:   наборов.

Биномиальные коэффициенты и их свойства. Коэффициентом первого члена разложения бинома есть 1 (или  ), второго -  , третьего -  и т.д. Коэффициент последнего, (m + 1)-го члена равен  . Эти коэффициенты называются биномиальными.

Биномиальные коэффициенты имеют следующие свойства:

1) Коэффициенты членов, одинаково удаленных от концов разложения, равны между собой, т.е.

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

3) Сумма всех биномиальных коэффициентов равна 2^m, т.е.

4) Сумма биномиальных коэффициентов, стоящих на нечетных местах, равна сумме биномиальных коэффициентов, стоящих на четных местах, т.е.