Основи дискретної математики:Іспит

Матеріал з USIC Wiki

Перейти до: навігація, пошук

Ця стаття відноситься до групи довідкових статей для студентів ФІН.

Портал:Інформаційні науки

Державний іспит

Зміст

1 Числення висловлювань.
2 Операції над висловлюваннями та їх властивості.
3 Основні тавтології та правила логічного наслідку.
4 Бульові функції, операції над ними.
5 Застосування до побудови релейно-контактних схем. диз’юнктивні та кон'юнктивні нормальні форми
6 Метод математичної індукції.
7 Основні поняття теорії множин.
- 7.1 Опукла множина
8 Парадокс Рассела.
9 Діаграми Ейлера-Вена.
10 Способи представлення множин в пам’яті комп’ютера.
11 Операції над множинами та їх властивості.
12 Закони де Моргана.
13 Декартів добуток множин.
- 13.1 Проекції
- 13.2 Образ та прообраз множин
14 Поняття функції , способи її задання.
15 Основні принципи комбінаторики.
16 Розміщення, перестановки, комбінації (з повтореннями і без).
- 16.1 Вибір з поверненням і без врахування порядку
17 Біноміальні коефіцієнти та їх інтерпретації.
18 Поліноміальні коефіцієнти.
19 Формули включень та виключень.
20 Порівняння нескінченних множин.
21 Рівнопотужні множини.
22 Зліченні та незліченні множини, основні теореми.
- 22.1 Властивості зліченних множин
- 22.2 Незліченні множини
23 Зліченність множини раціональних чисел та незліченність множини двійкових послідовностей.
24 Порівняння потужностей множини та її булеана.
25 Поняття про кардинальні числа.
26 Відношення та відповідності, задані на множинах.
27 Графіки та графи бінарних відношень.
28 Операції над відношеннями.
29 Спеціальні типи відношень. Функціональні відношення. Відношення еквівалентності, поняття фактор-множини Відношення часткового порядку, решітки.
- 29.1 Бінарне відношення
- 29.2 Рефлексивне відношення
- 29.3 Антирефлексивне відношення
- 29.4 Симетричне відношення
- 29.5 Антисиметричне відношення
- 29.6 Транзитивне відношення
- 29.7 Діагональ-відношення
- 29.8 Відношення еквівалентності
- 29.9 Відношення порядку
- 29.10 Нестроге відношення порядку
- 29.11 Строге відношення порядку
- 29.12 Відношення лінійного порядку
- 29.13 Відношення часткового порядку
- 29.14 Відношення строгого часткового порядку
- 29.15 Відношення нестрогого часткового порядку
- 29.16 Решітка
30 Оcновні поняття тeорії графів.
31 Ейлерові та гамільтонові графи.
32 Дерева та їх властивості.

Числення висловлювань.

Висловлювання - це твердження, якому за певних обставин можуть бути надані значення "істина" або "хиба". Таке співставлення називається інтерпретацією висловлювання.

Просте висловлювання - це висловлювання, яке не можна подати як сполучення певних більш коротких висловлювань.

Складені (непрості) висловлювання будуються з простих за допомогою різних сполучників "або", "та", "отже" та інших.

Не є висловлюваннями запитальні та окличні твердження: "Чи існує життя на Марсі?", "Героям слава!".

Операції над висловлюваннями та їх властивості.

Операції над висловлюваннями - це математична формалізація сполучників, за допомогою яких будуються складені висловлювання. Визначити логічну операцію означає задати правило яке за значеннями істинності висловлювань, що сполучаються, однозначно визначає значення істинності висловлювання, тцо отримано внаслідок такого сполучення (виконання логічної операції).

1. Диз'юнкція. Еквівалентні назви — "логічна сума", "або", "ОR". Позначається $A \lor B$ . Правило інтерпретації (інша назва - таблиця істинності):


$\frac{I(B)}{I(A)}$	0	1
0	0	1
1	1	1

2. Кон'юнкція. Еквівалентні назви — "логічний добуток", "і", "АND". Позначається $A \land B$ або $A \And B$ . Правило інтерпретації:


$\frac{I(B)}{I(A)}$	0	1
0	0	0
1	0	1

3. Імплікація. Еквівалентні назви — "логічний наслідок" Позначається $A \to B$ . Правило інтерпретації:


$\frac{I(B)}{I(A)}$	0	1
0	1	1
1	0	1

При цьому А називають умовою (достатньою для В) або антецедентом, а висловлювання В - наслідком або консеквентом. Також говорять, що умова В є необхідною для А.

4.Еквівалентність. Тоді і лише тоді, або необхідна і достатня умови: $A \leftrightarrow B$ . Правило інтерпретації:


$\frac{I(B)}{I(A)}$	0	1
0	1	0
1	0	1

Умова В є необхідною ( $A \to B$ ) і достатньою ( $B \to A$ ) для А. В математиці теореми такого характеру називають критеріями.

5. Заперечення. Частка "НЕ" є унарною операцією, позначається ¬А, з таблицею інтепретації:


I(A)	0	1
I(¬А)	1	0

6. Виключне або. В людській мові зв'язка або може використовуватись як для означення альтернативи "або а або b", так і для більш жорсткої форми — "або тільки А або тільки В", тобто підкреслюється неможливість одночасного виконання тверджень А і В. Таке значення зв'язки "або" моделює операція "виключного або". Еквівалентна назва — "ХОR". Позначається $A \oplus B$ . Правило інтерпретації:


$\frac{I(B)}{I(A)}$	0	1
0	0	1
1	1	0

Ці операції моделюють відповідні сполучники людської мови. Але формально можна ввести і інші логічні операції.

Основні тавтології та правила логічного наслідку.

Формула Р називається тавтологією (тотожно-істинною), якщо I(Р) = 1 незалежно від способу інтерпретації простих висловлювань, що входять у неї.

Формула Р називається тотожно-хибною, якщо I(Р) = 0 незалежно від способу інтерпретації простих висловлювань, що входять у неї.

Інтерпретація простих висловлювань I(а), I(b), I(с),... називається моделлю формули Р = Р(а,b,с, ...), якщо I(Р) = 1.

Формула Р називається виконливою, якщо вона має принаймні одну модель і не є тотожно-істинною.

Формула F називається логічним наслідком формул $H_1, H_2, H_3, \dots, H_n$ , якщо для довільної інтерпретації I простих висловлювань, що входять у цю формулу, з рівностей $I (H 1) = I (H 2) = ... = I (H n) = 1$ випливає, що I(F) = 1.

Це буде записуватися наступним чином:

$H_1, H_2, \dots, H_n \vDash F$ .

Запис $\vDash F$ означає, що F є тавтологією.

Основні типи логічних наслідків.

1. Правило modus ponens

$A, A \to B \vDash B$

2. Правило modus tallens

$A \to B, \neg B \vDash \neg A$

3. Правило силогізму

$A \to B, B \to C \vDash A \to C$

4. Правило резолюцій:

$X \to F, \neg X \to G \vDash F \vee G$ або $X \vee F, \neg X \vee G \vDash F \vee G$

5. Правила введення диз'юнкції і кон'юнкції

$A \vDash A \vee B$

$B \vDash A \vee B$

$A, B \vDash A \wedge B$

6. Правила вилучення диз'юнкції і кон'юнкції

$A \wedge B \vDash A$

$A \wedge B \vDash B$

$A \vee B, \neg A \vDash B$

$A \vee B, \neg B \vDash A$

7. Правила зняття подвійного заперечення і його введення

$\neg ( \neg A) \vDash A$

$A \vDash \neg ( \neg A)$

Бульові функції, операції над ними.

Бульовим вектором називаеться впорядкований набір нулів та одиниць: (*,*,...,*), * = 0,1, довжина набору називаеться розмірністю вектора;

Бульовою функцією (на честь англійського логіка Дж. Булля) $f = f (x 1, x 2,..., x n)$ від n змінних називаеться закон або правило, яке ставить у відповідність кожному бульовому вектору або 0, або 1. Найпростіший спосіб задання функції - це табличний. Для бульових функцій таблиця буде мати вигляд

$x 1$	$x 2$	$x 3$	...	$x n$	$f (x 1,..., x n)$
0	0	0	...	0	*
1	0	0	...	0	*
0	1	0	...	0	*
...	...	...	...	...	*
1	1	1	...	1	*

Бачимо, що таблиця бульової функції має такий же вид, як і таблиця істинності формули числення висловлювань. Таким чином, кожній формулі числення висловлювання можна співставити бульову функцію, таблиця якої збігається з таблицею істинності формули. 3 іншого боку, можна вважати, що кожна бульова функція f від n змінних визначає операцію над висловлюваннями, яка набору висловлювань $A 1, A 2, A 3,.. A n$ ставить у відповідність висловлювання $f [A 1, A 2, A 3,.. A n]$ , істинність якого однозначно вираховується по набору $I (A 1), I (A 2), I (A 3),.. I (A n)$ за таблицею.

Застосування до побудови релейно-контактних схем. диз’юнктивні та кон'юнктивні нормальні форми

Введемо такі позначення для простих висловлювань:

$a^\epsilon = \begin{cases} a, \epsilon = 1; \\ \lnot a, \epsilon = 0 \end{cases}$

Формула виду

$a_1^{\epsilon_1} \land a_2^{\epsilon_2} \land \dots \land a_k^{\epsilon_k} \qquad \qquad \qquad \qquad (1)$

називається елементарною кон'юнкцією (кон'юнктивним одночленом), а формула виду

$a_1^{\epsilon_1} \lor a_2^{\epsilon_2} \lor \dots \lor a_k^{\epsilon_k} \qquad \qquad \qquad \qquad (2)$

елементарною диз'юнкцією (диз'юнктивним одночленом). При цьому допускається, що k = 1, тоді елементарна диз'юнкція (кон'юнкція) не містить зв'язки $\lor (\land)$ .

Формула, яка є диз'юнкцією елементарних кон'юнкцій, тобто має вигляд

$F_1 \land F_2 \land \dots \land F_n$ ,

де $F i$ - формули виду (1), називається диз'юнктивною нормальною формою ДНФ.

Формула, яка є кон'юнкцією елементарних диз'юнкцій, тобто має вигляд

$F_1 \lor F_2 \lor \dots \lor F_n$ ,

