Комбинаторные структуры (размещение, перестановки, сочетания)

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

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

P_n = n × (n - 1) ×...× 1 = n!

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

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

В неупорядоченном наборе порядок перечисления элементов не важен.

=

Перестановка с учетом повторения.

Перестановка с повторением означает, что если существует последовательность с одинаковыми элементами, при их перестановке последовательность не изменится.

= , где n = n ₁ + n ₂ +…+ n_k

Сочетания с учётом повторений.

Сочетанием с повторением из n элементов по k элементам называется всякая последовательность из k элементов:

Бином Ньютона»

(a + b) ⁿ = aⁿ + C_n ¹ a^{n -1} b + C_n ² a^{n -2} b^{n -2} + C_n ³ a^{n -3} b ³ + … + bⁿ .

Компоненты формулы «Бином Ньютона»

· Первая часть формулы – разложение бинома

· -,биномиальные коэффициенты

· Общий член разложения бинома n-й степени.

Где T – член разложения.

(K+1)- порядковый номер разложения.

 

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

Биномиальные коэффициенты

Биномиальным коэффициентом называется количество способов выбрать набор предметов из различных предметов без учёта порядка расположения этих элементов (т.е. количество неупорядоченных наборов).

Также биномиальные коэффициенты - это коффициенты в разложении (т.н. бином Ньютона):

Свойства:

1)

2) Число всех членов разложения на единицу больше показателя степени бинома то есть равно (n+1)

3) Сумма показателей степеней а и b каждого члена разложения равна показателю степени бинома то есть n

4) Биномиальныекоэффициенты членов разложения равноотстоящих от концов разложения, равны между собой «правило симметрии »

5) Сумма биномиальных коэффициентов всех членов разложения равна 2”

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

7) Правило Паскаля

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

9)

Треугольник Паскаля»

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

В верхней строке пишутся две единицы. Все следующиестроки начинаются и оканчиваются единицей. Промежуточные числаполучаются сложением соседних чисел вышестоящей строки.

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

Пример: (a + b) ⁶ =a ⁶ +6a ⁵ b + 15a ⁴ b ² +20a ³ b ³ + 15a ² b ⁴ +6ab ⁵ +b ⁶.

 

39. Ориентированные графы. Динамика графа. Матрицы смежности, инциденций и достижимости.

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

Динамика Графа.

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

Матрица смежности

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента a_ijравно числу рёбер из i-й вершины графа в j-ю вершину.

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

В случае ориентированного графа каждому ребру <x,y> ставится в соответствие "-1" на позиции (x,y) и "1" на позиции (y,x); если связи между вершинами нет, то ставится в соответствие "0".

 

Изоморфизм графов.

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

 

Маршруты, цепи и циклы

Маршрутом в графе G = <V,E; I> называется последовательность вершин и рёбер вида v 0 ,e 1 ,v 1 ,e 2,..., v_n- 1 ,e_n,v_n, где v_i  V, i  [0 ,n ], e_i  E, (v_i- 1 ,e_i), (v_i,e_i)  I, i  [1 ,n ]. Вершины v 0, v_n называются связанными данным маршрутом (или просто связанными). Вершину v 0 называют началом, а v_n – концом маршрута. Если v 0 = v_n, то маршрут называют замкнутым. Число n называется длиной маршрута.

(Цепь, простая цепь, цикл). Маршрут, в котором все рёбра попарно различны, называется цепью. Замкнутый маршрут, являющийся цепью, называется циклом. Маршрут, в котором все вершины попарно различны, называется простой цепью. Цикл, в котором все вершины, кроме первой и последней, попарно различны, называется простым циклом. 

Операции над графами.

Приводятся основные операции над графами такие как объединение, пересечение, кольцевая сумма, удаление вершины, удаление ребра, замыкание и стягивание. Эти операции рассматриваются для представления графов матрицами смежности. Цель лекции: Дать представление об операциях над графами и возможных способах их представления в матричных структурах.

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

Объединение графов G₁ и G₂, обозначаемое как , представляет такой граф , что множество его вершин является объединением Х₁ и Х₂, а множество ребер – объединением A₁ и A₂. Граф G₃, полученный операцией объединения графов G₁ и G₂, показан на рис. 2.1, а его матрица смежности – на рис. 2.1,е. Матрица смежности результирующего графа получается операцией поэлементного логического сложения матриц смежности исходных графов G₁ и G₂.

Рис. 2.1.

Пересечение графов G₁ и G₂, обозначаемое как , представляет собой граф . Таким образом, множество вершин графа G₄ состоит из вершин, присутствующих одновременно в G₁ и G₂. Операция пересечения графов показана на рис. 2.2,в, а результирующая матрица смежности получается операцией поэлементного логического умножения матриц смежности исходных графов G₁ и G₂. показана на рис. 2.2.г.

Рис. 2.2.

Рис.2.2. Операция пересечения и кольцевой суммы: а – граф G₁; б – граф G₂; в – граф ; г – матрица смежности графа ; д – граф ; е – матрица смежности графа

