Користувач:Kanzat/ОДА

Основні поняття теорії множин. Парадокс Рассела. Характеристичні функції (предикати.) Операції над множинами та їх властивості. Закони де Моргана. Декартів добуток множин. Поняття функції визначеної на множині. Поняття ін’єкції, сюр’єкції, бієкції.

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

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

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

Для позначення множини будемо вживати великі літери А, В, С, 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,....

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

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

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

$R\subseteq D_{1}\times D_{2}\times ...\times D_{n}$

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

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

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

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

• Об’єднання множин $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}$ то $\alpha (i)$ називається проекцією $\alpha$ на множину $A_{i}$ (позначається $Pr_{i}(\alpha )$ ) або i-ю координатою елемента $\alpha$

Для довільної підмножини $\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}\neq x_{2}\Rightarrow f(x_{1})\neq 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}|$

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

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

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

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

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

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

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

Нехай $\Omega$ — скінченна n—елементна множина. Будь-яка k—елементна підмножина множини $\Omega$ називаеться k—елементною комбінацією, визначеною на множині $\Omega$. Число таких комбінацій позначається $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$ така, що $|\sigma ^{-1}(i)|=n_{i},i=1,2,3,...,k$. Число таких перестановок з повтореннями будемо позначати $P(n_{1},n_{2},...n_{k})$.

Інше означення: Перестановкою з повтореннями з $n$ елементів по $n_{1},n_{2},...,n_{k}$ називається впорядкована множина, яка складається з $n_{1}$ елементів першого типу, $n_{2}$ елементів другого типу, ... , $n_{k}$ елементів $k$-го типу $(n_{1}+n_{2}+...+n_{k})=n$.

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

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 с возвращением и с учётом порядка равняется .

Приклад. При A={a, b, c} перестановками з повтореннями складу (1, 0, 2) є послідовності (a,c,c), (c,a,c), (c,c,a), складу (1, 1, 1) – (a,b,c), (a,c,b), (b,a,c), (b,c,a), (c,a,b), (c,b,a).

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

Загальна кількість різних наборів при виборі 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})$. Цим формула доведена.

Порівняння нескінченних множин. Рівнопотужні множини. Зліченні та незліченні множини, основні теореми. Зліченність множини раціональних чисел та незліченність множини двійкових послідовностей. Порівняння потужностей множини та її булеана. Поняття про кардинальні числа.

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

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

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

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

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

$\phi :A\to B$

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

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

$\phi :A\leftrightarrow B$

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

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

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

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

$|A|\leq |B|\wedge |B|\leq |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\leq i<jB_{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_{1n}$
$b_{21}$	$b_{22}$	$b_{23}$	$\dots$	$b_{2n}$
$\dots$	$\dots$	$\dots$	$\dots$	$\dots$
$b_{n1}$	$b_{n2}$	$b_{n3}$	$\dots$	$b_{nn}$
$\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$ всіх поганих елементів. Оскільки $\phi$ — бієкція, то існує елемент $x=\phi ^{-1}(Bad)\in A$, тобто для якого $x\leftrightarrow Bad$.

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

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

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

Дійсно, за означенням, число 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}|$ будується таким чином ${n}\to b$; кожному натуральному числу n ставиться у відповідність одноелементна множина {n}. Отже, маємо$|N|\leq |2^{N}|$. Покажемо тепер, що $|N|\neq |2^{N}|$. Доведення проведемо від супротивного, застосуванням діагонального методу Кантора. Припустимо, що існує бієкція $|N|\leftrightarrow |2^{N}|$, тоді маємо нумерацію послідовностей:

1	$b_{11}$	$b_{12}$	$b_{13}$	$\dots$	$b_{1n}$
2	$b_{21}$	$b_{22}$	$b_{23}$	$\dots$	$b_{2n}$
...	$\dots$	$\dots$	$\dots$	$\dots$	$\dots$
n	$b_{n1}$	$b_{n2}$	$b_{n3}$	$\dots$	$b_{nn}$
...	$\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$ всіх поганих елементів. Оскільки $\phi$ — бієкція, то існує елемент $x=\phi ^{-1}(Bad)\in A$, тобто для якого $x\leftrightarrow Bad$.

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

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

Природне бажання вважати потужність числом приводить до поняття кардинальних чисел. Кількість елементів в зліченній множині позначається кардинальним "числом" $\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}$

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

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

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

Основними способами визначення б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}$. Якщо $\sigma =(1,2)$ − перестановка координат, то для зображення графа вiдношення $R^{\sigma }$ слiд змiнити напрямок дуг на протилежний.

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

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

Нехай $\pi _{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^{\sigma }$ мiж множинами $D_{i_{1}},D_{i_{2}},\dots ,D_{i_{n}}$, яке складається з таких наборiв $(d_{i_{1}},d_{i_{2}},\dots ,d_{i_{n}})$, що пiсля зворотньої перестановки координат $\sigma ^{-1}$ отриманий набiр належить R, тобто $(d_{i_{1}},d_{i_{2}},\dots ,d_{i_{n}})^{\sigma ^{-1}}\in R$.

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

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

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

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

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

Для вiдношень еквiвалентностi замiсть запису $(d_{1},d_{2})\in R$ вживають запис $d_{1}\sim 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\sim d^{*},b\sim d^{*}$. Враховуючи симетричнiсть вiдношення, $a\sim d^{*},d^{*}\sim 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:\;\;(aRb\land bRc\Rightarrow aRc)$ (транзитивність),

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Б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_{E},d_{L})$, яка 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}degv=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\leq 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\geq n-2$. Отримана суперечність доводить імплікацію.

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

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

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

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

Доведення

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

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

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

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