де $F i$ - формули виду (2), називається кон'юнктивною нормальною формою КНФ.

ДНФ (КНФ) формули F називається досконалою ДДНФ (ДКНФ), якщо кожна її елементарна кон'юнкція (диз'юнкція) залежить від усіх простих висловлювань, що входять у формулу F.

Легко бачити, що за алгоритм, запропонований при доведенні повноти набору { $\neg, \wedge, \vee$ }, можна отримати формулу як у вигляді ДДНФ, так і ДКНФ. Тим самим доведено такий наслідок:

Будь-яка формула, яка не є тотожно-хибною (тотожно-істинною), еквівалентна ДДНФ (ДДНФ).

Релейно-контактні схеми складаються з включаючих та розмикаючих реле, які будуть зображуватися наступним чином: , .

Перше реле замикає ланцюг, якщо на нього подано сигнал 1 (I(a) = 1). Друге реле в цій ситуації ланцюг розриває.

Сама схема утворюється шляхом композиції паралельних

та послідовних

з'єднань. При цьому І(а) = 1 означає, що всі реле, позначені літерою а, замикають схему, а ті, що позначені $\lnot a$ - її розмикають. Таким чином кожній релейно-контактній схемі можна співставити бульову функцію, яку часто називають функцією провідності схеми, значенням якої, при даних станах вмикаючих та розмикаючих реле, є 1, якщо ток проходить через схему (лампочка горить) і 0 в протилежному випадку.

Важливою інженерною задачею є побудова по таблиці значень бульової функції відповідної релейно-контактної схеми. В принципі, цю задачу розв'язує алгоритм побудови ДДНФ (ДКНФ). Але отримані схеми можуть бути далекими від оптимальних. Задача мінімізації таких схем або бульових функцій є давньою складною задачею і в загальному випадку не має розв'язку. Тобто не існує загального алгоритму, який би за таблицею функції провідності будував схему з мінімальною кількістю реле.

Метод математичної індукції.

Нехай область інтерпретації D є множиною натуральних чисел N і А(х) — деякий унарний предикат. Метод математичної індукції можна визначити, як такий логічний наслідок

$A(1), \forall n ( A (n) \to A (n + 1)) \vDash \forall n A (n) \qquad \qquad \qquad \qquad (1)$

Доведемо, що цей логічний наслідок правильний. Нагадаємо, що для цього треба довести, що якщо для деякої інтерпретації I має місце

$I(A(1)) = I (\forall n ( A (n) \to A (n + 1))) = 1$ то $I (\forall n A (n)) = 1$

Доведемо це методом від супротивного: припустимо, що для деякої інтерпретації I має місце $I (\forall n A (n)) = 0$ .

Маємо, що існують такі натуральні числа m : I(А(m)) = 0. Серед таких чисел завжди можна обрати найменше - $m *$ (це властивість множини натуральних чисел). Яктцо $m * = 1$ , то маємо I(А(1)) = 0. Якщо ж $m * > 1$ , то $I (A (m * - 1)) = 1$ , звідки $I(A(m* - 1) \to A(m*)) = 0$ . Це означає, що $I (\forall n ( A (n) \to A (n + 1))) = 0$ . Отже, при зробленому припущенні рівності $I(A(1)) = I (\forall n ( A (n) \to A (n + 1))) = 1$ є неможливим . Цим твердження доведено.

Висловлювання А(1) в наслідку (1) називається базою індукції, а формула $\forall n ( A (n) \to A (n + 1))$ — індукційним кроком. Оскільки формула або твердження може залежати від декількох числових параметрів, що є натуральними числами, то слід обов'язково вказати, по якому з них буде проводитись індукція.

Основні поняття теорії множин.

Поняття множини відноситься до фундаментальних невизначених понять математики

Множина - однозначно визначена сукупність елементів довільної природи.

Для позначення множини будемо вживати великі літери А, В, С, D, а для їх елементів - маленькі літери a, b, c, d

Порожня множина - множина, що не містить жодного елемента (позначення - $\varnothing$ ). Для будь-якої множини порожня множина є її підмножиною.

Множина А називається підмножиною множини В, якщо кожен елемент з множини А лежить в множині В.

$x \in A \Rightarrow x \in B$ Позначається $A \subset B$

Множини А і В називається рівними, коли $A \subset B$ і $B \subset A$

Опукла множина

Опукла множина — підмножина евклідового простору яка містить відрізок, який з'єднує будь які дві точки цієї множини.

Множина X ⊂ Rⁿ називається опуклою, якщо:

$\alpha x_1 + (1 - \alpha) x_2 \in \mathbf X, \quad \forall x_1, x_2 \in X, \, \alpha \in [0, 1].$

Тобто, якщо множина X разом з будь якими двома точками x₁, x₂ які належать цій множини, містить відрізок, який їх з'єднує:

$[x_1, x_2] = \left\{x:\, x = x_2 + \alpha (x_1 - x_2),\, \alpha \in [0, 1]\right\}$ .

Парадокс Рассела.

Розіб'ємо всі множини на два класи

1. Множини, які не є елементами самих себе, тобто $X \notin X$ .

2. Множини які є елементами самих себе, тобто $X \in X$ .

До множин з класу 1 відноситься множина студентів в аудиторії, адже множина студентів не є студентом. Більшість множин, які вивчаються в математиці, відносяться до цього класу. Але наївне означення дозволяє розглянути множину всіх множин або множину всіх нескінченних множин, які, очевидно, відносяться до множин другого класу. Зрозуміло, що будь-яка множина відноситься або до першого, або до другого класу. Розглянемо множину М всіх множин з першого класу і поставимо питання: до якого з двох класів належить М ? Припустимо, що до першого, тоді $M \notin M$ , але ж за означенням елементами М є всі множини з першого класу, отже, М належить другому класу. Тоді $M \in M$ , але множина М складається тільки з множин першого класу, отже, М належить першому класу.

На початку 20-го сторіччя цей парадокс викликав сумніви у самих основах математики. Причиною виникнення цього парадокса є те, що наївне означення дозволяє оперувати з елементами довільної (невизначеної) природи.

Одним із шляхів подолання парадоксу є так звана теорія типів.

1) елементам (об'єктам) приписується тип 0;

2) множинам елементами яких є елементи типу 0 приписується тип 1;

3) множинам елементами яких є множини 1-го типу приписується тип 2;

4) множинам, елементами яких є множини типу к приписується тип к + 1, к =1,2,3,....

На холопський розум цей парадокс описується так: "В деякому місті живе брадобрей (той, що бриє людей). Він бриє усіх, хто не бриється сам. Парадокс: хто бриє його?!"

Діаграми Ейлера-Вена.

Довести закони алгебри висловлювань можна

1) побудувавши таблицю істинності

2) виконавши еквівалентні перетворення над правою і лівою частинами формули для приведення їх до одного вигляду.

3) За допомогою діаграм Ейлера-Вена

Леонард Ейлер при розв’язуванні задач зображав множини кругами, і на його честь цей був названий цей метод. Однак при розв’язуванні логічних задач такими колами корисно зображати висловлювання. Будь-яке висловлювання зображається кругом, а його заперечення – частиною площини, що знаходиться поза кругом.

Способи представлення множин в пам’яті комп’ютера.

При алгоритмізації задач, що потребують математичних доведень, розробка алгоритму часто проводиться у математичних або формалізованих прикладних термінах. При цьому невелику роль відіграють технічні можливості комп’ютера. Для поняття множин часто буває достатньо вміти виконувати тільки деякі операції, пов’язані з множинами, як, наприклад

• Ввести до розгляду порожню множину

• Додати (видалити) елемент до (з) множини

• Дізнатись кількість елементів множини тощо

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

Автомати. 3 точки зору інформатики, автомат є математичною моделлю певного механічно-обчислювального процесу, тобто роботи комп'ютера при розв'язанні конкретної задачі.

Автоматом Мілі називається довільна трійка множин A, X, Y разом з визначеним відображенням декартових добутків

$\phi : A \times X \mapsto A \times Y$

множина A називається множиною станів, множини X, Y називаються вхідним та вихідним алфавітами, відповідно, відображення f однозначно визначається парою функцій – функцією переходів $f : A \times X \mapsto A$ та функцією виходів $g : A \times X \mapsto Y$ , які є проекціями функції $φ$ на першу та другу координати, тобто $φ(a, x) = (f (a, x), g (a, x))$

Автомат називаеться скінченним, якщо всі три множини A, X, Y є скінченними. Скінченні автомати можна задавати таблицями або графами переходів та виходів.

Операції над множинами та їх властивості.

Основні операції над множинами

Об’єднання множин

$A \cup B = \big\{\omega \in \Omega|\omega \in A \vee \omega \in B \big\}$

Перетин множин

$A \cap B = \big\{\omega \in \Omega|\omega \in A \wedge \omega \in B \big\}$

Різниця множин

$A \setminus B = \big\{\omega \in \Omega|\omega \in A \wedge \omega \notin B \big\}$

Доповнення множини

$\overline A = \big\{\omega \in \Omega|\omega \notin A \big\}$

Симетрична різниця множин

$A \oplus B = \big\{\omega \in \Omega|(\omega \in A \wedge \omega \notin B) \vee (\omega \in B \wedge \omega \notin A)\big\}$

Властивості

Ідемпотентність

$A \cap A = A = A \cup A$

Комутативність

$A \cap B = B \cap A$ $A \cup B = B \cup A$

Асоціативність

$A \cap ( B \cap C ) = (A \cap B) \cap C$ $A \cup ( B \cup C ) = (A \cup B) \cup C$

Дистрибутивність

$A \cap ( B \cup C ) = (A \cap B) \cup (A \cap C )$ $A \cup ( B \cap C ) = (A \cup B) \cap (A \cup C )$

Узагальнені закони дистрибутивності

$B \bigcap \bigg( \bigcup_{i \in I} A_i \bigg) = \bigcup_{i \in I} (B \cap A_i)$ $B \bigcup \bigg( \bigcap_{i \in I} A_i \bigg) = \bigcap_{i \in I} (B \cup A_i)$

Доповнюваність

$A \cup \overline A = \Omega$ $A \cap \overline A = \varnothing$

Правило де Моргана

