- •Введение
- •1. Элементы теории множеств
- •1.1. Основные понятия и определения теории множеств
- •1.2. Операции над множествами и их свойства. Диаграммы Эйлера-Венна
- •1.3. Мощность множества
- •1.4. Взаимно однозначное соответствие между множествами
- •1.5. Счетные и несчетные множества
- •Задачи и упражнения
- •2. Элементы теории отношений
- •2.1. Бинарные отношения. Свойства отношений
- •2.2. Отношение эквивалентности и разбиения
- •2.3. Отношения порядка. Диаграмма Хассе
- •Задачи и упражнения
- •3.Функции, отображения и операции
- •4. Элементы теории графов
- •4.1. Основные понятия и определения теории графов
- •4.2. Типы графов
- •4.3. Матричные представления графов
- •4.5. Операции над графами
- •4.6. Метрические характеристики графа. Расстояние в графах
- •Затем, изымая степень, соответствующую вершине , получим
- •4.8. Достижимость и связность
- •4.8.1. Основные определения
- •4.8.2. Матрицы достижимостей
- •4.8.3. Нахождение сильных компонент
- •Алгоритм нахождения сильных компонент графа можно описать следующей последовательностью шагов
- •Таким образом, сильные компоненты графа можно находить по следующему алгоритму.
- •4.8.4. Базы и антибазы
- •4.9. Независимые и доминирующие множества
- •4.9.1. Нахождение всех максимальных независимых множеств
- •Опишем алгоритм нахождения всех максимальных независимых множеств вершин графа.
- •4.10. Покрытия и раскраски
- •4.11. Деревья, остовы и кодеревья
- •4.11.1. Основные определения
- •4.11.2. Алгоритм построения остова неорграфа
- •4.11.4. Обходы графа по глубине и ширине
- •Доказательство.
- •4.11.5. Упорядоченные и бинарные деревья
- •4.12. Эйлеровы циклы. Гамильтонов контур
- •4.12.1. Метод Флёри построения эйлерова цикла
- •Матрица м данного графа имеет вид
- •4.12.3. Алгебраический метод выделения гамильтоновых путей и контуров
- •4.13. Плоские и планарные графы
- •4.13.1. Формула Эйлера
- •4.13.2. Критерии анализа планарности
- •4.13.3. Алгоритм укладки графа на плоскости
- •Задачи и упражнения
- •5. Комбинаторика
- •5.1. Перестановки
- •5.2. Перестановки с неограниченными повторениями
- •5.3. Размещения
- •5.4. Сочетания
- •5.5. Сочетания с повторениями
- •5.6. Производящие функции для сочетаний
- •5.7. Производящие функции для перестановок
- •5.8. Циклы перестановок
- •Общее число дубликатов
- •5.9. Принцип включений и исключений
- •Почему появился ?
- •Задачи и упражнения
- •6. Алгебра высказываний
- •6.1. Операции над высказываниями
- •6.2. Правила записи сложных формул
- •6.3. Таблицы истинности
- •6.4. Равносильность формул
- •6.5. Дизъюнктивные и конъюнктивные нормальные формы
- •6.5.1. Алгоритм приведения пф к нормальным формам
- •6.5.2. Аналитический способ приведения к сднф
- •6.5.3. Табличный способ приведения к сднф
- •6.5.4. Табличный способ приведения к скнф
- •6.6. Логическое следствие
- •Задачи и упражнения
- •7. Разрешимые и неразрешимые проблемы
- •Заключение
- •Библиографический список
- •394026 Воронеж, Московский просп., 14
5.8. Циклы перестановок
Исходная упорядоченная совокупность n элементов. Воздействуем на нее оператором.
( 1 2 3 4 5 )
( 2 5 4 3 1 )
Воздействие оператора представим записью
(1, 2, 5) (3, 4)
Это означает 1 2 3 4
2 5 4 3
5 1
Последовательность связанных между собой переходов называется циклом.
Циклы, содержащие один элемент называются единичными. Циклы, содержащие два элемента - двоичными. Три – троичными, и т.д.
Перестановка может быть содержать
единичных циклов
двоичных циклов
троичных циклов
…
n-ичных циклов
Совокупность чисел определяют цикловой класс (или просто класс)
связь
с числом n
Для нашего примера имеем:
1
- число перестановок циклового класса (k)
? Как найти число перестановок, имеющих единичных, двоичных и т.д.
Выберем произвольную перестановку класса (k) и переставим все элементы всеми возможными n! способами.
Д ве причины, в силу которых не все получившиеся в результате этой операции перестановки оказываются различными.
I.
Не отличаются с токи зрения циклового
класса друг от друга все циклы, в которые
входит одинаковое число одинаковых
элементов.
II.
Относительное располо-жение циклов
несуществен-но (с точки зрения циклово-го
класса).
С точки зрения циклового класса не отличаются друг от друга все циклы, в которые входит одинаковое число одинаковых элементов.
Т. к. цикл может начаться с любого из r входящих в него элементов, то можно получить r дубликатов этого цикла.
4
3
r
элементов
r
дубликатов
2
5
2 1 4 3 6 5
1
6
т.к.
Общее число дубликатов для перестановок
Относительное расположение циклов не существенно с точки зрения циклового класса
Если число циклов равно , то их можно переставить = Ч.Д. Г
Общее число дубликатов
где , следовательно
1 2 3 4 5 6
2 1 4 3 6 5
1 3 5
2 4 6
Относительно первого фактора:
Имеем
Общее количество
дубликатов для перестановок
Относительно расположения циклов общее количество дубликатов
Т.е. из «3-х» переставить «3»
Общее количество перестановок будет
Пример. Разобьем на цикловые классы перестановки из 3-х элементов.
1 ,2,3 (1) (2) (3) *** Цикл. класс (3,0,0)
1
Цикл. класс (1,1,0)
3 ,2,1 (1,3), (2) **
2 ,1,3 (1,2), (3) **
3
Цикл. класс (0,0,1)
2 ,3,1 (1,2,3) *
* (3*1=3)
** (1+2*1=3)
*** (3*1+2*0+3*0=3)