Равносильности теории множеств



  • законы (свойства) коммутативности:

, ;

  • законы (свойства) ассоциативности:

, ;

  • законы (свойства) дистрибутивности:

, ;

 

  • законы де Моргана:

, ;

  • законы (свойства) операций с одним множеством:

, ;

  • свойство двойного дополнения:

;

  • свойства операций с пустым множеством:

AÈÆ = A, AÇÆ = Æ;

  • свойства операций с универсальным множеством:

AÈU = U, AÇU = A;

  • свойства дополнения:

, .

Графы.

В математической теории графов и информатике граф — это совокупность непустого множества вершин и наборов пар вершин (связей между вершинами).

Граф задается между двумя множествами.

 

Виды графов

Ориентированные графы— Граф, обладающий упорядоченными парами вершин;

Неориентированные графы — Граф, обладающий неупорядоченными парами вершин;

Смешанные графы — в котором встречаются как ориентированные, так и неориентированные рёбра и петли;

Эйлеровы графы — граф в котором существует циклический эйлеров путь (Эйлеров цикл).

мультиграфы — графы с кратными рёбрами, имеющими своими концами одну и ту же пару вершин;

Псевдографы — это мультиграфы, допускающие наличие петель;

Простые графы — не имеющие петель и кратных рёбер.

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

 

Элементы графов

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

Рёбра, проходящие через одну вершину, называются смежными.

Вершины, соединенные ребром, называется смежными.

Петля- это ребро, выходящее и заходящее из одной вершины.

Если 2 вершины соединены 2-мя или более ребер, то такие ребра называются кратными.

Степенью вершин неориентированного графа называется число ребер, проходящих через эти вершины.

Если степень вершины 0, то эта вершина называется изолированной.

Если степень вершины 1, то эта вершина называется висячей.

 

 

Представление графов в ЭВМ

Наиболее распространены следующие 4 метода представления графов в ЭВМ:

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

- Матрица инцидентности,

- Списки смежности вершин,

- Списки смежности дуг.

Вы уже имеете представление о представлении графа матрицами смежности и инцидентности (Тема 11, пункт 1). Поясним суть списков смежности вершин.

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

 

Правило суммы и произведения

Правило суммы: если элемент А можно выбрать n различными способами и независимо от него элемент B можно выбрать m различными способами, то выбрать все различные комбинации элементов «A или B» можно n+m способами. Пример: Школьникам на предстоящий зачет дается на выбор 5 тем по алгебре или 7 по геометрии. Сколькими способами можно выбрать тему по алгебре или геометрии? Решение: |X|=5, |Y|=7. Множества не пересекаются, значит можно применить правило суммы: |X|+|Y|=5+7=12 способов.

Ответ: 12 способами ученик может выбрать тему.

 

Правило произведения: если элемент A можно выбрать n различными способами и независимо от него элемент B можно выбрать m различными способами, то все различные комбинации элементов «A и B» можно выбрать n*m способами.

Пример: На первой полке стоит 10 книг, а на второй 5.

Сколькими способами можно взять книги с обеих полок? Решение: |X|=10, |Y|=5. По правилу произведения: |X|*|Y|=10*5=50.

Ответ: 50 способами.

 

Размещения с повторениями

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

.

 

Размещения без повторений

Размещениями из n элементов по k (k≤n) называются упорядоченные k-элементные выборки из данных n элементов   , причем выбирать только один предмет одного вида.Повторения запрещены.

- количество множителей равно k.

 

 

Перестановки без повторений

Перестановкой изэлементов (или -перестановкой) называется размещение из элементов по без повторений.

Pn = n!

 

Сочетания без повторений

Сочетаниями из n элементов по m (m≤n) называются неупорядоченные m-элементные выборки элементов.

 


Дата добавления: 2018-02-15; просмотров: 252; ЗАКАЗАТЬ РАБОТУ