Кольцевая сумма двух графов G₁ и G₂, обозначаемая как , представляет собой граф G₅, порожденный на множестве ребер . Другими словами, граф G₅ не имеет изолированных вершин и состоит только из ребер, присутствующих либо в G₁, либо в G₂, но не в обоих одновременно. Кольцевая сумма графов G₁ и G₂ показана на рис. 2.2,д, причем вершина не входит в граф кольцевой суммы а результирующая матрица смежности получается операцией поэлементного логического сложения по mod 2 матриц смежности исходных графов G₁ и G₂. показана нарис. 2.2.е.

Легко убедиться в том, что три рассмотренные операции коммутативны т. е. , и многоместны, т. е. . и так далее.

 

Удаление вершины. Если х_i -вершина графа G = (X, A), то G–х_i -порожденный подграф графа G на множестве вершин X–х_i, т. е. G–х_i является графом, получившимся после удаления из графа G вершины х_i и всех ребер, инцидентных этой вершине. Удаление вершины х₃ показано на рис. 2.3,б (для исходного графа, изображенного на рис. 2.3,а). Матрица смежности исходного графа представлена на таблице 2.1а). Результирующая матрица смежности графа после выполнения операции удаления вершины х_i получается путем удаления соответствующего i - го столбца и i -ой строки из исходной матрицы и "сжимания" матрицы по вертикали и горизонтали начиная с (i+1) - го столбца и (i+1) -ой строки (таблица 2.1б). В дальнейшем элементы графа могут быть переобозначены.

Рис. 2.3.

Удаление ребра или удаление дуги. Если a_i - дуга графа G = (X, A), то G-a_i – подграф графа G, получающийся после удаления из G дуги a_i. Заметим, что концевые вершины дуги a_i не удаляются. Удаление из графа множества вершин или дуг определяется как последовательное удаление определенных вершин или дуг. Удаление дуг a₄ и a₇ показано на рис. 2.3,в. Результирующая матрица смежности графа после выполнения операции удаления дуги a_i получается путем удаления соответствующих элементов из исходной матрицы (таблица 2.1в).

Таблица 2.1a.   X1 X2 X3 X4 X5 X1           X2           X3           X4           X5	Таблица 2.1б.   X1 X2 X4 X5 X1         X2         X4         X5	Таблица 2.1в.   X1 X2 X3 X4 X5 X1           X2           X3           X4           X5
Таблица 2.1г.   X1-2 X3 X4 X5 X1-2         X3         X4         X5	Таблица 2.1д.   X1-2 X3 X4 X5 X1-2         X3         X4         X5	Таблица 2.1е.   X1-2 X3-4 X5 X1-2       X3       X5

Замыкание или отождествление. Говорят, что пара вершин х_i и x_j в графе G замыкается (или отождествляется), если они заменяются такой новой вершиной, что все дуги в графе G, инцидентные х_i и x_j, становятся инцидентными новой вершине. Например, результат замыкания вершины х₁ и х₂показан на рис. 2.3,г для графа G (рис. 2.3,а). Матрица смежности графа после выполнения операции замыкания вершин х_i и x_j получается путем поэлементного логического сложения i - го и j - го столбцов и i -ой и j - строк в исходной матрице и "сжимания" матрицы по вертикали и горизонтали (таблица 2.1г).

Стягивание. Под стягиванием подразумевают операцию удаления дуги или ребра и отождествление его концевых вершин. Граф, изображенный на рис. 2.3,д получен стягиванием дуги a₁, а на рис. 2.3,е – стягиванием дуг a₁, a₆ и a₇. Соответствующие результирующие матрицы смежности показаны в таблицах 2.1д и 2.1е.

Деревья

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

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

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

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

На рисунке приведены диаграммы всех неизоморфных ориентированных деревьев с тремя и четырьмя вершинами.

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

Расстояние от корня до некоторой вершины называется уровнем вершины. Сам корень имеет уровень 0. Вершины одного уровня образуют ярус дерева.

Замечание. При изображении ориентированных деревьев принято помещать корень наверху и все стрелки дуг ориентировать сверху вниз, что избавляет от необходимости изображать эти стреДеревья ориентированные

На рисунке показано дерево, изображенное в соответствии с указанными выше правилами Вершины дерева разбиты на 4 яруса.

Нулевой ярус содержит корень дерева х, В первом ярусе 3 вершины, во втором ярусе 5 вершин, в третьем ярусе-6 вершин

Деревья бинарные и сбалансированные

Бинарным деревом называется ориентированное дерево, из каждой вершины которого выходит не более двух дуг.

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

Сбалансированные деревья иногда называют АВЛ деревьями, в соответствии с именами их первооткрывателей, советских математиков: Адельсона-Вельского и Ландиса, которые предложили в 1962 году данное определение.

Разрезы

Пусть G(V,U) –неориентированный граф.

Разрезом называется всякое множество R ребер графа G, что удаление этих ребер из графа делает его несвязным.

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

 

Потоковые модели.

Социометрические модели.