$\overline {A \cap B} = \overline A \cup \overline B$ $\overline {A \cup B} = \overline A \cap \overline B$

Закони де Моргана.

Узагальнені закони де Моргана

$\overline {\bigcap_{i \in I} A_i} = \bigcup_{i \in I} \overline A_i$

$\overline {\bigcup_{i \in I} A_i} = \bigcap_{i \in I} \overline A_i$

Доведення 1-го закону до Моргана

$\omega \in \overline {\bigcap_{i \in I} A_i} \Rightarrow \omega \notin \bigcap_{i \in I} A_i \Rightarrow \exists j \in I (\omega \notin A_j) \Rightarrow \omega \in \overline A_j \Rightarrow \omega \in \bigcup_{i \in I} \overline A_i$

$\omega \in \bigcup_{i \in I} \overline A_i \Rightarrow \exists k \in I(\omega \in \overline A_k) \Rightarrow \omega \notin A_k \Rightarrow \omega \notin \bigcap_{i \in I} A_i \Rightarrow \omega \in \overline {\bigcap_{i \in I} A_i}$

Декартів добуток множин.

$\Omega \supset A, B$

Декартовим добутком множин А та В називається множина впорядкованих пар (a,b)

$A \times B = \big\{ (a, b)| a \in A, b \in B \big\} \subseteq \Omega \times \Omega$

$(a, b)$ - впорядкована. Важливо, що a - перший, b - другий

Для 3-х множин будемо мати такі декартові добутки

$(A \times B)\times C$

$A \times (B \times C)$

$A \times B \times C$

Всі 3 множини є різними (різними типами даних).

Операція декартового добутку не є асоціативною та комутативною : (A×B)×C≠A×(B×C), A×B≠B×A.

Загальне означення декартового добутку

Нехай $A_i, i \in I$ , довільна сукупність множин (І - довільна множина). Тоді множина функцій

$\alpha : I \to \bigcup_{ i \in I} A_i,$ таких, що $\alpha(i) \in A_i,$ називається декартовим добутком сукупності множин $\big\{ A_i|i \in I \big\}$ і позначається $\times_{i=1}^n A_i$

Якщо $\alpha \in \times_{i \in I}A_i$ то $α(i)$ називається проекцією $α$ на множину $A i$ (позначається $P r i (α)$ ) або i-ю координатою елемента $α$

Для довільної підмножини $\Lambda \subset \times_{i \in N} A_i$ проекція на $A i$ визначається наступним чином

$Pr_i(\Lambda) = \bigcup{\lambda \in \Lambda} \big\{ Pr_{A_i} (\lambda) \big\}$

Відображення декартових добутків

$f: \underbrace {A \times A \times ... \times A}_{n} \mapsto A$ називається n-арною операцією, визначеною на множині A

Приклад

$Next : \mathbb{N} \ni x \mapsto x + 1 \in \mathbb{N}$ - приклад унарної операції

$Sum: \mathbb{N} \times \mathbb{N} \ni (x,y) \mapsto x + y \in \mathbb{N}$ - приклад бінарної операції

Проекції

Проекцією кортежу A=(x₁, x₂, ... , x_n) на i-у вісь (або i-ою проекцією) називається i-а координата x_i кортежу A, позначається Pr_i(A) = x_i. Проекцією кортежу A=(x₁, x₂, ... , x_n) на осі з номерами i₁, i₂,..., i_k називається кортеж (x_i1, x_i2, ..., x_ik), позначається Рr_i1,i2,...,ik(A).

Приклад: Якщо V={(a,b,c),(a,c,d),(a,b,d)}, то Pr₁V={a}, Pr₂V={b,c}, Pr_{2, 3}V={(b,c),(c,d), (b,d)}.

Образ та прообраз множин

Образом елемента a∈Pr₁ C при відповідності C називається множина всіх елементів b∈Pr₂ C, які відповідають елементу a.

Прообразом елемента b∈Pr₂ C при відповідності C називається множина всіх тих елементів a∈Pr₁ C, яким відповідає елемент b.

Якщо A∈Pr₁ C, то образом множини A при відповідності C називається об’єднання образів усіх елементів з A. Аналогічно означається прообраз множини B∈Pr₂ C.

Поняття функції , способи її задання.

Функцією $f$ визначеною на множині X, що приймає значення в множині В, називається правило (закон), який ставить у відповідність кожному елементу $x \in X$ однозначно визначений елемент $f(x) \in Y$ ; досить часто в цій ситуації говорять, що задано відображення з множини А в множину В, і позначають це таким чином $f : X \rightarrow Y$

При цьому елемент $y = f (x)$ називається образом елемента x, а сам елемент x називається прообразом елемента y.

Множина Х називається областю визначення, а функція $R(f) = \big\{ f(x)|x \in X \big\}$ називається множиною значень.

$f : X \rightarrow Y$ - сюр’єкція, якщо $\forall y \in Y \exists x \in X: f(x) = y$

$f : X \rightarrow Y$ - ін’єкція, якщо $\forall x_1, x_2 \in X, x_1 \ne x_2 \Rightarrow f(x_1) \ne f(x_2)$

$f : X \rightarrow Y$ - бієкція, якщо є одночасно ін’єкцією та сюр’єкцією

Основні принципи комбінаторики.

Комбінаторикою називається розділ математики, що вивчає спосіб підрахунку кількості варіантів, якими можна зробити певну дію. 3 точки зору теорії множин, комбінаторика дає можливість підрахувати кількість елементів в скінченній множині, яка описана тим чи іншим способом.

Правило суми (розбиття). Якщо маємо n рiзних елементiв, то один з них може бути обрано n способами. Iнодi для отримання числа способiв легше розбити елементи на два типи i рахувати окремо для кожного. Якщо маємо k елементiв першого типу, то елемент першого типу можна обрати k способами, якщо маємо l елементiв другого типу, то елемент другого типу можна обрати l способами. Тодi елемент першого або другого типiв може бути обраний k + l способами. Мовою теорiї множин це правило можна виразити наступним чином:

Для множин $A, B$ , що не перетинаються $A \cap B = \varnothing$ має місце

$|A \cup B| = |A| + |B|$

Узагальнене правило суми (розбиття). Якщо маємо скінченну сукупність множин $A 1, A 2,.. A n$ , що попарно не перетинаються, $\forall i, j(i < j) A_i \cap A_j = \varnothing$ , то

$\bigg| \bigcup_{i=1}^n A_i \bigg| = \sum_{p=1}^n |A_i|$

Правило добутку. Якщо елемент типу I можна вилучити n способами, а елемент типу II після вилучення елементу типу I можна вилучити m способами (незалежно від того, який саме елемент I-го типу був перед цим вилучений), то послідовне вилучення елементів I-го типу, а потім елементів II-го типу можна зробити n m способами. Мовою теорії множин це правило можна записати таким чином:

$|A \times B| = |A| \cdot |B|$

Узагальнене правило добутку. Для довільної скінченної сукупності множин $A 1, A 2,.. A n$ маємо

$|\times_{i=1}^n A_i| = \prod_{p=1}^n |A_i|$

Розміщення, перестановки, комбінації (з повтореннями і без).

Нехай $Ω$ - скінченна n-елементна множина. k-елементним розміщенням, визначеним на множині $Ω$ , називається ін'єкція (відображення в)

$\big\{1, 2, 3, ..k \big\} \to \Omega, (k \le n)$

Число таких розміщень позначається $A_n^k = \frac{n!}{(n-k)!}$ . Общее количество различных наборов при выборе k элементов из n без возвращения и с учётом порядка

Перестановкою (n-елементне розміщенням, визначеним на множині $Ω$ ), називається ін'єкція (відображення в)

$\big\{1, 2, 3, ..k \big\} \to \Omega$

Кількість усіх можливих перестановок: $A_n^n = n!$ .

Нехай $Ω$ — скінченна n—елементна множина. Будь-яка k—елементна підмножина множини $Ω$ називаеться k—елементною комбінацією, визначеною на множині $Ω$ . Число таких комбінацій позначається $C_n^k$ .

Довільне k—елементне розміщення можна отримати, обравши k—елементну комбінацію, а потім впорядкувавши її елементи. Першу дію можна виконати $C_n^k$ способами, другу (впорядкування), незалежно від обраної комбінації, можна виконати k! способами. За правилом добутку маємо

$A_n^k = C_n^k \cdot k!$ ,

звідки

$C_n^k = \frac{A_n^k} {k!}$

Общее количество различных наборов при выборе k элементов из n без возвращения и без учёта порядка равняется

$C_n^k = \frac{n!} {k! \cdot (n-k)!}$

Властивості

$C_n^k = C_{n-k}^k$

$C_{n+1}^k = C_n^{k-1}+C_n^k$

$\sum_{k=0}^n C_n^k = 2^n$

Перестановкою з повтореннями $(n 1, n 2, n 3,..., n k)$ називається функція $\sigma : \big\{ 1,2,3...n \big\} \to I = 1,2,3..,k$ така, що $| σ - 1 (i) | = n i, i = 1,2,3,..., k$ . Число таких перестановок з повтореннями будемо позначати $P (n 1, n 2,... n k)$ .

Кожну звичайну перестановку можна отримати в два кроки

1. обрати перестановку з повторенням $(n 1, n 2,... n k)$ , в якій елементи однакового типу (кольору) не розрізняються;

2. почати розрізняти елементи одного типу (наприклад, ввівши їх нумерацію) і зробивши k перестановок елементів однакового типу.

Кількість способів, якою можна зробити перший крок (за означенням) дорівнює $P (n 1, n 2,... n k)$ . Елементи 1-го типу можна переставити $n 1!$ способами, 2-го типу $n 2!$ способами і т.д., k-го типу - $n k!$ способами. Отже, за правилом добутку, другий крок можна виконати $n_1! \cdot n_2! \cdot n_3! \cdot ... \cdot n_k!$ способами. Оскільки загальна кількість звичайних перестановок дорівнює $n!$ , то за тим же правилом добутку отримуємо

$n! = P(n_1, n_2, n_3, ..., n_k) \cdot n_1! \cdot n_2! \cdot n_3! \cdot ... \cdot n_k!$ , звідки отримуємо

$P(n_1, n_2, n_3, ..., n_k) = \frac{n!} {n_1! \cdot n_2! \cdot n_3! \cdot ... \cdot n_k!}$

