Основы дискретной математики : теория графов

МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РФ 

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ 
ВЫСШЕГО ОБРАЗОВАНИЯ «НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ 
ТЕХНОЛОГИЧЕСКИЙ УНИВЕРСИТЕТ «МИСиС» 

ИНСТИТУТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ И АВТОМАТИЗИРОВАННЫХ СИСТЕМ 
УПРАВЛЕНИЯ 

 

 
 
 

 

 

 

 
 

№ 3049 

Кафедра автоматизированного проектирования и дизайна 

 
Д.В. Калитин 
О.С. Калитина 
 
 
Основы дискретной
математики 

Теория графов 

Практикум 

Рекомендовано редакционно-издательским 
советом университета 

Москва 2017 

УДК 
51:004 
 
К17 

Р е ц е н з е н т  
канд. техн. наук, доц. И.В. Баранникова 

Калитин Д.В. 
К17  
Основы дискретной математики : теория графов : практикум / Д.В. Калитин, О.С. Калитина. – М. : Изд. Дом НИТУ 
«МИСиС», 2017. – 67 с. 
 
 
ISBN 978-5-906846-68-6 
 
Рассмотрено решение основных задач, возникающих при использовании теории графов. Для каждой задачи приведены подробные решения. 
Описаны условия однотипных заданий. 
Предназначен для обучающихся в бакалавриате по направлениям подготовки 09.03.01 «Информатика и вычислительная техника», 09.03.04 «Информационные системы и технологии», 27.04.03 «Управление в технических системах». 

УДК 51:004 

 

 

 

 

 

 
 
© Д.В. Калитин, 
О.С. Калитина, 2017 
ISBN 978-5-906846-68-6 
© НИТУ «МИСиС», 2017 

СОДЕРЖАНИЕ 

Введение ................................................................................................................. 4 
Основы теории множеств ..................................................................................... 5 
Операции над множествами ................................................................................. 8 
Понятие «алгебра». Алгебра множеств ............................................................. 10 
Бинарные отношения .......................................................................................... 12 
Основы теории графов ........................................................................................ 12 
Связность и сильная связность графа ................................................................ 16 
Цикломатика и коцикломатика .......................................................................... 18 
Устойчивость, покрытия, паросочетания.......................................................... 20 
Вложение графов в плоскость ............................................................................ 23 
Раскраска вершин графа ..................................................................................... 25 

Примеры решения задач ..................................................................................... 27 
Операции над графами ........................................................................................ 27 
Связность графов ................................................................................................. 33 
Цикломатика ........................................................................................................ 44 
Поиск пустых подграфов .................................................................................... 49 
Внешняя устойчивость графов ........................................................................... 56 
Раскраска вершин графа ..................................................................................... 60 

Литература ............................................................................................................ 66 
 
 
 

ВВЕДЕНИЕ 

Теория графов, как раздел дискретной математики, является важным математическим аппаратом, который используется во многих 
прикладных задачах. 
Начало теории графов как математической дисциплине было положено Эйлером в его знаменитом рассуждении о Кенигсбергских 
мостах. Однако эта статья Эйлера 1736 г. была единственной в течение почти 100 лет. Интерес к проблемам теории графов возродился 
около середины XX в. и был сосредоточен главным образом в Англии. Имелось много причин для такого оживления изучения графов. 
Естественные науки оказали свое влияние на это благодаря исследованиям электрических сетей, моделей кристаллов и структур молекул. Развитие формальной логики привело к изучению бинарных отношений в форме графов. Большое число популярных головоломок 
поддавалось формулировкам непосредственно в терминах графов и 
это приводило к пониманию, что многие задачи такого рода содержат некоторое математическое ядро, важность которого выходит за 
рамки конкретного вопроса. Наиболее знаменитая среди этих задач – 
проблема четырех красок, впервые поставленная перед математиками Де Морганом около 1850 г. Никакая другая проблема не вызывала 
столь многочисленных и остроумных работ в области теории графов. 
Благодаря своей простой формулировке и раздражающей неуловимости она до сих пор остается мощным стимулом исследований различных свойств графов. 
Прошлое столетие было свидетелем неуклонного развития теории 
графов, которая за последние 30–40 лет вступила в новый период 
интенсивных разработок. В этом процессе явно заметно влияние запросов новых областей приложений: теории игр и программирования, теории передачи сообщений, электрических сетей и контактных 
цепей, а также проблем биологии и психологии. 
 
 

