Тема 1. Множества

Тема 1. Множества

Лекция 1.

Цель – познакомить студентов с общими понятиями теории множеств и с разбиением множества на классы.

1.1.  Общие понятия теории множеств

Язык теории множеств. Совокупность элементов, объединённых некоторым признаком, свойством, составляет понятие множество. Например, множество книг в библиотеке, множество студентов в группе, множество натуральных чисел N и т. д.

Запись означает: элемент a принадлежит множеству М, т. е. элемент a обладает некоторым признаком. Аналогично читается: элемент a не принадлежит множеству М.

Множество считается заданным, если или перечислены все его элементы, или указано свойство, которым обладают те и только те элементы, которые принадлежат данному множеству. Само свойство называется характеристическим. В качестве характеристического свойства может выступать указанная для этого свойства порождающая процедура, которая описывает способ получения элементов нового множества из уже полученных элементов или из других объектов. Например, множество всех чисел, являющихся неотрицательными степенями числа 2 , можно задать с помощью порождающей функции по индуктивным правилам:

*  ;

*  если , то .

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

Изображение множеств. Множества удобно изображать с помощью кругов Эйлера.

Множество K на рис. 1.1 называют подмножеством множества М и обозначают . Таким образом, множество K называется подмножеством множества M , если для любого выполняется (т. е. влечёт ).

Необходимо учитывать различие в употреблении знаков включения и принадлежности для множества множеств.

Универсальным называется множество U, состоящее из всех возможных элементов, обладающих данным признаком.

Равными называют два множества A и B, состоящие из одинаковых элементов: .

Число элементов множества A называется мощностью множества и обозначается или .

Множество A можно разбить на классы непересекающихся подмножеств Ai, если:

*  объединение всех подмножеств совпадает с множеством A: ;

*  пересечение любых двух различных подмножеств пусто, т. е. для любых выполняется .

1.2.  Соответствия между множествами. Отображения

Основные понятия. Пары задают соответствие между множествами A и B, если указано правило R, по которому для элемента множества A выбирается элемент из множества B.

Пусть для некоторого элемента a множества A поставлен в соответствие некоторый элемент b из множества B, который называется образом элемента a и записывается . Тогда - прообраз элемента , который обладает свойствами единственности и полноты:

*  каждому прообразу соответствует единственный образ;

*  образ должен быть полным, так же как полным должен быть и прообраз.

Образ множества A при соответствии R называется множеством значений этого соответствия и обозначается , если состоит из образов всех элементов множества A.

Прообраз множества B при некотором соответствии R называют областью определения этого соответствия и обозначают , т. е. ; является обратным соответствием для R.

Задание отображений. Для описания соответствий между множествами используют понятие отображения (функции) одного множества на другое.

Для задания отображения необходимо указать:

*  множество, которое отображается (область определения данного отображения, часто обозначается );

*  множество, в (на) которое отображается данная область определения (множество значений этого отображения, часто обозначается );

*  закон или соответствие между этими множествами, по которому для элементов первого множества выбраны элементы из второго множества.

При записи подразумевается, что отображение f определено всюду на A, т. е. A – полный прообраз отображения f, хотя для B такое свойство полноты не подразумевается. Однозначным называется отображение, где каждому аргументу поставлено в соответствие не более одного образа.

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

Для задания отображения множеств табличным способом принято строить таблицу, в которой первую строку составляют элементы области определения, а вторую строку – их образы, т. е. элементы вида при отображении , где (табл. 1.1).

Таблица 1.1

Табличное задание отображения

x	a1	a2	…	an	…
g(x)	g(a1)	g(a2)	…	g(an)	…

Графическое представление отображения связано со стрелочными схемами (диаграммами или графами).

Отображения и называются равными, если .

Виды отображений. По мощности однозначные отображения делятся на сюръективные и инъективные (рис. 1.2).

 

Отображение множества А на множество В, при котором каждому элементу множества В соответствует единственный элемент множества А, называется взаимно-однозначным соответствием между двумя множествами, или биекцией.

Пусть множество А отображается взаимно-однозначно на множество В, т. е. . Тогда отображение , при котором каждому элементу множества В ставится в соответствие его прообраз из множества А, называется обратным отображением для f и записывается или .

Если между элементами множеств установлено взаимнооднозначное соответствие, то эти множества равносильны, равномощны, или эквивалентны.

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