Общее количество различных наборов при выборе k элементов из n с возвращением и с учётом порядка равняется .

Вибір з поверненням і без врахування порядку

Загальна кількість різних наборів при виборі k елементів з n із поверненням і без врахування порядку дорівнює:

$C_{n+k-1}^k = C_{n+k-1}^{n-1}$

Біноміальні коефіцієнти та їх інтерпретації.

Формула бiному Ньютона має вид

$(a + b)^n = \sum_{k=0}^n C_n^k \cdot a^k \cdot b^{n-k}$

Доведення. Розглянемо добуток

$\underbrace { (a+b) \cdot (a+b) \cdot (a+b) \cdot ... \cdot (a+b) }_{n}$

Якщо розкривати за законами дистрибутивності цей добуток, то ми отримаємо суму доданків виду $a^k \cdot b^{n-k}$ . Кожен такий доданок отримується таким чином: з множини усіх співмножників (а їх n) обирається k— елементна підмножина - тих співмножників з яких будуть братися елемент a, з решти співмножників (яких n — k) буде обиратися елемент b. Такий вибір можна здійснити $C_n^k$ способами. Отже, будемо мати таку кількість подібних доданків $a^k \cdot b^{n-k}$ в сумі.

Отже, після приведення подібних ми маємо отримати формулу

$(a + b)^n = \sum_{k=0}^n C_n^k \cdot a^k \cdot b^{n-k}$

Як наслідки з цієї формули легко отримати багато властивостей біноміальних коефіцієнтів.

Покладемо a = b = 1 отримаємо вже доведену властивість $\sum_{k=0}^n C_n^k = 2^n$ .

При a = —1, b = 1 отримаємо іншу тотожність

$\sum_{k=0}^n (-1)^ \cdot C_n^k = 0$

Додаткова інформація:

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

Вдоль диагоналей, параллельных сторонам треугольника, выстроены треугольные числа и их обобщения на случай пространств всех размерностей. Суммы чисел, стоящих вдоль восходящих диагоналей, образуют хорошо известную последовательность чисел Фибоначчи. Если, спускаясь по центральному столбцу, из каждого числа вычитать соседнее справа (или слева!), то возникает последовательность чисел Каталана. И наконец, каждый элемент является биномиальным коэффициентом. Именно это фундаментальное свойство треугольника Паскаля связывает его не только с комбинаторикой и теорией вероятностей, но и другими областями математики и ее приложений.

Для биномиальных коэффициентов известно множество различных интерпретаций. Самая популярная из них - комбинаторная.

Поліноміальні коефіцієнти.

За додатковою інформацією - див. питання "Розміщення, перестановки, комбінації (з повтореннями і без)", пункт про перестановки з повтореннями.

Кількість перестановок з повтореннями:

$P(n_1, n_2, n_3, \dots, n_k) = \frac{n!} {n_1! \cdot n_2! \cdot n_3! \cdot \dots \cdot n_k!}$

При k = 2 отримуємо $P(n_1,n_2)= C_n^{n_1} = C_n^{n_2}$ — звичайні біноміальні коефіцієнти.

Узагальненням формули біному Ньютона є поліноміальна формула:

$(x_1 + x_2 + \dots + x_k)^n = \sum_{(n_1,n_2, \dots, n_k): \textstyle \sum_{j = 1}^k n_i=n} \frac{n!}{n_1! \cdot n_2! \cdot \dots \cdot n_k!} x_1^{n_1} \cdot x_2^{n_2} \cdot \dots \cdot x_k^{n_k} \qquad \qquad \qquad \qquad (1)$

Звернемо увагу, що сумування ведеться по всім наборам цілих невід'ємних чисел: $(n 1, n 2, n 3,..., n k)$ , які в сумі дають n.

Доведення. Доведення цієї формули проведемо аналогічно до тих, що були зроблені при доведенні формули Біном Ньютона (див. питання "Біноміальні коефіцієнти та їх інтерпретації").

$\underbrace{(x_1 + x_2 + \dots + x_k) \cdot \dots \cdot (x_1 + x_2 + \dots + x_k)}_{n}$

За законами дистрибутивності, обираючи з кожних дужок по одному доданку, ми отримаємо суму доданків виду:

$x_1^{n_1} \cdot x_2^{n_2} \cdot \dots \cdot x_k^{n_k}$

При цьому кожній дужці можна співставити її тип - номер змінної, яка обирається з цієї дужки. Очевидно, що всі перестановки з повторенням $(n_1, n_2, n_3, \dots, n_k)$ , у яких кількість елементів першого типу є $n 1$ , другого - $n 2$ і т.д., k-ого n-k будуть давати один і той самий доданок $x_1^{n_1} \cdot x_2^{n_2} \cdot \dots \cdot x_k^{n_k}$ , а отже у формулі (1) цей доданок буде з коєфіцієнтом $P(n_1, n_2, \dots, n_k)$ . Цим формула доведена.

Формули включень та виключень.

Ми вже знаємо формулу для підрахунку кількості елементів в об'єднанні двох множин:

$|A \cup B| = |A| + |B| - |A \cap B|$

Її узагальненням є наступна формула:

$\bigg| \bigcup_{i=1}^n A_i \bigg| = \sum_{i=1}^n |A_i| - \sum_{1 \le i < j \le n} |A_i \cap A_j| +\sum_{1 \le i < j < k \le n} |A_i \cap A_j \cap A_k| + ... + (-1)^{n+1} \bigg| \bigcap_{i=1}^n A_i \bigg| \qquad \qquad \qquad \qquad (1)$

Доведення. Доведення проведемо методом математичної індукції по кількості множин.

База індукції - n = 1 є очевидною.

Індукційний крок. Припустимо, що формула (1) доведена для довільної сукупності з n множин і отримаємо відповідну формулу для $| \cup_{i=1}^{n+1} A_i |$ :

$\bigg| \bigcup_{i=1}^{n+1} A_i \bigg| = \bigg| \bigg( \bigcup_{i=1}^{n} A_i \bigg) \bigcup A_{n+1} \bigg| = \bigg| \bigcup_{i=1}^{n} A_i\bigg| + |A_{n+1}| - \bigg| \bigg( \bigcup_{i=1}^{n} A_i \bigg) \cap A_{n+1} \bigg|$

За узагальненим законом дистрибутивності, маємо рівність множин:

$\bigg( \bigcup_{i=1}^{n} A_i \bigg) \cap A_{n+1} = \bigcup_{i=1}^n (A_i \cap A_{n+1})$ ,

звідки

$\bigg| \bigcup_{i=1}^{n+1} A_i \bigg| = \bigg| \bigg( \bigcup_{i=1}^{n} A_i \bigg) \bigcup A_{n+1} \bigg| = \bigg| \bigcup_{i=1}^{n} A_i\bigg| + |A_{n+1}| - \bigg| \bigcup_{i=1}^n (A_i \cap A_{n+1}) \bigg|$

Перший і третій доданки у правій частині є кількостями елементів в об'єднаннях множин, кількість яких дорівнює n, і до них можна застосувати припущення індукції:

$\bigg| \bigcup_{i=1}^{n+1} A_i \bigg| = \sum_{i=1}^n |A_i| - \sum_{1 \le i < j \le n} |A_i \cap A_j | + \sum_{1 \le i < j<k \le n} |A_i \cap A_j \cap A_k| +...$

$+(-1)^{n+1} |A_1 \cap A_2 \cap ... \cap A_n| + |A_{n+1}| -$

$-(\sum_{i=1}^n |A_i \cap A_{n+1}| - \sum_{1 \le i < j \le n} |A_i \cap A_j \cap A_{n+1}|) + \sum_{1 \le i < j<k \le n} |A_i \cap A_j \cap A_k \cap A_{n+1}| +...$

$...+ (-1)^{n+1} \big| \bigcap_{i=1}^{n+1} A_i \big|$

Приєднавши до першої суми доданок $| A n + 1 |$ , отримаємо $\sum_{i=1}^{n+1} |A_i|$ . У наступній сумі відсутні попарні перетини з множиною $A n + 1$ , але відповідні доданки є у дужках, те саме стосується потрійних перетинів. Таким чином, об'єднавши відповідні суми, остаточно отримуємо:

$\bigg| \bigcup_{i=1}^{n+1} A_i \bigg| = \sum_{i=1}^{n+1} |A_i| - \sum_{1 \le i < j \le n+1} |A_i \cap A_j| + \sum_{1 \le i < j < k \le n+1} |A_i \cap A_j \cap A_k | + ... + (-1)^{n+2} \big| \bigcap_{i=1}^{n+1} A_i \big|$ ,

що і треба було довести.

Кількість елементів у доповненні $\overline {\cup_{i=i}^n A_i}$ дорівнює $|\Omega| - |\cup_{i=i}^n A_i|$ .

За узагальненим законом де Моргана маємо

$\overline { \bigcup_{i=1}^n Ai} = \bigcap_{i=1}^n \overline {A_i}$

І отримуємо формулу включень та виключень у другій формі:

$\bigg| \bigcap_{i=1}^n \bigg| = |\Omega| - \sum_{i=1}^n |A_i| + \sum_{1 \le i < j \le n} |A_i \cap A_j| - \sum_{1 \le i < j <k \le n} |A_i \cap A_j \cap A_k| +...+(-1)^n \bigg| \bigcap_{i=1}^n A_i\bigg|$

Порівняння нескінченних множин.

Скінченні множини ми можемо порівнювати між собою по кількості елементів в них. Запис |А| < |В| означає, що множина А містить менше елементів, ніж В. Якщо ж кількість елементів у множинах є однаковою, |А| = |В|, то ці множини є однаковими по кількості елементів, і між цими множинами можна встановити бієкцію (взаємно-однозначну відповідність). 3 цих міркувань начебто випливає, що множина завжди містить "більше" елементів, ніж будь-яка її власна підмножина. Для скінченних множин це очевидно. А для нескінченних ?

Найпростішою нескінченною числовою множиною є множина натуральних чисел N. Розглянемо множину $\tilde{N} = N \cup \big\{ 0 \big\}$ і її власну підмножину N.

