16. Понятие композиции. Теорема о числе композиций n.

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

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

При фиксированной длине композиций в них иногда также допускают нулевые части.

В общем случае существует   композиций числа n, из которых в точности   имеют длину k. Для доказательства этого утверждения достаточно построить биекцию между композициями n длины k и  -элементными подмножествами  -элементного множества. Поставим в соответствие композиции   подмножество множества  , состоящее из частичных сумм:  . Очевидно, у этого соответствия есть обратное: по подмножеству  , элементы которого упорядочены по возрастанию, можно восстановить исходную композицию:

,   при   и, наконец,  .

Таким образом, построенное отображение биективно, и поэтому количество композиций числа n длины k равно количеству  -элементных подмножеств  -элементного множества, то есть биномиальному коэффициенту  . Для подсчета общего числа композиций числа n достаточно или просуммировать эти биномиальные коэффициенты, или использовать то же отображение для построения биекции между всеми композициями числа n и всеми подмножествами  -элементного множества.

Если в композициях числа n длины k разрешить нулевые части, то количество таких композиций будет равно  , поскольку прибавление 1 к каждой части даёт композицию числа n + k уже без нулевых частей. Вопрос об общем количестве композиций числа n с возможными нулевыми частями лишён смысла, так как оно бесконечно.

17. Понятие композиции. Теорема о числе композиций n из k частей при рi>0.

18. Понятие композиции. Теорема о числе композиций n из k частей при рi0.

19. Основные понятия и определения теории графов.

Возьмем два множества: V- множество точек(не пустое), E- множество линий (может быть пустое). Возьмем элемент e из множества E. Если существует пара элементов u,vV, что эти элементы являются концами линии е, то говорят, что элемент е инцидентен элементам u и v, и наоборот, элементы u и v инцидентные. Графом (G,G(u,v),V E) называется совокупность множеств V и E между элементами которых определено отношение инцидентности, причем для каждого элемента еÎЕ найдется пара элементов из множества V, что e инцидентно этим элементам. Обратное вообще говоря неверно: элементы V не инцидентны никаким элементам из множества Е.??? Элементы множества V называются вершинами графа, элементы множества Е- ребрами графа. Вершина, не инцидентная ни одному ребру, называется изолированной. Граф, состоящий только из изолированных вершин, называется нуль-графом. Вершины, инцидентные одному ребру, называются смежными. Два ребра, инцидентные одной вершине, называются смежными. Если вершина инцидентна только одному ребру, то она называется висячей. Если вершина инцидентна только двум ребрам, то она называется транзитивной. Если граф содержит петли, то он называется псевдографом. Если граф содержит кратные ребра, то его называют мультиграф. Если не никаких оговорок, то, говоря о графе, будем полагать, что он не содержит ни петель, ни кратных ребер. В некоторых случаях рассматриваются графы, вершины которого неравноправны, т.е. рассматриваются в определенном порядке, тогда ребру приписывается направление от начальной вершины к конечной. Направленное ребро называется дугой графа. Граф, содержащий только дуги, называется ориентированным графом, или ор-графом. Если граф содержит дуги и ребра, то он называется смешанным. Для неориентированных. графов (u,v)=(v,u), для ор-графов (u,v)≠(v,u).

20. Способы хранения графов в памяти ЭВМ.

Результатом проектирования структуры является комплекс графов следования, соответствующих структуре процесса, структуре операций и структуре переходов. Этот комплекс необходимо каким-то образом хранить в памяти ЭВМ. Будем различать следующие основные способы хранения графов следования в памяти ЭВМ:

1. В виде матрицы смежности.

2. В гнездовом виде.

3. В виде списка дуг.

4. В виде списка вершин.

5. В линейном виде.

21. Алгоритм поиска на графах (поиск в глубину).

Поиск в глубину (англ. Depth-first search, DFS) — один из методов обхода графа. Алгоритм поиска описывается следующим образом: для каждой непройденной вершины необходимо найти все не пройденные смежные вершины и повторить поиск для них. Используется в качестве подпрограммы в алгоритмах поиска одно- и двусвязных компонент, топологической сортировки.

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

1. Из множества всех белых вершин выберем любую вершину, обозначим её  .

2. Выполняем для неё процедуру DFS( ).

3. Повторяем шаги 1-3 до тех пор, пока множество белых вершин не пусто.

Процедура DFS (параметр — вершина  )

1. Перекрашиваем вершину   в черный цвет.

2. Для всякой вершины  , смежной с вершиной u и окрашенной в белый цвет, выполняем процедуру DFS(w).

22. Алгоритм поиска на графах (поиск в ширину).

Поиск в ширину (BFS, Breadth-first search) — метод обхода и разметки вершин графа.

Поиск в ширину выполняется в следующем порядке: началу обхода s приписывается метка 0, смежным с ней вершинам — метка 1. Затем поочередно рассматривается окружение всех вершин с метками 1, и каждой из входящих в эти окружения вершин приписываем метку 2 и т. д.

Если исходный граф связный, то поиск в ширину пометит все его вершины. Дуги вида (i, i+1) порождают остовный бесконтурный орграф, содержащий в качестве своей части остовное ордерево, называемое поисковым деревом.

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