Распространённая ошибка: запись вида , где знак «×» - умножение в R, не является композицией или суперпозицией этих функций. Дело в том, что произведение функций определено на множестве функций, а выражение обозначает произведение значений каждой из функций в каждой конкретной точке.

Отображение называется тождественным (единичным), если каждому аргументу оно ставит в соответствие себя.

Равенство функций определяется действием их на всех элементах.

1.3. Классификация множеств. Мощность множества

Основной характеристикой множеств является количество элементов, содержащихся в этом множестве.

Число элементов множества М называется его мощностью и обозначается |M|. Множества А и В называются эквивалентными, или равномощными, А ~ В, если между их элементами можно установить взаимно-однозначное соответствие.

Множество, содержащее конечное число элементов, называется конечным. Пустое множество является конечным и имеет мощность, равную нулю, т. е. . Множество, не являющееся конечным, называется бесконечным.

Бесконечное множество, эквивалентное множеству натуральных чисел N, называется счётным. В противном случае бесконечное множество будет несчётным. Множество называется бесконечным, если оно равномощно одному из своих собственных подмножеств.

Булеаном множества М называется множество всех его подмножеств, которое обозначается 2М, т. е. .

Для конечных множеств справедливо утверждение, которое называется основной теоремой о конечных множествах.

Теорема. Любое конечное множество не эквивалентно никакому его собственному подмножеству, кроме самого себя.

Следствие. Всякое непустое конечное множество эквивалентно одному и только одному отрезку натурального ряда чисел .

Счётными являются множество Z целых чисел и Q рациональных чисел. Множество R действительных чисел несчётно.

Всякое бесконечное множество, равносильное множеству действительных чисел, называется множеством мощности континуума (от лат. continuum – непрерывный).

1.4. Кортежи. Декартовы произведения

Слово кортеж переводится с французского cortege как торжественная процессия.

Пару назовём упорядоченным множеством, или перестановкой, из п элементов, если А – конечное множество, состоящее из п элементов, - функция, задающая порядок на А. Кортежем длины п из элементов множества А называется упорядоченная последовательность элементов этого множества, причём на первом месте стоит прообраз единицы: .

Кортежи и называются равными, если они имеют одинаковую длину и их элементы с одинаковыми номерами совпадают, т. е. = , если и для .

Операция, с помощью которой из двух кортежей длиной k и m можно составить новый кортеж длиной k + m, в котором сначала идут подряд элементы первого кортежа, а затем – элементы второго кортежа, называется соединением кортежей.

Конечное множество А, элементами которого являются некоторые символы, называют алфавитом над заданным множеством символов. Алфавит есть кортеж попарно различимых символов, называемых буквами алфавита. Элементы множества Ап принято называть словами длины п в алфавите А.

Кортежи, элементы которых являются только нулями или единицами, называются упорядоченными наборами или векторами.

Каждый такой п-мерный вектор единственным образом определяет вершину куба, построенного на единичных векторах (рис. 1.3).

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

Вектор, состоящий из единиц и нулей, описывает состояние памяти вычислительных машин, причём память может содержать числа, тексты, команды и т. д.

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

Декартово произведение

Декартовым (прямым) произведением множеств называется множество , состоящее из всех кортежей длины п, в которых , где .

Если , то пишут и называют п-й декартовой степенью множества А.

В прямоугольной декартовой системе координат координаты точек являются кортежами.

Изоморфизм

Функция называется бинарной операцией на М. Множества и , где - бинарные операции, соответственно, на множествах М и N, называются изоморфными, если существует биекция , такая, что для любых элементов выполнено условие . В таком случае взаимно-однозначное соответствие s называется представлением множества М во множестве N.

1.5. Отношения. Бинарные отношения и их свойства

Основные понятия. Соответствие между равными множествами А = В называется отношением на данном множестве (А).

Подмножество называется п-местным отношением R на непустом множестве М. При п = 2 отношение R называется бинарным. То есть бинарным отношением между элементами множеств А и В называют любое подмножество R множества и записывают .

Свойства бинарных отношений.

Рефлективность: aRa.

2.  Антирефлективность.

3.  Симметричность любых двух элементов. Отношение R на множестве М называется симметричным, если для любых одновременно справедливо aRb и bRa.

4.  Антисимметричность.

5.  Транзитивность.

