В.А. Носов - Комбинаторика и теория графов

МИНИСТЕРСТВО ОБЩЕГО И ПРОФЕССИОНАЛЬНОГООБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИМосковский государственный институтэлектроники и математики (Технический университет)В.А. НосовКомбинаторика и теория графовУтверждено Редакционно-издательскимсоветом институтав качестве учебного пособияМосква, 1999УДК 519.1Носов Валентин АлександровичКомбинаторика и теория графовУчебное пособиеПособие содержит изложение основ комбинаторики и теории графов всоответствии с программой семестрового курса для студентов младших курсов,обучающихся по специальности "Прикладная математика"Рецензенты:Кафедра математической теории интеллектуальныхсистем МГУ им.

М.В. Ломоносова(зав. кафедрой профессор Кудрявцев В.Б.)профессор Строгалов А.С. (РГГУ)Электронная версия подготовлена к публикации на web-сервере "Интеллектуальные системы" (http://intsys.msu.ru) кафедры Математической теорииинтеллектуальных систем механико-математического факультета МГУ имениМ.В. ЛомоносоваВсе вопросы использования пособия просьба согласовывать с авторомЭлектронный адрес автора - vnosov@intsys.msu.ru1ОглавлениеОГЛАВЛЕНИЕ ......................................................................................................... 2ВВЕДЕНИЕ................................................................................................................ 0ГЛАВА I.

ВВЕДЕНИЕ В КОМБИНАТОРИКУ.................................................. 1§ 1. МНОЖЕСТВА. ОТОБРАЖЕНИЯ. .......................................................................... 11. Множества.....................................................................................................

12. Отображения................................................................................................. 33. Алгебра множеств. ........................................................................................ 5Упражнения ........................................................................................................ 6§ 2. ПРИНЦИПЫ ПЕРЕЧИСЛЕНИЯ И ПРИМЕРЫ...........................................................

9Элементарные тождества. ............................................................................. 9Упражнения. ..................................................................................................... 17§ 3. БИНАРНЫЕ ОТНОШЕНИЯ.................................................................................. 181. Определения. .................................................................................................

182. Операции над отношениями. ...................................................................... 193. Свойства операций над отношениями. ..................................................... 21Упражнения. ..................................................................................................... 22§ 4.

СПЕЦИАЛЬНЫЕ КЛАССЫ БИНАРНЫХ ОТНОШЕНИЙ.......................................... 241. Отношения эквивалентности. ................................................................... 242. Отношения толерантности....................................................................... 263. Отношения частичного порядка................................................................ 27Упражнения. ..................................................................................................... 30§ 5.

ЭЛЕМЕНТЫ ТЕОРИИ ПОДСТАНОВОК. ............................................................... 32Упражнения. ..................................................................................................... 37§ 6. ПОРОЖДЕНИЕ СОЧЕТАНИЙ И ПЕРЕСТАНОВОК................................................. 38ГЛАВА II. МЕТОДЫ ПЕРЕЧИСЛЕНИЯ ......................................................... 43§ 1. МЕТОД ВКЛЮЧЕНИЯ-ИСКЛЮЧЕНИЯ. ...............................................................

43§ 2. МЕТОД РЕКУРРЕНТНЫХ СООТНОШЕНИЙ ......................................................... 51§ 3. ПРОИЗВОДЯЩИЕ ФУНКЦИИ И ФОРМУЛЫ ОБРАЩЕНИЯ .................................... 56§ 4. ОБРАЩЕНИЕ МЕБИУСА. .................................................................................. 64§ 5. ПЕРМАНЕНТЫ И ИХ ПРИМЕНЕНИЕ К ПЕРЕЧИСЛИТЕЛЬНЫМ ЗАДАЧАМ. ........... 68УПРАЖНЕНИЯ ......................................................................................................... 74ГЛАВА III.

ВВЕДЕНИЕ В ТЕОРИЮ ГРАФОВ............................................... 76§ 1. ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ГРАФОВ. .......................................................... 76§ 2. ЭЙЛЕРОВЫ ГРАФЫ. .......................................................................................... 81§ 3. ГАМИЛЬТОНОВЫ ГРАФЫ.................................................................................. 85§ 4. КРАТЧАЙШИЕ ПУТИ......................................................................................... 89§ 5. ДЕРЕВЬЯ. ......................................................................................................... 91§ 6.

ПЛАНАРНЫЕ ГРАФЫ ........................................................................................ 99§ 7. РАСКРАСКА ГРАФОВ ...................................................................................... 103§ 8. ПОТОКИ В СЕТЯХ. .......................................................................................... 105УПРАЖНЕНИЯ.

...................................................................................................... 111ЛИТЕРАТУРА ...................................................................................................... 1122ВВЕДЕНИЕНастоящее пособие подготовлено на основе лекций по одноименному семестровому курсу, читаемому в 2-м семестре для студентов, обучающихся по специальности"Прикладная математика".В настоящее время имеется ряд обстоятельных руководств как по комбинаторике, так и по теории графов, однако, по мнению автора, ощущается потребность в небольшом пособии, охватывающем все темы курса, ориентированном на читателя соскромной математической подготовкой.Предлагаемое пособие отличается от известных руководств такого типа двумясущественными обстоятельствами.

Изложение организуется так, чтобы кроме необходимых сведений дать материал, относящийся к приложениям и к развитию изучаемойпроблематики. Уделено повышенное внимание конструктивному направлению, связанному с разработкой комбинаторных и графических алгоритмов.Список литературы представлен в конце пособия. Нумерация утверждений иссылок независима в каждом параграфе.Знаки и означают начало и конец доказательства.Автор выражает признательность всем прочитавшим рукопись пособия и сделавшим свои замечания по его улучшению.ГЛАВА I. ВВЕДЕНИЕ В КОМБИНАТОРИКУ.§ 1. Множества.

Отображения.1. Множества.Основные понятия теории множеств будут играть в дальнейшем существеннуюроль. Понятие “множество” является первичным и неопределяемым. Предметы (объекты), составляющие данное множество, называются его элементами. Тот факт, что элемент x принадлежит множеству A записывается так: x ∈ A, в противном случае пишем x∈ А. Для однозначного описания некоторого множества мы будем пользоваться следующими способами:а) давать список элементов, входящих в данное множество. Если множество Асостоит из элементов a1, … , an то будем писать А = { a1, … , an }.б) указывать общее свойство элементов, принадлежащих множеству А.