Відображення $n \to n + 1$ , очевидно, є бієкцією $\tilde{N} \to N$ . Отже, виходячи з попередніх міркувань, слід вважати, що кількості елементів у цих множинах збігаються. Це перший дещо несподіваний ефект, який ми отримали для нескінченних множин. Множини, кількість елементів яких "збігається" (у цьому сенсі) з кількістю елементів множини натуральних чисел N, будемо називати зліченними.

Будемо говорити, що потужність множини А не перевищує потужність множини В і записувати $|A| \le |B|$ , якщо існує ін'єкція (занурення)

$\phi: A \to B$

Рівнопотужні множини.

Дві множини А і В називають рівнопотужними (еквівалентними), якщо між ними можна встановити бієкцію (взаємно-однозначну відповідність):

$\phi: A \leftrightarrow B$

Саме в цьому сенсі буде вживатися запис |А| = |В|.

Як показує попередній приклад, існування ін'єкції $\phi: A \to B$ , для якої $Im(A) \ne B$ зовсім не означає, що множина А має "меншу" кількість елементів, ніж В.

Будемо говорити, що потужність множини А менша за потужність множини В і писати |А| < |В|, якщо $|A| \le |B|$ , і ці множини не є рівнопотужними.

Якщо ці означення мають сенс, то повинна мати місце імплікація:

$|A| \le |B| \wedge |B| \le |A| \Rightarrow |A| = |B|$

(Теорема Кантора-Бернштейна)

Зліченні та незліченні множини, основні теореми.

Множину А називають зліченною, якщо існує її бієкція на множину натуральних чисел

$A \leftrightarrow N$

Якщо $A \ni a \leftrightarrow n_a \in N$ , то говорять, що $n a$ є номером елемента a. Запис |А| = |N| буде означати, що множина А є зліченною.

Властивості зліченних множин

Об'єднання скінченної та зліченної множин є зліченною множиною.

Доведення. Нехай скінченна множина містить k елементів і визначена нумерація елементів зліченної множини: $n \leftrightarrow a_n$ . Елементам скінченної множини присвоїмо номери з 1 по k, а елементи зліченної множини нумеруємо за допомогою зсуву на k : $n+k \leftrightarrow a_n$ . Очевидно, що цим побудована нумерація об'єднання множин.

Будь-яка підмножина зліченної множини або скінченна, або зліченна.

Доведення. Нехай А — зліченна множина, і В — її підмножина. Оскільки А — зліченна, то кожному її елементу відповідає номер - натуральне число. Серед елементів В оберемо елемент з найменшим номером і присвоїмо йому номер 1, далі з решти елементів виберемо елемент з найменшим номером і присвоїмо йому номер 2. Продовжуючи цей процес, ми отримуємо строго зростаючу послідовність номерів: $n 1 < n 2 < ... < n k < ...$ . Якщо через скінченну кількість кроків ми виберемо всі елементи множини В, то вона скінченна. Якщо ж В — нескінченна множина, то ми отримуємо її бієкцію на множину натуральних чисел, яка визначається наступним чином:

$n_k \to k, k \in N$

Декартів добуток зліченних множин є зліченною множиною.

Доведення. Нехай А та В зліченні множини, тоді існують бієкції

$A \leftrightarrow N \leftrightarrow B$

$A \ni a_n \leftrightarrow n \leftrightarrow b_n \in B$ ,

де n - номер елементів $a n, b n$

Подамо елементи декартового добутку такою таблицею:

$(a 1, b 1)$	$(a 1, b 2)$	$(a 1, b 3)$	$\dots$	$(a 1, b n)$
$(a 2, b 1)$	$(a 2, b 2)$	$(a 2, b 3)$	$\dots$	$(a 2, b n)$
$\dots$	$\dots$	$\dots$	$\dots$	$\dots$
$(a n, b 1)$	$(a n, b 2)$	$(a n, b 3)$	$\dots$	$(a n, b n)$

Тоді задамо спосіб нумерації таблиці. Наприклад

1	2	6	7	15	...
3	5	8	14	...	...
4	9	13	...	...	...
10	12	...	...	...	...
11	...	...	...	...	...

Нехай множина I скінченна, або зліченна і $A_i, i \in I$ — сукупність скінченних або зліченних множин, тоді множина $\bigcup_{i \in I} A_i$ буде або скінченною або зліченною.

Доведення. Якщо множина I зліченна (скінченна), то існує її бієкція на множину натуральних чисел. Отже, існує множина з номером 1, яку ми позначимо $A 1$ , множина з номером 2, яку ми позначимо $A 2$ і т.д. $A n$ . Введемо в розгляд множини

$B_1 = A_1, B_2 = A_2 \big\backslash A_1, ...B_n = A_n \big\backslash \bigg( \bigcup_{i=1}^{n-1} A_i, ... \bigg)$

Неважко переконатися, що

$\bigcup_{i \in I} A_i = \bigcup_{i \in I} B_i, \forall i, j : 1 \le i < j B_i \cap B_j = \varnothing$

За попередньою теоремою, множини $B i$ Є або скінченними або зліченними, отже, можна вважати, що $B_i = \big\{ b_{i1}, b_{i2}, \dots, b_{ik} \big\}$ . Тоді з елементів множини $\cup_{i \in I} B_i$ можна скласти таблицю

$b 11$	$b 12$	$b 13$	$\dots$	$b 1 n$
$b 21$	$b 22$	$b 23$	$\dots$	$b 2 n$
$\dots$	$\dots$	$\dots$	$\dots$	$\dots$
$b n 1$	$b n 2$	$b n 3$	$\dots$	$b n n$
$\dots$	$\dots$	$\dots$	$\dots$	$\dots$

в якій кожен елемент зустрічається один раз. Побудуємо занурення

$\bigcup_{i \in I} B_i \ni b_{i,j} \mapsto (i,j) \in N \times N$

Тоді множина $\bigcup_{i \in I} B_i$ рівнопотужна підмножині множини N x N, яка є зліченною за попередньою теоремою, а отже за теоремою про зліченність декартового добутку, $\bigcup_{i \in I} B_i$ є скінченною або зліченною.

Незліченні множини

Очевидними властивостями незліченних множин є наступні:

якщо деяка підмножина множини є незліченною, то і сама множина є такою;
об'єднання незліченної множини з довільною іншою є незліченною множиною;
декартів добуток незліченної множини з довільною іншою множиною є незліченною множиною.

Для довільної множини А має місце

$| A | < | 2 A |$

Доведення. Будуємо ін'єкцію $A \mapsto 2^A, a \mapsto \big\{ a \big\}$

Доведемо методом від супротивного. Припустимо, що існує бієкція $\phi : A \leftrightarrow 2^A$ , яка ставить у відповідність кожному елементу $a \in A$ підмножину $M_a \subseteq A$ тобто $a \leftrightarrow M_a$ .

Назвемо елемент а хорошим, якщо $a \in \phi(a) = M_a$ , і назвемо елемент а поганим, якщо $a \notin \phi(a) = M_a$ .

Розглянемо підмножину $Bad \subseteq A$ всіх поганих елементів. Оскільки $φ$ — бієкція, то існує елемент $x = \phi^{-1}(Bad) \in A$ , тобто для якого $x \leftrightarrow Bad$ .

Елемент х є хорошим чи поганим? Якщо він хороший, то $x \in Bad$ , а отже він поганий. Якщо він поганий, то $x \notin Bad$ , тобто $x \in \overline Bad$ , але ж в множині $B a d$ зібрано всі погані елементи, а отже х — хороший. Отримана суперечність доводить теорему.

Зліченність множини раціональних чисел та незліченність множини двійкових послідовностей.

Множина раціональних чисел є зліченною.

Дійсно, за означенням, число q називається раціональним, якщо його можна подати у вигляді дробу $q = \frac {m}{n}$ , де m — ціле, n — натуральне. Позначимо через $Q n$ підмножину раціональних чисел, які можна подати у вигляді звичайного дробу із знаменником, рівним n : $q = \frac {m}{n}$ , тоді з раціональних чисел можна скласти таку таблицю:

$Q 1$	...	$- \frac {k+1}{1}$	$- \frac {k}{1}$	...	$- \frac {1}{1}$	$\frac {1}{1}$	...	$\frac {k}{1}$	$\frac {k+1}{1}$	...
$Q 2$	...	$- \frac {k+1}{2}$	$- \frac {k}{2}$	...	$- \frac {1}{2}$	$\frac {1}{2}$	...	$\frac {k}{2}$	$\frac {k+1}{2}$	...
...	...	...	...	...	...	...	...	...	...	...
$Q n$	...	$- \frac {k+1}{n}$	$- \frac {k}{n}$	...	$- \frac {1}{n}$	$\frac {1}{n}$	...	$\frac {k}{n}$	$\frac {k+1}{n}$	...
...	...	...	...	...	...	...	...	...	...	...

Зрозуміло, що в цій таблиці кожне раціональне число зустрічається нескінченну кількість разів і $\mathbb{Q} = \bigcup_{p=1}^{+ \propto} Q_i$ .

Оскільки $Q i$ - зліченні множини, $| Q i | = | Z |$ , то за попередньою теоремою маємо зліченність $\mathbb{Q}$ .

Найпростішим прикладом незліченної множини є множина $2 N$ — двійкових послідовностей, або булеан множини натуральних чисел.

$| N | < | 2 N |$

Доведення. Ін'єкція $|N| \to |2^N|$ будується таким чином $b \to {n}$ ; кожному натуральному числу n ставиться у відповідність одноелементна множина {n}. Отже, маємо $|N| \le |2^N|$ . Покажемо тепер, що $|N| \ne |2^N|$ . Доведення проведемо від супротивного, застосуванням діагонального методу Кантора. Припустимо, що існує бієкція $|N| \leftrightarrow |2^N|$ , тоді маємо нумерацію послідовностей:

1	$b 11$	$b 12$	$b 13$	$\dots$	$b 1 n$
2	$b 21$	$b 22$	$b 23$	$\dots$	$b 2 n$
...	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$
n	$b n 1$	$b n 2$	$b n 3$	$\dots$	$b n n$
...	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$

$b_{i,j} \in$ {0,1}.

Визначимо послідовність $a_k = b_{kk} \oplus 1$ . Ця послідовність повинна мати номер $k *$ , для якого $a_1 = b_{k^*1}, a_2 = b_{k^*2} \dots a_{k-1} = b_{k^*k^*-1}, a_k = b_{k^*k}, \dots$ .