6.  Антитранзитивность.

7.  Связность.

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

*  xRx (рефлективность);

*  если xRy, то yRx (симметричность);

*  если xRy, а yRz, то xRz (транзитивность).

Непересекающиеся подмножества, на которые разбивается множество М отношением эквивалентности, называются классами эквивалентности. Множество классов эквивалентности множества А относительно отношения эквивалентности Q называется фактор-множеством и обозначается A \ Q.

Отношение толерантности. Отношение А на множестве М называется отношением толерантности, если оно рефлективно и симметрично.

Отношение порядка. Отношение R называется отношением порядка на множестве М, если оно обладает свойствами свойствами антисимметричности и транзитивности. Для произвольного отношения порядка принято обозначение , означающее предшествование.

Множество М, которое обладает отношением порядка, называется упорядоченным.

Рефлективное (антирефлективное) отношение порядка называют отношением нестрогого (строгого) порядка и обозначают знаком (<).

На множестве М задано отношение полного (частичного) порядка, если сравнимы все (не все) элементы этого множества.

Отношение порядка даёт возможность сравнивать между собой различные элементы множества М. Об упорядоченной паре говорят, что элемент х предшествует элементу у. Если для элемента х не нашлось предшествующего, то он называется минимальным: т. е. не существует элементов у, «меньших», чем х.

Если известно, что А и В – упорядоченные множества с отношениями порядка, аналогичными < и , и , то функция называется монотонной (строго монотонной), если из следует, что ().

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

Проверочная работа № 3 по теме «Отношения»

В – 1

1. Даны множества и . Известно, что .

Составьте отношение и постройте график указанного отношения: .

2. Объясните, будут ли выполнимы свойства отношений на заданном множестве людей и почему: «быть знакомым»?

3. Существует ли взаимно-однозначное соответствие между множеством букв и множеством звуков русского языка?

Проверочная работа № 3 по теме «Отношения»

В – 2

1. Даны множества и . Известно, что .

Составьте отношение и постройте график указанного отношения: .

2. Объясните, будут ли выполнимы свойства отношений на заданном множестве людей и почему: «быть отцом»?

3. Существует ли взаимно-однозначное соответствие между множеством чисел, записанных в арабской и двоичной системах счисления?

Проверочная работа № 3 по теме «Отношения»

В – 3

1. Даны множества и . Известно, что .

Составьте отношение и постройте график указанного отношения: .

2. Объясните, будут ли выполнимы свойства отношений на заданном множестве людей и почему: «поздравлять с праздником»?

3. Существует ли взаимно-однозначное соответствие между множеством чисел и множеством студентов вашей группы?

Проверочная работа № 3 по теме «Отношения»

В – 4

1. Даны множества и . Известно, что .

Составьте отношение и постройте график указанного отношения: .

2. Объясните, будут ли выполнимы свойства отношений на заданном множестве людей и почему: «встречаться»?

3. Существует ли взаимно-однозначное соответствие между словом на русском языке и его значением?

Проверочная работа № 3 по теме «Отношения»

В – 5

1. Даны множества и . Известно, что .

Составьте отношение и постройте график указанного отношения: .

2. Объясните, будут ли выполнимы свойства отношений на заданном множестве людей и почему: «быть другом»?

3. Существует ли взаимно-однозначное соответствие между автором и музыкальным произведением?

Проверочная работа № 3 по теме «Отношения»

В – 6

1. Даны множества и . Известно, что .

Составьте отношение и постройте график указанного отношения: .

2. Объясните, будут ли выполнимы свойства отношений на заданном множестве людей и почему: «быть ровесником»?

3. Существует ли взаимно-однозначное соответствие между названием и музыкальным произведением?

1.7. Элементы комбинаторики

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

Правило суммы.

Задача 1. Сколько человек в группе занимается спортом, если 9 человек занимаются лыжами и плаванием, а 12 человек – плаванием и волейболом, причём в секцию по плаванию ходят 4 человека из группы (рис. 1.4)?

Решение.

Имеем:

Ключевое слово для применения правила суммы – слово или.

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

Пример 2. В колледже есть три варианта занятий по интересам: творческие объединения (ТО), спортивные секции (СС) и научное студенческое общество (НСО). Каждое направление содержит по четыре вида коллективов: ТО – театральный, музыкальный, танцевальный и КВН; СС – лёгкая атлетика, лыжи, спортивные игры и плавание. В состав НСО входят естественно-математическое, гуманитарное, техническое и информационное направления. Сколькими способами студенты могут разнообразить свой досуг в колледже после занятий, выбрав коллектив по интересам?