Будемписать А = {x P(x)}, что означает “множество всех x, таких, что выполнено P(x)”. ЗдесьP(x) - означает свойство, характеризующее в точности все элементы множества А.в) указывать порождающую процедуру, т.е. способ получения элементов множества А.г) указывать разрешающую процедуру, т.е. правило решения вопроса, верно лиx ∈ А для любого x.Если каждый элемент множества А является элементом множества B, то А называетсяподмножеством множества B.

(обозначение А⊆B). Два множества А и B называютсяравными, если справедливо А⊆B и B⊆А. (обозначение А = B).Объединение множеств А и B(обозначение - А U B ) есть множество, состоящее из тех итолько тех элементов, которые принадлежат хотя бы одному из множеств А или B, т.е.A U B = {x x ∈ A или x ∈ B}Аналогично определяется объединение произвольной системы множеств A1, … , An:A1 U …U A n = {x x ∈ Ai для некоторого i ∈ 1, n }Пересечением множеств А и B (обозначение: А I B ) называется множество, состоящееиз тех и только тех элементов, которые принадлежат обоим множествам А и B, т.е.1AI B = {x x ∈ A и x ∈ B}Аналогично определяется пересечение произвольной системы множеств A1, … , An:A1I K I A n = {x x ∈ Ai для всех i ∈ 1, n }Разностью множеств А и B (обозначение: А\B) называется множество, состоящее из тех и только тех элементов А, которые не принадлежат B, т.е.A\B = {x x ∈ A и x ∈ B}Если А - подмножество множества Е, то дополнение множества А в множестве Е (обозначение: A или CEA) есть множество, состоящее из тех и только тех элементов Е, которые не принадлежат А, т.е.A = {x x ∈ E и x ∈ A}Множество, не содержащее элементов, называется пустым множеством и обозначается ∅.Примем следующее соглашение об обозначениях: Высказывание “из P следует Q” будемобозначать P ⇒ Q.

Если P ⇒ Q и Q ⇒ P, то используем обозначение P ⇔ Q, что эквивалентно высказыванию “P справедливо тогда и только тогда, когда справедливо Q”. Высказывание “для всех x справедливо P(x)” будем обозначать ∀x P(x), высказывание “существует x, такое, что справедливо P(x)” будем обозначать ∃x P(x). Булеан множества А(обозначение: B(А)) есть множество всех подмножеств множества А, т.е.B(A) = {x x ⊆ A}Прямое (декартово) произведение непустых множеств А и B(обозначение: А×B) определяется как множество всех упорядоченных пар вида (x1,x2), где x1 ∈ А, x2 ∈ B. Для упорядоченных пар (x1,x2), ( x1′ , x ′2 ) справедливо:(x1,x2) = ( x1′ , x ′2 ) ⇔ x1 = x1′ , x2 = x ′2 .Аналогично определяется прямое произведение системы множеств A1, … , An:A1× … × An { (x1, … , xn) x1 ∈ A1, … , xn ∈ An }причем (x1, … , xn) = ( x1′ , … , x ′n ) ⇔ xi = x1′ , ∀ i ∈ 1, nЕсли A1 = … = An = A , то A1×… ×An обозначим An.22.

Отображения.Пусть А и B непустые множества. Если каждому элементуx ∈ А ставится всоответствие единственный элемент y ∈ B, то говорят, что задано отображение F множества А в множество B(обозначение: F: А → B). Говорят также, что задана функция F собластью определения А и областью значения B. При этом элемент y называется образом элемента x (обозначение: y = F(x)), а элемент x - прообразом элемента y.