ОСНОВЫ ТЕОРИИ МНОЖЕСТВ 

Любое понятие дискретной математики можно определить с помощью понятия «множество». Под множеством понимают объединение в одно общее объектов, хорошо различаемых нашей интуицией или нашей мыслью. Таково интуитивное определение понятия 
«множество», данное основателем теории множеств Георгом Кантором. Это понятие является в математике первичным и, следовательно, не имеет строгого определения. Объекты, которые образуют 
множество, будем называть элементами множества и обозначать, как 
правило, строчными буквами латинского алфавита. Если элемент принадлежит множеству , то будем использовать запись ∈ , 
в противном случае используем запись ∉ ; знак принадлежности 
элемента множеству ∈ является стилизацией первой буквы греческого слова εστι (есть, быть). 
Множество, содержащее конечное число элементов, называется 
конечным. Если же множество не содержит ни одного элемента, то 
оно называется пустым и обозначается ∅. 
Множество может быть задано различными способами: перечислением элементов (конечные множества) или указанием их свойств 
(при этом для задания множеств используют фигурные скобки). Например, множество цифр десятичного алфавита можно задать в 
виде = {0, 1, … , 9} или = {/ целое, 0 ≤ ≤ 9}, где справа от 
наклонной черты указано свойство элементов этого множества. 
Множество четных чисел можно записать в виде = {m/m – четное число}. 
Множество ′ называется подмножеством множества (M' 
включено в M тогда и только тогда, когда любой элемент множества 
′ принадлежит множеству : 

⊂ ↔ (∈ → ∈ ) 

или 

⊂ ↔ = {/ ∈ }, 

где ⊂ – знак включения подмножества;  
→ означает: если , то ; ↔ означает: , если и только если . В частном случае множества ′ и могут совпадать. 

Невключение подмножества ′ во множество обозначается 
⊄ . 

Очевидно, что если множество – подмножество множества и множество – подмножество множества , то оба этих множества состоят из одних и тех же элементов. Такие множества называются равными: = . Если же множество ′ – подмножество 
множества , а множество не является подмножеством множества 
′, то множество ′ называется собственным подмножеством 
множества ; запись: ′ ⊂⊂ . 
Для каждого множества существует множество, элементами 
которого являются подмножества множества и только они. Такое 
множество будем называть семейством множества , или булеаном 
этого множества, и обозначать (), а множество будем называть 
универсальным, универсумом, или пространством, и обозначать 1. 
При рассмотрении различных подмножеств и их свойств часто приходится обращаться к комбинаторике – разделу дискретной математики, посвященному решению задач выбора и расположения элементов 
некоторого, как правило, конечного множества в соответствии с заданными свойствами. Каждое такое свойство определяет способ построения некоторой конструкции из элементов множества, называемой комбинаторной конфигурацией. Простейшими комбинаторными конфигурациями являются размещения, перестановки и сочетания. 
Размещение (, ) мощности из элементов (≤ ) – это 
любая последовательность (т. е. множество с зафиксированным в нем 
порядком элементов) попарно различных элементов, взятых из элементов; для записи размещений используются круглые скобки. 
Первый элемент последовательности можно зафиксировать способами, второй элемент – − 1 способами и т. д., i-й элемент – 
− + 1 способами. Следовательно, количество таких последовательностей (размещений) равно произведению чисел , − 1, … , 
 − + 1: 

|(, )| = ∙ (− 1) ∙ … ∙ (− + 1) = (− )

. 

В этой конфигурации важен как состав элементов, так и их порядок. 
Размещение при = называется перестановкой (). Число 
перестановок |()| из элементов есть 

(− ) =

∙ (− 1) ∙ … ∙ 2 ∙ 1 = !. 

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

|(, )| = (, )
() =
!
(− )! ∙ ! . 

Это число, кстати, равно коэффициенту в разложении бинома 
Ньютона (+ ). 
Рассмотрим образование булеана (1) от универсума 1 = {, , }. 
|1| – количество элементов конечного множества, в дальнейшем 
называемое мощностью множества. 
Очевидно, что мощность |(1)| булеана от универсума 1 равна 2||: 

|(1)| = 2||. 

В рассматриваемом случае: 

(1) = ∅, {}, {}, {}, {, }, {, }, {, }, {, , }. 

Множество также часто задают графически с помощью диаграмм 
Эйлера. Например, задание множества {, , }, {, , }в пространстве 1 = {, , , , } приведено на рис. 1, где замкнутые линии, называемые в дальнейшем кругами Эйлера, ограничивают элементы 
множества, при этом рамка, в верхнем правом углу которой стоит 1, 
ограничивает элементы пространства. 

 

Рис. 1. Диаграмма Эйлера. 

1

ОПЕРАЦИИ НАД МНОЖЕСТВАМИ 

Декартовым произведением двух множеств × множеств и называется множество вида 

= {, / ∈ , ∈ }. 

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

× × … × = произвольного числа множеств , , … , называется множество 

= {(, , … , )/ ∈ , ∈ , … , ∈ }. 

Элементами декартова произведения × × … × являются 
всевозможные последовательности, каждая из которых состоит из элементов, причем первый элемент принадлежит множеству , второй – множеству и т. д., n-й элемент принадлежит множеству . 
Объединением ∪ двух множеств и является множество , состоящее из элементов множества и из элементов множества : 

=  ∪ = {/ ∈ и/или ∈ }. 

Пересечением ∩ двух множеств и является множество , состоящее из элементов, которые принадлежат как множеству , так и множеству : 

=  ∩ = {/ ∈ и ∈ }; 

часто союз «и» заменяют знаком &: 

=  ∩ = {/ ∈ & ∈ }. 

Разностью \ множеств и является множество , 
состоящее из элементов, принадлежащих множеству и не принадлежащих множеству : 

=  \ = {/ ∈ & ∉ }. 

Введенные операции являются двуместными. 
Рассмотрим операцию дополнения, являющуюся одноместной. 
Дополнением множества является множество 

= {/ ∉  }. 

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

 

Рис. 2. Диаграммы Эйлера для различных операций 

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

Пример 
Рассмотрим операцию дополнения множества, являющегося пересечением множеств к . Ее результат совпадает с объединением 
дополнений этих множеств: =  ∪ = ∩ ; в этом 
можно убедиться с помощью диаграмм Эйлера (рис. 3). 

 

Рис. 3. Диаграмма Эйлера для операции  ∪ ПОНЯТИЕ «АЛГЕБРА». АЛГЕБРА МНОЖЕСТВ 

Алгеброй называется совокупность множества с заданными в 
нем операциями 

= , , … , , , , … , , … , , , … , ; 

обозначается = < М, >; здесь множество – носитель, – сигнатура алгебры. 
Рассмотрим алгебру множеств (алгебру Кантора, алгебру классов) 

= < (1),∪,∩, >, 

носителем которой является булеан универсального множества 1, 
сигнатурой – операции объединения ∪ пересечения ∩ и дополнения 
. Для операций алгебры Кантора выполняются следующие законы: 

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

 ∪ = ∪  ,
 ∩ = ∩  ; 

закон ассоциативности объединения и пересечения 

 ∪ (∪ ) =  (∪  ) ∪ , 

 ∩ (∩ ) =  (∩  ) ∩ ; 

закон дистрибутивности пересечения относительно объединения 
и объединения относительно пересечения 

 ∩ (∪ ) =  ∩  ∪  ∩  , 

 ∪  ∪ =  (∪  ) ∩  (∪  ); 

законы поглощения 

 ∪  ∩ =  ,
 ∩  (∪ ) =  ; 

законы склеивания 

 ∩  ∪ ∩  =  , 

 (∪  ) ∩  (∪ ) = ; 

законы Порецкого 

 ∪  ∩ =  ∪ ,
 ∩ ( ∪ ) =  ∩ ; 

закон идемпотентности объединения и пересечения 

 ∪ = ∪  ,
 ∩ = ∩  ; 

закон действия с универсальным (1) и пустым (0) множествами 

∪ ∅ = , ∩ ∅ = ∅, ∪ 1 = 1, 

∩ 1 = , ∪ = 1, ∩ = ∅; 

законы де Моргана 

 ∩ = ∪  ,
 ∪ = ∩  ; 

закон двойного дополнения 

= .