Решение. Так как надо учесть и три основных направления, и то, что в каждом из них по четыре коллектива, то для подсч1та общего числа вариантов их нужно перемножить: .

Частным случаем правила произведения является число размещений с повторениями для подсчёта кортежей длины k, составленных из элементов множества Х, мощность которого т.

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

Упорядоченные множества (кортежи), состоящие из п различных элементов, называются перестановками (без повторений).

Формула называется рекуррентной и даёт возможность подсчитать число перестановок во множестве из п элементов через подстановки во множестве из элементов.

Размещения (без повторений). Упорядоченное подмножество т элементов (кортеж), составленное из всего множества, содержащего п элементов, называется размещением (без повторений). Число таких размещений обозначается (от фр. arrangement – размещение).

Задача 3. Сколькими способами из различных нечётных цифр можно составить различные трёхзначные цифры?

Решение. Нечётных цифр пять: 1, 3, 5, 7, 9. Тогда количество различных трёхзначных чисел найдём по формуле

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

Сочетаниями из п элементов по т называется неупорядоченное подмножество (выборка), состоящая из т элементов, взятых из множества, состоящего из п элементов. Число сочетаний обозначается (от фр. combinaison – сочетание).

Задача 4. Сколькими способами могут взойти 3 зерна пшеницы, если посажено 7 зёрен?

Решение. По условию задачи порядок в подмножестве из 3 зёрен не важен, поэтому по формуле сочетания имеем:

Перестановки с повторениями. Кортеж, имеющий повторяющиеся элементы, называется перестановкой с повторениями.

Частные случаи

1.  Если , то .

2.  Если , то .

3. Если а , то

Задача 5. Сколькими способами можно расставить белые фигуры на первой линии шахматной доски?

Решение. На первой линии могут находиться король, ферзь, 2 ладьи, 2 коня и 2 слона. Без учёта общепринятых шахматных правил составим кортежи длины 8, имеющие указанный состав (1, 1, 2, 2, 2). Тогда число перестановок с повторениями найдём по формуле

Задача 6. Найти число точек пересечения диагоналей выпуклого п-угольника, если никакие три из них не пересекаются в одной точке.

Решение. Минимальный многоугольник с диагоналями имеет четыре вершины. Если взять любые четыре вершины многоугольника, то через них можно провести две диагонали, пересекающиеся внутри этого четырёхугольника. Другие четыре вершины дадут новую точку пересечения диагоналей. Поэтому число точек пересечения диагоналей многоугольника, а значит и число четвёрок-вершин, можно найти с помощью сочетаний .

Задача 7. Разложить п различных деталей в т ящиков. Сколько различных вариантов таких размещений можно перебрать?

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

Задача 8. Сколько различных двоичных чисел длиной 6 можно записать с помощью цифр 0 и 1?

Решение. Размещаем две цифры (0, 1) на шесть мест, т. е. на каждом из шести мест (т = 6) может быть одна из двух двоичных цифр. Всего таких вариантов будет двоичных чисел: на каждом из шести мест по два варианта цифр.

Задача 9. Сколько проводится матчей в Чемпионате РФ по футболу в премьер-лиге за сезон?

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

1.8. Подстановки

Взаимнооднозначное отображение множества на себя называется подстановкой степени п.

Если прообразы (аргументы) расположены в порядке возрастания (при ), то запись подстановки называют канонической.

Подстановку вида называют тождественной, так как .

Произведение отображений также является подстановкой и называется произведением подстановок и и записывается .

Задача 10. Даны две подстановки: . Привести подстановки к канонической записи и найти их произведение.

Решение. Вторая постановка записана в каноническом виде, первая – нет. Поэтому в верхней строке запишем числа от 1 до 5, а в нижней Т. о., Найдём . Сначала выполняется первая подстановка , а затем вторая , т. е. . Поэтому можно сразу записывать в матрицу: . Аналогично найдём остальные образы: . Теперь найдём а т. е.

В итоге получим .

Натуральной степенью подстановки называется подстановка , т. е. произведение п функций, каждая из которых есть .

Задача 11. Дана подстановка Найти её степени.