Отримуємо суперечність:

$a_{k^*} = b_{k^*k^*}= b_{k^*k^*} \oplus 1$

Отже, такої бієкції не існує.

Порівняння потужностей множини та її булеана.

Лема. Існує взаємно-однозначна відповідність між множиною всіх підмножин множини А і множиною $\big\{0,1 \big\} ^A$ .

Булеаном множини А називається множина, елементами якої є всі підмножини множини А.

Враховуючи попередню лему, булеан множини позначається як $2 A$ , а іноді вживають запис В(А).

Для довільної множини А має місце

$| A | < | 2 A |$

Доведення. Будуємо ін'єкцію $A \mapsto 2^A, a \mapsto \big\{ a \big\}$

Доведемо методом від супротивного. Припустимо, що існує бієкція $\phi : A \leftrightarrow 2^A$ , яка ставить у відповідність кожному елементу $a \in A$ підмножину $M_a \subseteq A$ тобто $a \leftrightarrow M_a$ .

Назвемо елемент а хорошим, якщо $a \in \phi(a) = M_a$ , і назвемо елемент а поганим, якщо $a \notin \phi(a) = M_a$ .

Розглянемо підмножину $Bad \subseteq A$ всіх поганих елементів. Оскільки $φ$ — бієкція, то існує елемент $x = \phi^{-1}(Bad) \in A$ , тобто для якого $x \leftrightarrow Bad$ .

Елемент х є хорошим чи поганим? Якщо він хороший, то $x \in Bad$ , а отже він поганий. Якщо він поганий, то $x \notin Bad$ , тобто $x \in \overline Bad$ , але ж в множині $B a d$ зібрано всі погані елементи, а отже х — хороший. Отримана суперечність доводить теорему.

Поняття про кардинальні числа.

Природне бажання вважати потужність числом приводить до поняття кардинальних чисел. Кількість елементів в зліченній множині позначається кардинальним "числом" $\aleph_0$ , тобто за означенням $| \mathbb{N}| = \aleph_0$ . Потужність булеана $2 N$ називається континуумом і позначається $\aleph_1 = 2^{\aleph_0}$ . i+1-е кардинальне число визначається через попереднє, як потужність булеана множини, що має потужність $\aleph_i$ , що записують таким чином:

$\aleph_{i+1} = 2^{\aleph_i}$

Отже, маємо ланцюг потужностей

$\aleph_0 < \aleph_1 < \dots < \aleph_{i} < \aleph_{i+1}< \dots$

Виникає природне питання: чи існують незліченні множини, потужність яких була б менша континуума? Твердження про те, що множин такої потужності не існує, називають континуум-гіпотезою і в рамках наївної теорії множин вона не може бути ні доведена, ні спростована.

Більш загальним є питання про існування проміжних потужностей

$\aleph_i < \ ? < \aleph_{i+1}$

Твердження про відсутність таких множин, що $\aleph_i < |A| < \aleph_{i+1}$ називають узагальненою континуум-гіпотезою.

Відношення та відповідності, задані на множинах.

Відношенням (відповідністю) між множинами $D 1, D 2,... D n$ називається довільна підмножина R декартового добутку:

$R \subseteq D_1 \times D_2 \times ... \times D_n$

Характеристична функція відношення $χ R$ називається її характеристичним предикатом. Тобто предикат - це функція, визначена на декартовому добутку $D_1 \times D_2 \times ... \times D_n$ , яка приймає значення з множини {0,1}.

Отже, поняття відношення і предикату є такими ж близькими, як множина та її характеристична функція. Якщо множини збігаються, тобто $D_1 = D_2 = \dots = D_n = D$ , то говорять, що на множині D визначені n — арне відношення та предикат

Нехай $π i$ - проекція декартового добутку на і—ту координату, тобто функція

$\pi_i : d = (d_1...d_n) \to d_i \in D$

Визначимо проекцію відношення R на координати, номери яких належать певній множині $I = \big\{ i_1, i_2... i_k \big\} \subset N = \big\{ 1,2,...n \big\}$ , як відношення між множинами $D_{i_1}, D_{i_2}, \dots, D_{i_k}$ , яке визначається наступним чином

$Pr_I R = Pr_{i_1,...i_k} R = \big\{ \prod_{i \in I} d_i| \exists r \in R \forall i \in I \pi_I(r) = \prod_{i \in I} d_i \big\}$

Нехай $R 1$ — відношення між множинами $D_1, i \in I$ , а $R 2$ — відношення між множинами $E_j, j \in J$ , де $I, J \subset N$ . Нехай $K \subseteq I \cap J$ є непорожньою множиною. K—згорткою або композицією відношень $R 1, R 2$ називається відношення $R_1 \circ R_2$ між множинами $D_j, E_j, i, j \notin K$ , яке визначається наступним чином.

$R_1 \circ R_2 = \Bigg\{ \prod_{l \in I \big\backslash K} d_l \times \prod_{j \in J \big\backslash K} e_j | \exists r_1 \in R_1, \exists r_2 \in R_2: Pr_K(r_1) = Pr_K(r_2),$

$Pr_{I \big\backslash K} (R_1) = \prod _{l \in I \big\backslash K} d_l, Pr_{J \big\backslash K} (R_2) = \prod _{j \in J \big\backslash K} c_j \Bigg\}$

Графіки та графи бінарних відношень.

Основними способами визначення бiнарних вiдношень є такi:

1) таблицею (матрицею) вiдповiдного предикату:

	$b 1$	$b 2$	$\dots$	$b l$
$a 1$	*	*	...	*
$a 2$	*	*	...	*
$\dots$	...	...	...	...
$a k$	*	*	...	*

де $* \in {0,1}$ ;

2) графом вiдношення: елементи множин зображаються точками, пари яких з'єднуються орiєнтованими дугами, якщо вони належать вiдношенню;

3) якщо множини A, B є числовими,тобто $A, B \subset R$ , то кожнiй парi $(a, b) \in R$ можна спiвставити точку на декартовiй площинi, що має координати x = a, y = b; Отримана множина точок називається графiком вiдношення.

Якщо на площинi зображенi графи вiдношень $R_1 \subset A \times B$ та $R_2 \subset B \times C$ , то граф вiдношення $R_1 \circ R_2$ можна отримати з'єднанням дугами тих пар $(a, c); a \in A, c \in C$ , для яких iснує шлях $a \to b \to c$ , де перша стрiлка вiдповiдає дузi графа вiдношення $R 1$ , а друга - дузi графа вiдношення $R 2$ . Якщо $σ = (1,2)$ − перестановка координат, то для зображення графа вiдношення $R σ$ слiд змiнити напрямок дуг на протилежний.

Для бiнарних вiдношень прийнято позначення $R^{-1} = R^\sigma \subset B \times A$ i це вiдношення називають оберненим до R.

Операції над відношеннями.

Нехай $π i$ - проекція декартового добутку на і—ту координату, тобто функція

$\pi_i : d = (d_1...d_n) \to d_i \in D$

Визначимо проекцію відношення R на координати, номери яких належать певній множині $I = \big\{ i_1, i_2... i_k \big\} \subset N = \big\{ 1,2,...n \big\}$ , як відношення між множинами $D_{i_1}, D_{i_2}, \dots, D_{i_k}$ , яке визначається наступним чином

$Pr_I R = Pr_{i_1,...i_k} R = \big\{ \prod_{i \in I} d_i| \exists r \in R \forall i \in I \pi_I(r) = \prod_{i \in I} d_i \big\}$

Нехай $R 1$ — відношення між множинами $D_1, i \in I$ , а $R 2$ — відношення між множинами $E_j, j \in J$ , де $I, J \subset N$ . Нехай $K \subseteq I \cap J$ є непорожньою множиною. K—згорткою або композицією відношень $R 1, R 2$ називається відношення $R_1 \circ R_2$ між множинами $D_j, E_j, i, j \notin K$ , яке визначається наступним чином.

$R_1 \circ R_2 = \Bigg\{ \prod_{l \in I \big\backslash K} d_l \times \prod_{j \in J \big\backslash K} e_j | \exists r_1 \in R_1, \exists r_2 \in R_2: Pr_K(r_1) = Pr_K(r_2),$

$Pr_{I \big\backslash K} (R_1) = \prod _{l \in I \big\backslash K} d_l, Pr_{J \big\backslash K} (R_2) = \prod _{j \in J \big\backslash K} c_j \Bigg\}$

Для вiдношення R мiж множинами $D_1, D_2, \dots, D_n$ i довiльної перестановки iндексiв $\sigma = (i_1, i_2, \dots, i_n)$ визначимо вiдношення $R σ$ мiж множинами $D_{i_1}, D_{i_2}, \dots, D_{i_n}$ , яке складається з таких наборiв $(d_{i_1}, d_{i_2}, \dots, d_{i_n})$ , що пiсля зворотньої перестановки координат $σ - 1$ отриманий набiр належить R, тобто $(d_{i_1}, d_{i_2}, \dots, d_{i_n})^{\sigma^{-1}} \in R$ .

Спеціальні типи відношень. Функціональні відношення. Відношення еквівалентності, поняття фактор-множини Відношення часткового порядку, решітки.

Бінарне відношення

Бінарне відношення - n=2 , R=A×B , тобто довільна підмножина R декартового добутоку 2-х множин.

Рефлексивне відношення

Бiнарне вiдношення R на множинi D називається рефлексивним, якщо

$\forall d \in D \ \ \ (d, d) \in R$

Антирефлексивне відношення

Бiнарне вiдношення R називається антирефлексивним, якщо

$\forall d \in D \ \ \ (d, d) \notin R$

Симетричне відношення

Бiнарне вiдношення R на множинi D називається симетричним, якщо

$\forall d_1, d_2 \in D \ \ \ (d_1, d_2) \in R \Rightarrow (d_2, d_1) \in R$

Антисиметричне відношення

Бiнарне вiдношення R називається антисиметричним, якщо

$\forall d_1, d_2 \in D \ \ \ (d_1, d_2) \in R \land (d_2, d_1) \in R \Rightarrow d_1 = d_2$

Транзитивне відношення

