§1.2. Формулы пересчета числа комбинаторных конфигураций.

1. Число (n,k)-размещений без повторений может быть определено с помощью правила произведения. Первый из k элементов размещения может быть выбран n способами, второй - способами, поскольку элемент, выбранный первым, не должен быть повторен; аналогично, для третьего (если k > 2) элемента остается (n - 2) способов и т.д. Всего k элементов могут быть выбраны А„ =n-(n-1)-...-(n-k + 1) способами: произведение k убывающих на 1 сомножителей, начиная с n. По-другому, используя обозначение можно записать:

2 . Числа (n,k) -сочетаний без повторений обозначаются символами и называются также биномиальными коэффициентами

Приведем некоторые свойства биномиальных коэффициентов.

1)

2)

3)

4)

5)

6) (тождество Коши).

§1.3. Перечисление перестановок

Рассмотрим некоторые алгоритмы порождения (перечисления) последовательности всех перестановок п элементов.

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

1, (все перестановки из {2,..., n} в алфавитном порядке)

2, (все перестановки из {1, 3,..., n} в алфавитном порядке) .

3, (все перестановки из (1, 2, 4,..., n} в алфавитном порядке)

n, (все перестановки из (1, 2,,.,, n -1} в алфавитном порядке).

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

в) Частным случаем предыдущего можно считать последовательность, в которой разница между двумя соседними перестановками еще меньше: они различаются транспозицией двух соседних элементов.

§1.4. Приложения к теории вероятностей и теоретической физике.

Припишем исходу х. некоторое число где - действительное число, _{этому числу} будем придавать вероятностный смысл и равно вероятности появления этого исхода. Будем считать, что все элементы равновероятны могут

_{Если при этом мы считаем за сопутствующее нашему опыту m, то вероятность этого будет} .

Глава 2. Графы и сети

§2.1. Ориентированные и неориентированные графы. Способы задания графов.

1. Граф - это система некоторых объектов вместе с некоторыми парами этих объектов, изображающая отношения связи между ними. Неориентированный граф (соответственно ориентированный граф, или орграф) G - система G = (V, E, Г), состоящая из множества элементов V= {v}, называемых вершинами графа, множества элементов Е = {е}, называемых ребрами, и отображения , ставящего в соответствие каждому элементу неупорядоченную (соответственно упорядоченную) пару элементов называемых концами ребра е.

Для неориентированного графа значение V₁ и V₂ может быть произвольным. Для ориентированного – V₁ - начало пути, V₂ - конец.

образует множество элементов графа; при этом предполагается, что

Отображение Г определяет отношение инцидентности ребра с каждым из своих концов. Для графа G = (V, Е, Г) употребляется также более короткое обозначение G = (V, Е) без указания инцидентностей, которые определяются контекстом.

Если - упорядоченная пара при v₁ - v₂), то ребро е называется ориентированной дугой, исходящей из вершины v₁ и входящей в вершину ; называется началом, а концом дуги е. Если – неупорядоченная пара, то ребро е называется неориентированным.

Всякому графу G можно поставить в соответствие соотнесенный неориентированный граф с теми же множествами V и Е и инцидентностями, но все пары неупорядоченные.

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

Ребро с совпадающими концами называется петлей.

Две вершины, инцидентные одному и тому же ребру, называются соседними (или смежными). Два ребра, инцидентные одной и той же вершине, называются смежными.

Ребра, которым поставлена в соответствие одна и та же пара вершин, называются кратными, или параллельными.

2 . Графы могут различаться и не различаться. Обычно это связывают с понятием изоморфизма графов.

Два графа называются изоморфными, если существуют взаимно однозначные отображения сохраняющие инцидентность, т.е. е Є E₁

3. Существует несколько способов задания графов:

1) Перечисление (список) ребер графа с указанием их концов и добавлением списка изолированных вершин.

2 ) Матрица инциденций графа с b вершинами и p ребрами - прямоугольная матрица с b строками и p столбцами, строки которой соответствуют вершинам графа, а столбцы - ребрам, причем j для неориентированного графа элемент матрицы равен 1, если вершина и ребро инцидентны, и равен 0 в противном случае. Для ориентированного графа если является началом дуги = +1, если v. - конец дуги В каждом столбце матрицы инциденций -два ненулевых элемента, если ребро - не петля. Петле соответствует элемент, равный 2.

3) Матрица соседства (смежности) вершин графа с b вершинами - квадратная матрица размерности Ь, строки и столбцы которой соответствуют вершинам графа, причем неотрицательный элемент равен числу ребер, идущих из вершины в вершину ( не равно, вообще говоря, , однако для неориентированных графов матрица соседства - симметричная). Для несмежных вершин соответствующий элемент матрицы равен 0.

4) Для наглядности граф часто представляют в виде геометрического объекта: вершинам соответствуют различные выделенные точки в пространстве (на плоскости), ребрам - отрезки кривых, связывающие соответствующие точки и не проходящие через выделенные точки, отличные от их концов.

5. Граф называется подграфом графа обозначение: если и для множеств сохраняются инциденции графа G. При этом, очевидно, каждое ребро из Е' входит в подграф Н вместе со своими концами.

Обычно рассматриваются только подграфы без изолированных вершин или только подграфы, содержащие все вершины графа (и только часть ребер); такие подграфы полностью определяются множеством своих ребер. В этих случаях можно естественным образом определить теоретико-множественные операции над подграфами: пересечение, объединение, симметрическую разность (называемую также суммой по модулю 2 или просто суммой), дополнение до всего графа.

Подграфом, натянутым на множество вершин графа

G, называется подграф, содержащий вершины из V и все ребра графа G, соединяющие пары вершин из

Подграф , состоящий из всех ребер, инцидентных вершине называется звездой вершины

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