Решение.

Тогда очевидно, что и т. д.

Порядком подстановки называется наименьшее натуральное число , такое, что .

Инверсией подстановки называется переставление (рокировка) двух соседних значений в нижнем ряду канонической записи.

Если п – число инверсий, приводящих подстановку к единичной, а функция такова, что , то подстановка называется чётной, если , то подстановка называется нечётной.

Задача 12. Найти число инверсий и чётность подстановки

Решение. Имеем

Тогда , поэтому т. е. подстановка чётная.

Одна инверсия меняет чётность подстановки и знак функции .

Любая перемена и местами называется транспозицией.

Число чётных и нечётных подстановок п-й степени одинаково и равно .

Выражение называется симметричным по своим переменным, если любая подстановка (где - множество подстановок п-й степени) оставляет значение F неизменным: .

Задача 13. Пятьдесят лучших студентов колледжа наградили за успехи поездкой в Англию и Германию. Из них 5 не владели ни одним разговорным иностранным языком, 34 знали английский язык и 27 – немецкий. Сколько студентов владело двумя разговорными иностранными языками?

Решение. Введём обозначения множеств:

Е – множество студентов, не владеющих ни одним иностранным языком;

А – множество всех студентов, ;

В – множество студентов, владеющих английским языком, ;

С – множество студентов, владеющих немецким языком, ;

D – множество студентов, владеющих английским и немецким языками, .

Представим множества графически с помощью кругов Эйлера (рис. 1.5).

Способ 1. Составим уравнение: , откуда .

Способ 2. Найдём из уравнения или , .

Следовательно, 16 студентов свободно общались на двух иностранных языках.

Задача 14. Каждый студент группы программистов занимается в свободное время в НСО или спортом. Сколько студентов в группе, если 23 увлекаются спортом, 12 занимаются в НСО, а 7 совмещают занятия в НСО и увлечения спортом?

Решение. Изобразим множества кругами Эйлера, обозначив множества «спортсменов» - А и «исследователей» - В (рис. 1.6). Тогда

Задача 15. Из 35 студентов, побывавших на каникулах в Москве, все, кроме двоих, делились впечатлениями. О посещении Большого театра с восторгом вспоминали 12 человек, Кремля – 14, а 16 – о концерте, по три студента запомнили посещение театра и Кремля, а также театра и концерта, а четверо – концерта и пребывания в Кремле. Сколько студентов сохранили воспоминания одновременно о театре, концерте и Кремле?

Решение. Введём обозначения: А – множество студентов, вспоминающих о театре, ; В – о Кремле, ; С – о концерте, ; D – множество всех студентов, побывавших в поездке (рис. 1.6). , тогда , .

Проверочная работа по теме Подстановки

В – 1

Найдите и порядок каждой из подстановок:

В – 2

Найдите и порядок каждой из подстановок:

В – 3

Найдите и порядок каждой из подстановок:

В – 4

Найдите и порядок каждой из подстановок:

В – 5

Найдите и порядок каждой из подстановок:

В – 6

Найдите и порядок каждой из подстановок:

Тема 2. Графы

Лекция 1.

Цель – познакомить студентов с основными понятиями и определениями графа и его элементов.

2.1. Основные понятия и определения графа и его элементов

Графом называется пара двух конечных множеств: множество точек и множество линий, соединяющих некоторые пары точек.

Точки называются вершинами, или узлами, графа, линии – рёбрами графа.

Если ребро графа G соединяет две его вершины V и W, (т. е. ), то говорят, что это ребро им инцидентно. Две вершины графа называются смежными, если существует инцидентное им ребро: на рис. 2.1, а смежными являются вершины А и В, А и С. Если граф G имеет ребро , у которого начало и конец совпадают, то это ребро называется петлёй. На рис. 2.1, б петля - . Два ребра называются смежными, если они имеют общую вершину.

Рёбра, которые начинаются в одной и той же вершине, заканчиваются также в одной и той же вершине, называются кратными, или параллельными. Количество одинаковых пар вида называется кратностью ребра . Число рёбер, инцидентных вершине А, называется степенью этой вершины и обозначается (от англ. degree – степень).

Вершина графа, имеющая степень, равную нулю, называется изолированной. Граф, состоящий из изолированных вершин, называется нуль-графом. Вершина графа, имеющая степень, равную 1, называется висячей.