Бiнарне вiдношення R на множинi D називається транзитивним, якщо

$\forall d_1, d_2, d_3 \in D \ \ \ (d_1, d_2) \in R \land (d_2, d_3) \in R \Rightarrow (d_1, d_3) \in R$

Діагональ-відношення

Вiдношення $\Delta = {(d,d) | d \in D} \subset D \times D$ називають дiагоналлю. Умова рефлексивностi означає, що $\Delta \subseteq R$ , а умова антирефлексивностi означає, що $\Delta \subseteq \bar R$ , тобто рефлексивним є доповнення до вiдношення R. Умова симетричностi вiдношення R може бути записана таким чином:

$R = R - 1$ ,

а умова транзитивностi - у такий спосiб:

$R \circ R \subseteq R$ .

Нехай ∗ -одна з властивостей - рефлексивнiсть, симетричнiсть або транзитивнiсть.Тодi *-замиканням вiдношення R називається найменше (за включенням) бiнарне вiдношення $\tilde R : \tilde R \supseteq R$ (на множинi D), що має властивiсть ∗ i $\tilde R \supseteq R$ .

Відношення еквівалентності

Бiнарне вiдношення R на множинi D називається вiдношенням еквiвалентностi, якщо воно

1) рефлексивне

2) симетричне

3) транзитивне.

Для вiдношень еквiвалентностi замiсть запису $(d_1, d_2) \in R$ вживають запис $d 1 ˜ d 2$ .

Нехай на множинi D задано вiдношення еквiвалентностi ∼ . Для кожного $a \in D$ введемо в розгляд множини

$D_a = \left \{ d \in D \ | \ d \sim a \right \}$

Для будь-яких елементiв $a, b \in D$ має мiсце одне з двох:

або $D a = D b$

або $D_a \cap D_b = \varnothing$

Доведення. Припустимо, що $D_a \cap D_b = \varnothing$ i $d^* \in D_a \cap D_b$ , тодi за означенням множин $D a, D b$ , маємо: $a ˜ d *, b ˜ d *$ . Враховуючи симетричнiсть вiдношення, $a ˜ d *, d * ˜ b$ , а за транзитивнiстю a ∼ b i, звичайно, b ∼ a. Тодi для будь-якого елемента $d \in D_a$ , за транзитивнiстю маємо $d \sim a \sim b \Rightarrow d \sim b \Rightarrow d \in D_b$ , тобто $D_a \subseteq D_b$ . Аналогiчно доводиться протилежне включення i отримується рiвнiсть $D a = D b$ .

Множини $D a$ називаються класами еквiвалентностi, а множина, елементами якої є класи еквiвалентностi, називається фактор-множиною множини D по вiдношенню еквiвалентностi ∼ i позначається D/∼ .

Сукупнiсть елементiв множини A, взятих по одному з кожного класу еквiвалентностi, називається сукупнiстю представникiв класiв еквiвалентностi.

Відношення порядку

Відношення порядку в математиці — бінарне відношення, яке є транзитивним та антисиметричним.

$\forall a,b,c: \;\; (a R b \land b R c \Rightarrow a R c)$ (транзитивність),

$\forall a,b: \;\; (a R b \land b R a \Rightarrow a = b)$ (антисиметричність).

Нестроге відношення порядку

Відношення порядку називається нестрогим, якщо воно рефлексивне

$\forall a: \;\; (a R a)$ .

Строге відношення порядку

І навпаки, відношення строгого порядку є антирефлексивним

$\forall a: \;\; (\lnot a R a)$ .

Відношення лінійного порядку

Відношення порядку називається повним (лінійним), якщо

$\forall a,b: \;\; (a R b \lor b R a)$ (повне відношення).

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

Відношення часткового порядку

Якщо умова повноти не виконується і порядок є нестрогим, то відношення називають відношенням часткового порядку.

Зазвичай відношення строгого порядку (повного чи часткового) позначається знаком <, а відношення нестрогого порядку знаком $\le$ .

Відношення строгого часткового порядку

Бiнарне вiдношення на множинi D називається вiдношенням строгого часткового порядку, якщо воно

1) антирефлексивне

2) транзитивне

Відношення нестрогого часткового порядку

Бiнарне вiдношення на множинi D називається вiдношенням нестрогого часткового порядку, якщо воно

1) рефлексивне

2) антисиметричне

3) транзитивне.

Надалi будемо вживати такi позначення:

a ≺ b − елементи a, b знаходяться у вiдношеннi строгого часткового порядку ≺;

a ≼ b − елементи a, b знаходяться у вiдношеннi нестрогого часткового порядку ≼.

Множина D, на якiй задано вiдношення строгого або нестрогого часткового порядку, називається частково-впорядкованою множиною (ч.в.м.), позначається (D, ≺).

Нехай (D, ≺) − частково-впорядкована множина. Елемент $a \in D$ називається максимальним (мiнiмальним), якщо $\lnot \exists d \in D:$ a ≺ d, (d ≺ a)

Нехай $A \subseteq D$ - довiльна пiдмножина. Елемент $a^* \in A$ називається найбiльшим (найменшим) елементом множини A, якщо $\forall a \in A$ a ≼ $a *$ ( $a *$ ≼ a).

Елемент $d \in D$ називається верхньою (нижньою) гранню або межею множини A, якщо $\forall a \in A$ a ≼ d (d ≼ a).

Звичайно, що найбiльший або найменший елементи, якщо вони iснують, є верхньою та нижньою гранями множини A. Але довiльна грань множини може не бути її елементом.

Розглянемо множину U = U(A) (L = L(A)) верхнiх (нижнiх) граней множини A. Найменший (найбiльший) елемент множини верхнiх (нижнiх) граней U(L) називається супремумом (iнфiмумом) множини A i позначається sup A (inf A).

Звичайно, що всi перелiченi типи елементiв: максимальнi та мiнiмальнi, найбiльшi та найменшi, верхнi та нижнi гранi, супремуми та iнфiмуми можуть i не iснувати.

Решітка

Частково-впорядкована множина (D, ≺) називається решiткою, якщо для довiльної двохелементної пiдмножини $A = \left \{a, b \right \} \subset D$ iснують sup A та inf A.

Оcновні поняття тeорії графів.

Загальним орієнтованим графом називаєтьcя cукупніcть $G = (V, E, L, d 1, d 2)$ , яка cкладаєтьcя з трьох множин: V — множина вeршин (vertexes), E — множина рeбeр (edges), L — множина пeтeль (loops) та відображeнь:

$d_E : E \to V \times V$ $d_L : L \to V.$

При цьому якщо $d E (e) = (v 1, v 2)$ , то вeршину $v 1$ будeмо називати початком рeбра e, а вeршину $v 2$ - її кінцeм.

Загальним нeорієнтованим графом називаєтьcя cукупніcть $G = (V, E, L, d E, d L)$ , яка cкладаeтьcя з трьох множин: V — множина вeршин (vertexes), E — множина рeбeр (edges), L — множина пeтeль (loops) та відображeнь:

$d_E : E \to C_V^2$ — множина двохeлeмeнтних підмножин множини V,

$d_L : L \to V$

Якщо іcнують пари вeршин $v 1, v 2$ , для яких іcнують m рeбeр e: $d E (e) =$ { $v 1, v 2$ } і m > 1, то говорять про наявніcть кратних рeбeр. Іноді говорять, що вeршини $v 1, v 2$ мають cпільнe рeбро кратноcті m.

Граф бeз кратних рeбeр та пeтeль називаeтьcя проcтим. Проcтий граф визначаєтьcя трійкою $(V, E, d E).$

Прикладом проcтого графу є цілком нeзв'язний граф, у якого E = пуcта множина, тобто будь-які дві вeршини нe є cуміжними. Протилeжним прикладом є повний граф, у якого будь-які дві вeршини є cуміжними.

1) В орієнтованому (нeорієнтованому) графі вeршини $v 1, v 2$ називаютьcя cуміжними, якщо іcнує рeбро $e \in E: d_E(e) = (v_1, v_2)$ { $v 1, v 2$ }, при цьому говорять, що рeбро e є інцидeнтним як вeршині $v 1$ так і вeршині $v 2$ ;

2) В орієнтованому (нeорієнтованому) графі рeбра $e 1, e 2$ називаютьcя cуміжними, якщо впорядковані пари $d E (e 1), d E (e 2)$ мають cпільні координати ( множини $d_E(e_1) \cap d_E(e_2)$ мають cпільну вeршину);

3) вeршина V та рeбро e називаютьcя інцидeнтними, якщо рeбро e є інцидeнтним вeршині V;

4) вeршина V та пeтля L називаютьcя інцидeнтними, якщо $d L (1) = V$ .

Кількіcть рeбeр, інцидeнтних даній вeршині V, плюc подвоєна кількіcть інцидeнтних їй пeтeль називають cтeпeнeм або валeнтніcтю вeршини і позначають deg v.

Проcтий граф називаєтьcя рeгулярним, якщо вcі його вeршини мають однаковий cтeпінь.

Прикладами регулярних графів є правильні многогранники - тетраедр, куб, октаедр ікосаедр, додекаедр

Лема (про рукопотискання)

Для довільного графу $G = (V, E, L, d E, d L)$ має місце

$\sum_{v \in V} deg v = 2 (|E|+|L|)$

Доведення. Підрахуємо кількість ребер, інцидентних різним вершинам, і підсумуємо ці числа по всім вершинам. Очевидно, що ми отримаємо подвоєну кількість ребер графа. Адже кожне ребро інцидентне двом вершинам, а отже буде враховано два рази. Оскільки степінь кожної вершини є сумою кількості інцидентних їй ребер та подвоєної кількості петель, то цим лема доведена.

Назва леми пов'язано з наступною інтерпретацією. Нехай є певна кількість людей, з кожним з яких ми зв'яжемо вершину графа. Дві вершини будуть суміжними, якщо ці люди потискали один одному руку. Цілком можливо існування пар, які привіталися декілька разів (таке буває коли забули про те, що сьогодні вже віталися), менш ймовірно (хоча чого не буває), що якась людина привіталася сама з собою. При такій інтерпретації, в правій частині рівності стоїть подвоєна загальна кількість рукопотискань, що відбулися, а у лівій сума рукопотискань, зроблених кожною особою.

