Понятие мощности множества. Сравнение множеств по мощности. Теорема Кантора-Бернштейна

Мощность: Два множества А и В называются эквивалентными или имеющими одинаковую мощность, если между их элементами можно установить взаимооднозначное соответствие.

А~В

Билет 9

Гомеоморфизм графов. Теорема Понтрягина – Куратовского.

Гомеоморфизм. Графы переводимые друг в друга конечным числом подразделения и слияния рёбер называется – гомеоморфными.

Оношение гомеоморфизма есть отношение эквивалентности, заданное на множестве всех неор. Графов.

1)GpG - рефлексивность

2) р => р – симметричность

3) р и р => р – транзитивность

Критерий планарности.

Теорема Пантрягина-Куратовского.

Для того чтобы граф G имел плоскую ориентацию, необходимо и достаточно, чтобы любой его подграф не был гомеоморфен не одному из графов К5 и К3,3.

Билет 10

Отношения порядка. Основные свойства. Частично упорядоченные множества. Линейно упорядоченные множества.

Частичный порядок: отношение, в котором одновременно выполняется рефлексивность, антисимметричность и транзитивность, называется отношением частичного порядка.

Линейный порядок: отношение частичного порядка называется отношением линейного порядка, если любые 2 элемента множества Х сравнимы между собой, т.е. для

Упорядоченные множества: Множество Х с заданным на нём частичным (линейным) порядком называется частично (линейно) упорядоченным.

Пусть Х – частично упорядоченное множество.

х - называется минимальным (максимальным) элементом множества Х.

Если для

2)a<xóa=x

3)x<a=>a- наибольший элемент

4)a<x=>a – наименьший элемент.

 

Билет 10

Раскраска графов. Теорема о пяти красках. Гипотеза четырех красок.

Хроматическое число графа G — минимальное число цветов, в которые можно раскрасить вершины графа G так, чтобы концы любого ребра имели разные цвета. Обозначается χ(G).

 

Если наибольшая из степеней вершин графа равна Р, то этот граф Р+1 -раскрашиваем.

K-раскрашиваемый граф — граф, хроматическое число которого не превосходит K. То есть его вершины можно раскрасить K разными цветами так, что у любого ребра концы будут разного цвета.

K-хроматический граф — граф, хроматическое число которого равно K. То есть вершины графа можно раскрасить K цветами так, что у любого ребра концы будут разного цвета, но так раскрасить K − 1 цветами — уже нельзя.

Билет 11

Отображения, сохраняющие порядок. Изоморфизм между частично упорядоченными множествами

 

Частичный порядок: отношение, в котором одновременно выполняется рефлексивность, антисимметричность и транзитивность, называется отношением частичного порядка.

Линейный порядок: отношение частичного порядка называется отношением линейного порядка, если любые 2 элемента множества Х сравнимы между собой, т.е. для

Упорядоченные множества: Множество Х с заданным на нём частичным (линейным) порядком называется частично (линейно) упорядоченным.

 

Два частично упорядоченных множества называются изоморфными, если между ними существует изоморфизм, то есть взаимно однозначное соответствие, сохраняющее порядок. (Естественно, что в этом случае они равномощны как множества.) Можно сказать так: биекция называется изоморфизмом частично упорядоченных множеств А и В, если

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

 

Теорема

Конечные линейно упорядоченные множества из одинакового числа элементов изоморфны.

 

Билет 11

Плоские и планарные графы. Теорема Эйлера.

Планарный граф — граф, который может быть изображен на плоскости без пересечения ребер.

 

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

 

Непланарны К5(полный) и К33

 

Теорема Эйлера

Вершины – рёбра + грани = 2

Докво по индукции (добавл 1 грань, r ребер и r-1 вершину)

 

Билет 12