Теорема 2.1. В графе сумма степеней всех его вершин – число чётное, равное удвоенному числу рёбер графа:

,

где - число вершин; - число рёбер графа.

Вершина называется чётной (нечётной), если её степень – чётное (нечётное) число.

Теорема 2.2. Число нечётных вершин любого графа – чётно.

Следствие. Невозможно начертить граф с нечётным числом нечётных вершин.

Граф G называется полным, если любые две его различные вершины соединены одним и только одним ребром.

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

Если все пары во множестве Ч являются упорядоченными, т. е. кортежами длины 2, то граф называется ориентированным, орграфом, или направленным. Началом ребра называется вершина, указанная в кортеже первой, концом – вторая вершина этой пары (графически она указана стрелкой). Рёбра ориентированного графа имеют определённые фиксированные начало и конец и называются дугами.

Степенью входа (выхода) вершины ориентированного графа называется число рёбер, для которых эта вершина является концом (началом).

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

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

Расстоянием между двумя вершинами называется минимальная длина из всех возможных маршрутов между этими вершинами при условии, что существует хотя бы один такой маршрут. Обозначается как (от лат. distantio – расстояние) .

Если любое ребро в маршруте встречается только один раз, то маршрут называется цепью.

В орграфе маршрут является ориентированным и называется путём.

Путь – упорядоченная последовательность рёбер ориентированного графа, в которой конец предыдущего ребра совпадает с началом следующего и все рёбра единственны. Цикл в орграфе – путь, у которого совпадают начало и конец.

Цепь, путь и цикл в графе называются простыми, если они проходят через любую из вершин не более одного раза. Неориентированный граф называется связным, если между любыми двумя его вершинами есть маршрут. Так, графы G1 и G3 (рис. 2.1, а, в) являются связными, а граф G2 (рис. 2.1, б) – несвязным.

Две вершины называются связными, если существует маршрут между ними. Связность между вершинами является отношением эквивалентности.

Все подграфы Vi (классы эквивалентности) графа G называют связными компонентами, или компонентами связности.

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

Теорема 2.3. Для того чтобы связный граф G являлся простым циклом, необходимо и достаточно, чтобы каждая его вершина имела степень, равную 2.

Ребро связного графа G называется мостом, если после его удаления G станет несвязным и распадётся на два связных графа и .

Теорема 2.4. Ребро графа является мостом тогда и только тогда, когда не принадлежит ни одному циклу.

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

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

Теорема 2.5 (Эйлера). Связный плоский граф с п вершинами и т рёбрами разбивает плоскость на r областей (включая внешнюю), причём .

Задача 16 «О трёх колодцах». Проложить дорожки от трёх домов к каждому из трёх колодцев так, чтобы никакие две дорожки не пересекались.

Решение: Предположим, что эти 9 тропинок можно проложить. Обозначим домики точками А, В, С, колодцы - точками К1, К2, К3. Каждую точку-дом соединим с каждой точкой-колодцем. Получились ребра (графа) в количестве девяти штук, которые попарно не пересекаются. Такие ребра образуют на рассматриваемой плоскости задачи многоугольник, поделенный на меньшие многоугольники. Для такого разбиения должно выполняться известное соотношение Эйлера  п - т + r = 2, причем n = 6 и m = 9. Получается, r = 5. Каждая из пяти граней имеет по крайней мере четыре ребра, так как, по условию задачи Эйлера, ни одна из дорожек не должна напрямую соединять два колодца или два дома. Так как любое ребро лежит ровно в 2-х гранях, то количество ребер графа должно быть не меньше 5*4/2 = 10. Это противоречит условию исходной задачи, по которому их число равно девять! Полученное противоречие доказывает, что ответ в задаче о 3х колодцах Эйлера отрицателен.

Граф называется двудольным, если его вершины разбиты на два непересекающихся подмножества: , а рёбра связывают вершины только из разных классов (не обязательно все пары). Если каждая вершина множества V1 связана ребром с каждой вершиной множества V2, то двудольный граф называется полным двудольным и обозначается , где .

Эйлеровым путём (циклом) графа называется путь (цикл), который содержит все рёбра графа только один раз. Граф, обладающий эйлеровым циклом, называется эйлеровым. Плоский эйлеров граф также называют уникурсальным.

