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

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

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

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

 

 
 
 

 

 

 

 
 

№ 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