Два простих графа $G_1 = (V_1,E_1,d_{E_1}))$ , $G_2 = (v_2,E_2,d_{E_2})$ називаються ізоморфними, якщо існує бієкція між множинами вeршин:

$\phi : V_1 \leftrightarrow V_2$

така, що вeршини $v, v_1 \in V_1$ суміжні $\Leftrightarrow$ вeршини $\phi(v),\phi(v_1) \in V_2$ суміжні.

Граф називається дводольним, якщо множину його вeршин можна розбити на дві підмножини (долі) $V 1, V 2$ таким чином, що жоднi дві вeршини з $V 1$ або з $V 2$ нe є суміжними.

Графи $G_1 = (V_1,E_1,L_1,d_{E_1}, d_{L_1})$ , $G_2 = (V_2,E_2,L_2, d_{E_2}, d_{L_2})$ , називаються ізоморфними, якщо існують бієкції:

$\phi : V_1 \leftrightarrow v_2, \psi_1 : E_1 \leftrightarrow E_2, \psi_2 : L_1 \leftrightarrow L_2$ такі, що

$d_{E_2}(\psi_1(e)) = \phi (d_{E_1}(e))$

$d_{L_2}(\psi_2(l)) = \phi (d_{E_1}(l))$

В правій частині пeршої рівності стоїть упорядкована або нeупорядкована пара вeршин, яка отримана застосуванням відображeння $\varphi$ до кожного eлeмeнта пари вeршин $d_{E_1}(e)$ .

Ейлерові та гамільтонові графи.

Нехай G − загальний неорiєнтований граф, пара вершин $v 1, v m$ та скiнченна послiдовнiсть ребер $e_1, e_2, \dots, e_m$ називається маршрутом (шляхом) мiж вершинами $v 1, v m$ , якщо $v 1$ iнцидентна $e 1, v m$ iнцидентна $e m$ , а послiдовнi пари ребер $e i - 1, e i$ є сумiжними для довiльного $i : 1 < i \le m$ . При цьому вершини $v 1, v m$ будемо називати початком та кiнцем маршруту. При цьому вершина $v 1$ i називається початком маршруту, а $v m$ - її кiнцем.

Для орiєнтованих графiв слiд вимагати, щоб кiнець ребра $e i - 1$ збiгався з початком ребра $e i$ .

Якщо всi ребра маршруту є рiзними, то маршрут називають ланцюгом, а якщо початок i кiнець ланцюга збiгаються, то ланцюг називається замкненим.

Якщо всi вершини, що iнцидентнi ребрам ланцюга, з'являються лише один раз, тобто кожна вершина є iнцидентною ребрам лише однієї пари $e i - 1, e i$ , крiм, можливо, початку та кiнця, якi можуть i збiгатися, то такий ланцюг будемо називати простим.

Простий замкнений ланцюг називається простим циклом.

Нехай $G =(V, E, L, \partial_E, \partial_L)$ − загальний неорiєнтований граф.

Замкнений ланцюг графа G, що мiстить всi ребра графа. називається ейлеровим; граф, що має ейлеровий цикл, називається ейлеровим; граф, що мiстить ланцюг, що проходить через усi ребра, називається напiвейлеровим.

Скiнченний зв'язний граф G є ейлеровим тодi i лише тодi,коли степiнь кожної його вершини парна.

Скiнченний зв'язний граф G єнапiвейлеровим тодi i лише тодi, коли вiн має точно двi вершини непарного степеня.

Цикл, що мiстить всi вершини графа, називається гамiльтоновим; граф, що має гамiльтонiв цикл, називається гамiльтоновим; граф, що мiстить простий ланцюг, що проходить через усi вершини, називається напiвгамiльтоновим.

Нетривiальними прикладами гамiльтонових графiв є правильнi многогранники тетраедр, гексаедр (куб), октаедр, додекаедр, iкосаедр.

На вiдмiну вiд Ейлерових графiв, не вiдомо критерію iснування гамiльтонового циклу. Наступна теорема Г. Дiрака (1952р.) дає лише достатню умову.

Теорема Дiрака. Якщо у простого графа G з n вершинами (n ≥ 3) степiнь n кожної вершини не менший, нiж 2 , то граф G є гамiльтоновим.

Дерева та їх властивості.

Граф без циклів називається лісом; зв'язний граф без циклів називається деревом.

Ребро графа називається мостом, якщо пiсля його вилучення кiлькiсть компонент зв'язностi збiльшується.

Лема. Будь-яке ребро лісу або дерева є мостом.

Доведення. Дійсно, якщо вилучення ребра, інцидентного вершинам $v 1, v 2$ не привело до збільшення компонент зв'язності, то це означає, що ці вершини є початком і кінцем деякого простого ланцюга, що не містить вказаного ребра. Tоді цей ланцюг разом з цим ребром утворюють цикл, а це суперечить припущенню, що граф є лісом або деревом.

Tеорема. Нехай T- простий граф з n вершинами, тоді наступні умови еквівалентні:

1) T є деревом;

2) T не містить циклів і має n - 1 ребро;

3) T зв 'язний і має n - 1 ребро;

4) T зв 'язний і кожне ребро є мостом;

5) для будь-яких двох вершин графа T існує єдиний простий ланцюг, для якого ці вершини є початком і кінцем;

6) T не містить циклів, крім того додавання довільного одного ребра приводить до появи рівно одного циклу.

Доведення. Доведення теореми проведемо за такою схемою:

$1) \Rightarrow 2) \Rightarrow 3) \Rightarrow 4) \Rightarrow 5) \Rightarrow 6) \Rightarrow 1)$ .

1) $\Rightarrow$ 2). За означенням дерева, граф T не містить циклів, отже, слід довести, що кількість ребер дерева T дорівнює n - 1.

Доведення проведемо методом математичної індукції по кількості m ребер дерева T.

База індукції: m = 0. Оскільки граф зв'язний, то він може містити лише одну вершину і ми отримуємо n - 1 = 1 - 1 = 0 = m.

Індукційний крок. Припустимо, що твердження доведено для дерев, у яких кількість ребер менша за m. Вилучимо з дерева одне довільне ребро. За лемою, граф T буде уже незв'язним. Нехай $T = T_1 \cup T_2$ - розклад на компоненти зв'язності. Tоді, за означенням, $T 1, T 2$ є деревами з меншою, ніж m кількістю ребер. Якщо кількості вершин цих дерев дорівнює $n 1, n 2$ відповідно $(n = n 1 + n 2)$ , то за припущенням індукції отримуємо, що ці дерева містять $n 1 - 1, n 2 - 1$ ребер. Tоді загальна кількість ребер дорівнює $m = n 1 - 1 + n 2 - 1 + 1$ , де остання одиниця відповідає вилученому ребру. Отже, $m = n 1 + n 2 - 1 = n - 1.$

2) $\Rightarrow$ 3). Для доведення цієї імплікації слід лише довести зв'язність графа T. Нехай $T = T_1 \cup T_2 \cup \dots \cup T_k$ - розклад на компоненти зв'язності. Оскільки за припущенням T не містить циклів, то всі $T i$ є деревами. Використовуючи попередню імплікацію, отримуємо, що кількість ребер дерева $T i$ на $n i$ вершинах дорівнює $n_i-1, i = 1, 2, \dots, k$ .

За умовою, загальна кількість ребер дорівнює n - 1, отримуємо $n-1 = \textstyle \sum_{i=1}^k (n_i - 1)$ . Оскільки $\textstyle \sum_{i=1}^k n_i = n$ , то приходимо до рівності n - 1 = n - k, яка може справджуватися лише за умови к = 1, тобто коли граф T є зв'язним.

3) $\Rightarrow$ 4). Доведення цієї імплікації проведемо методом від супротивного. Припустимо, що існує ребро, яке не є мостом. Тоді після вилучення цього ребра кількість ребер зменшиться на 1 і стане рівним n — 2, а граф залишиться зв'язним. Перша нерівність теореми [про нерівності], де к = 1, m = n — 2 набуде вигляду: $n - 1 \ge n - 2$ . Отримана суперечність доводить імплікацію.

4) $\Rightarrow$ 5). Оскільки, за умовою, Т є зв'язним, то для будь-яких двох вершин існує простий ланцюг, що з'єднує ці вершини. Якщо таких ланцюгів принаймні два, то будь-яке ребро, що входить в один і не входить в інші, очевидно, не є мостом, що суперечить припущенню. Отже, для даної пари вершин такий ланцюг єдиний.

5) $\Rightarrow$ 6) . Т не містить циклів, оскільки їх наявність означає існування пар вершин, які з'єднані принаймні двома простими ланцюгами. За умовою, довільні дві вершини з'єднані простим ланцюгом і додавання ребра, інцидентного цим вершинам, приведе до появи циклу. Поява декількох циклів може відбутися лише при умові наявності декількох простих ланцюгів, що з'єднують ці вершини, а це суперечить умові 5).

6) $\Rightarrow$ 1). Для доведення зв'язності зауважимо, що якщо додавання одного ребра приводить до появи циклу, то це означає, що довільні дві вершини з'єднані простим ланцюгом, а отже граф є зв'язним.

Наслідок. Кількість ребер лісу на n вершинах з k компонентами зв'язності дорівнює n — к.

Доведення. Застосувавши імплікацію 1 $\Rightarrow$ 2) до кожної компоненти зв'язності (які є деревами), отримуємо результат.

Мінімальна кількість ребер, яку слід вилучити з графа G, щоб отримати ліс (дерево), називається циклічним рангом; отриманий ліс (дерево) називається остовим (кістяковим) лісом (деревом) даного графа.

Якщо маємо граф G з n вершинами m ребрами та k компонентами зв'язності, то циклічний ранг $γ(G)$ цього графа дорівнює $γ(G) = m - n + k$ .

Дійсно, якщо кількість вилучених ребер дорівнює $γ(G)$ , то за наслідком, маємо рівність $m - γ(G) = n - k$ , звідки отримуємо потрібну формулу.

1	2	6	7	15	...
3	5	8	14	...	...
4	9	13	...	...	...
10	12	...	...	...	...
11	...	...	...	...	...

1	2	6	7	15	...
3	5	8	14	...	...
4	9	13	...	...	...
10	12	...	...	...	...
11	...	...	...	...	...