Теорема 2.6. Граф G является эйлеровым тогда и только тогда, когда G – связный граф, имеющий все чётные вершины.

Гамильтоновым путём (циклом) графа G называется путь (цикл), проходящий через каждую его вершину только один раз. Граф, содержащий гамильтонов цикл, называется гамильтоновым.

Задача 17 «О кёнигсбергских мостах» (Эйлера). Необходимо обойти все 7 мостов так, чтобы на каждом побывать только один раз и вернуться к началу пути (рис. 2.3).

2.2. Операции над графами

Объединением графов и называется граф , множество вершин которого , а множество рёбер .

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

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

Кольцевой суммой двух графов называется граф , порождённый множеством вершин и множеством рёбер , т. е. множеством рёбер, содержащихся либо в , либо в , но не в .

Компонентой связности неориентированного графа называется его подграф с множеством вершин и множеством рёбер , инцидентных только вершинам из множества , причём ни одна вершина из не смежна с вершинами из множества .

2.3. Деревья. Лес. Бинарные деревья

Деревом называют конечный связный граф с выделенной вершиной (корнем), не имеющий циклов (рис. 2.4).

Для каждой пары вершин дерева – узлов – существует единственный маршрут, поэтому вершины удобно классифицировать по степени удалённости от корневой вершины. Расстояние до корневой вершины называется ярусом s вершины, .

Теорема 2.7. Граф является деревом тогда и только тогда, когда выполняется хотя бы одно из условий:

граф связен и не содержит циклов;

граф не содержит циклов и имеет п – 1 ребро;

граф связен и имеет п – 1 ребро;

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

граф связный, но утрачивает это свойство после удаления любого ребра;

в графе всякая пара вершин соединена цепью, и только одной.

Висячие вершины, за исключением корневой, называются листьями.

Упорядоченное объединение деревьев представляет собой несвязный граф, называемый лесом. Остовом связного графа G называется любой его подграф, содержащий все вершины графа G и являющийся деревом.

Кодеревом остова Т графа G называется дополнение Т до G, т. е. такой его подграф, который содержит все его вершины и только те его рёбра, которые не входят в Т.

При описании деревьев принято использовать термины: отец, сын, предок, потомок.

Каждая вершина дерева называется узлом, причём каждый узел является корнем дерева, состоящего из поддеревьев. Узел k-го яруса называется отцом узла (k + 1)–го яруса, если они смежны. Узел (k + 1)–го яруса называется сыном узла k-го яруса. Два узла, имеющие одного отца, называются братьями (рис. 2.5).

Упорядоченным деревом называется дерево, в котором поддеревья каждого узла образуют упорядоченное подмножество. Для упорядоченных деревьев принята терминология: старший и младший сын для обозначения соответственно первого и последнего сыновей некоторого узла.

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

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

Цикломатическое число графа. Цикломатическим числом неориентированного графа G называется число , где - число его рёбер; - число связных компонент графа; - число вершин.

2.4. Способы задания графа. Изоморфные графы

Геометрическое представление плоского графа называется его реализацией.

При переходе от алгебраического способа (способа задания графа дугами путём указания вершин, которым они инцидентны) к геометрическому одному и тому же графу могут соответствовать различные изображения – изоморфные графы.

Граф можно задавать таблицей, состоящей из п строк (вершины) и т столбцов (рёбра).

Одним из самых распространённых способов задания графа является матричный способ.

Матрицей инцидентности называется таблица В, состоящая из п строк (вершины) и т столбцов (рёбра), в которой:

*  для неориентированного графа:

, если вершина инцидентна ребру ;

, если вершина не инцидентна ребру ;

*  для ориентированного графа:

, если вершина является началом дуги ;

, если вершина не инцидентна дуге ;

, если вершина является концом дуги .

Матрицей смежности графа без кратных рёбер называется квадратная матрица А порядка п, в которой:

, если ; , если .

При восстановлении графа по его матрице инцидентности можно получить граф лишь с точностью до изоморфизма.

Задача 18. Пусть граф G задан матрицей смежности А. Построить диаграмму этого графа, если

Указание. Поскольку матрица А несимметрична (например ), то она может задавать только ориентированный граф.

Задача 19. Пусть граф G задан матрицей смежности А. Построить диаграмму этого графа, если

Решение. Диаграмму графа, имеющего шесть вершин, можно представить следующим образом (рис. 2.7).