BSc: DiscreteMath

From IU
Jump to navigation Jump to search

Дискретная математика

Квалификация выпускника: бакалавр
Направление подготовки: 09.03.01 - “Информатика и вычислительная техника”
Направленность (профиль) образовательной программы: Математические основы ИИ
Программу разработал(а):

1. Краткая характеристика дисциплины

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

2. Перечень планируемых результатов обучения

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

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


Общая характеристика результата обучения по дисциплине

Знания: сформированы систематические знания по комбинаторике и дискретной математике
Умения: сформированы умения понять поставленную задачу; использовать свои знания для решения фундаментальных и прикладных задач; оценивать корректность постановок задач; строго доказывать или опровергать утверждение; самостоятельно находить алгоритмы решения задач, в том числе и нестандартных, и проводить их анализ; самостоятельно видеть следствия полученных результатов; точно представить математические знания в области в устной и письменной форме.
Навыки (владения): сформировано владение навыками освоения большого объема информации и решения задач ( в том числе, сложных); навыками самостоятельной работы и освоения новых дисциплин;

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


3. Структура и содержание дисциплины


п/п
Наименование раздела
дисциплины
Содержание дисциплины по темам
1. Базовые понятия теории графов - определение графа, орграфа, мультиграфа

- вершины, рёбра, степень вершины, лемма о рукопожатиях

- маршрут, путь, цикл

- связность, компонента связности

- подграф, индуцированный подграф, изоморфизм

2. Деревья - эквивалентные определения дерева

- количество рёбер в дереве

- остов графа

- лес, унициклический граф

- теорема Кэли

3. Эйлеровы пути и циклы в графах. - Эйлеров обход графа

- критерий эйлерова цикла, пути, в том числе в орграфе

- применения: последовательности де Брёйна

4. Планарные и плоские графы - укладка графа на плоскости. понятие грани

- формула Эйлера для связного и не связного графа

- примеры непланарных графов

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

- графы на сфере, классификация правильных многогранников

- задача о четырёх красках. Хроматическое число планарного графа, верхняя оценка 5 и 6.

5. Хроматическое число графа - клики и независимые множества

- правильная раскраска, хроматическое число графа, тривиальные оценки

- связь хроматического числа с максимальной степенью вершины

- жадный алгоритм правильной раскраски, его точность

- хроматическое число графа не больше 2 и двудольность

6 Паросочетания в графе - паросочетания, максимальное паросочетания, совершенное паросочетание

- лемма Холла о совершенном паросочетании в двудольном графе

- задача о системах различных представителей, перманент

- чередующиеся цепи

- минимальное вершинное покрытие, связь с максимальным паросочетанием в двудольном графе (т. Кёнига)

7 Гамильтоновы циклы и пути - Гамильтоновы циклы и пути

- критерии Оре и Дирака гамильтоновсти

- критерий Эрдеша-Хватала

8 Введение в экстремальную комбинаторику - максимальное количество рёбер в графе без l-клик (т. Турана)

- структура графа без l-клик

- дистанционные графы, оценка числа ребер у дистанционного графа в произвольной размерности


4. Методические и оценочные материалы

Задания для практических занятий:


п/п
Наименование раздела
дисциплины (модуля)
Перечень рассматриваемых тем (вопросов)
1. Базовые понятия теории графов Как связаны сумма степеней вершин любого графа и количество его рёбер?

Верно ли, что число вершин нечётной степени любого графа чётно?


Существует ли граф с заданным набором степеней ; ; ; ; ?


В группе 21 студент. Докажите, что хотя бы двое из них имеют поровну друзей в классе. Ученик Ян заметил: у остальных 20-ти разное число друзей в классе. Сколько из них дружат с Яном?


Сколько в графе рёбер? Сколько в графе простых циклов/циклов/путей длины ? длины ?


Докажите, что любой цикл содержит простой цикл. Верно ли, что любой цикл нечётной длины содержит простой цикл нечётной длины? Верно ли аналогичное утверждение для циклов чётной длины?


Пусть в графе есть простой цикл проходящий через рёбра и , а также простой цикл, проходящий через рёбра и . Докажите, что есть простой цикл, проходящий через рёбра и .


В графе на вершинах степень каждой вершины равна . Докажите, что в этом графе есть цикл длины .


Докажите, что отношение <<соединённость некоторым путём>> является отношением эквивалентности на множестве вершин графа.


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


В графе вершин, степень каждой не менее . Докажите, что он связен.


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


Сколько существует попарно неизоморфных графов, имеющих 8 вершин и 25 рёбер?

2. Деревья Существует ли дерево на 9 вершинах, в котором 2 вершины имеют степень 5?


В дереве нет вершин степени 2. Докажите, что количество висячих вершин больше половины общего количества вершин.


Докажите, что каждый связный граф содержит остов.


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


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


Найдите количество деревьев с данными вершинами, в которых вершина с номером имеет степень .


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


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


Каких графов с данными вершинами больше:

  • имеющих изолированную вершину или не имеющих?
  • связных или несвязных?


Каких графов больше, деревьев с данными вершинами или унициклических графов с данными вершинами?


Выразите число унициклических графов с данными вершинами в виде суммы не более чем слагаемых.


Найдите асимптотику числа унициклических графов с данными вершинами.

3. Эйлеровы пути и циклы в графах. Сколькими способами рёбра в графе можно разбить на непересекающиеся циклы?


При каком условии на ориентированный граф в нём существует эйлеров цикл?


При каком условии на граф в нём существует ‘’эйлеров путь’’, т.е. путь, проходящий по всем рёбрам графа?



При каких граф эйлеров? граф эйлеров?


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


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


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

  • секунд, если в коде могут быть использованы только цифры , и .
  • секунды, если в коде могут быть использованы только десять цифр.

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


Постройте двоичную последовательность Де Брёйна порядка , начинающуюся с , , начинающуюся с , , заканчивающуюся на .


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


Существует дерево, содержащее все вершины ориентированного графа, у которого все ребра направлены в сторону вершины 1.

Фиксируем дерево из \textbf{а)} . Будем обходить ориентированный граф (по стрелкам), проходя по каждому ребру не более одного раза.

Сначала выйдем из вершины 1 в произвольном направлении.

Далее, пусть мы пришли в некоторую вершину .

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

А если невозможно, то выходим из нее по ребру, принадлежащему (такое ребро единственно).

Докажите, что обход закончится в вершине 1 и что в результате обхода получится эйлеров цикл.


Число эйлеровых циклов в ориентированном графе кратно числу

4. Планарные и плоские графы Для связного плоского графа без петель и кратных рёбер при выполнено неравенство Failed to parse (unknown function "\F"): {\displaystyle 2E \geq 3\F} .`

если , то выполнено неравенство Failed to parse (unknown function "\V"): {\displaystyle E \leq 3\V-6} .

Как можно улучшить неравенство в пункте а), если минимальная длина цикла равна ?


‘’Применения формулы Эйлера’’. Ни один из графов и невозможно без самопересечений нарисовать на плоскости.


Для каких полный двудольный граф не планарный?



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


(‘’Футбольный мяч’’) У выпуклого многогранника все грани — правильные пятиугольники или правильные шестиугольники. Докажите, что в каждой вершине этого многогранника сходятся ровно три грани. Сколько пятиугольных граней у данного многоугольника?

5. Хроматическое число графа Если в графе степень каждой вершины не превосходит , то его можно правильно раскрасить в цвет.

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

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

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

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

‘’Теорема Брукса’’ В графе степень каждой вершины не превосходит и нет полного подграфа с вершиной. Докажите, что его можно правильно раскрасить в цветов.

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

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

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

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

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


Для каждого натурального постройте двудольный граф , раскраска которого, построенная жадным алгоритмом, имеет не менее цветов.

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


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


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

7. Гамильтоновы циклы и пути Приведите пример гамильтонова не эйлерова графа; эйлерова не гамильтонова графа.


Связный граф с вершинами и является гамильтоновым.


Существует ли негамильтонов граф с рёбрами?

8. Введение в экстремальную комбинаторику Если граф не содержит треугольников, то

Если , то в графе есть по крайней мере треугольников.

Если и граф не содержит полного подграфа с вершинами, то .

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

Eсли среди любых вершин некоторые две соединены ребром, и , то .

Если граф двудолен и не содержит цикла длины 4, то .

В любом графе есть двудольный подграф, содержащий не менее половины ребер графа.

Если граф не содержит цикла длины 4, то .

Если граф не содержит подграфа , то .

Если граф не содержит подграфа , то .

Для любых целых , \ , если граф с не содержит подграфа , то . Если ни один граф из последовательности графов с вершинами и ребрами не содержит подграфа , то при .

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


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


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

Обозначим

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

.

.

.

Пусть --- -элементное подмножество пространства , любое -эле\-мент\-ное подмножество которого содержит две точки на расстоянии 1: .

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

То же больше, чем .


Текущий контроль успеваемости обучающихся по дисциплине:


п/п
Наименование раздела
дисциплины
Форма текущего контроля
Материалы текущего контроля

"|- style=""background-color:#F8F9FA; color:#202122;""

1 Базовые понятия теории графов Домашние работы В домашние работы включаются задачи, нерешенные во время семинарских занятий."

"|- style=""background-color:#F8F9FA; color:#202122;""

2 Деревья Домашние работы В домашние работы включаются задачи, нерешенные во время семинарских занятий."

"|- style=""background-color:#F8F9FA; color:#202122;""

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

"|- style=""background-color:#F8F9FA; color:#202122;""

4 Планарные и плоские графы Домашние работы В домашние работы включаются задачи, нерешенные во время семинарских занятий."

"|- style=""background-color:#F8F9FA; color:#202122;""

5 Хроматическое число графа Домашние работы В домашние работы включаются задачи, нерешенные во время семинарских занятий."

"|- style=""background-color:#F8F9FA; color:#202122;""

6 Паросочетания в графе Домашние работы В домашние работы включаются задачи, нерешенные во время семинарских занятий."

"|- style=""background-color:#F8F9FA; color:#202122;""

7 Гамильтоновы циклы и пути Домашние работы В домашние работы включаются задачи, нерешенные во время семинарских занятий."

"|- style=""background-color:#F8F9FA; color:#202122;""

8 Введение в экстремальную комбинаторику Домашние работы В домашние работы включаются задачи, нерешенные во время семинарских занятий."

Контрольные вопросы для подготовки к промежуточной аттестации:


п/п
Наименование
раздела дисциплины
Вопросы
1 Базовые понятия теории графов 1)Граф, ориентированный граф, мультиграф.

2) Вершина, ребро, степень вершины. Полный граф. Лемма о рукопожатиях.

3) Маршруты, пути, циклы, простые пути, простые циклы.

4) Связность, компонента связности. Изоморфизм графов, подграфы, индуцированные подграфы

2 Деревья 5) Дерево, висячая вершина, остов.

6) Эквивалентные определения деревьев

7)Существование висячей вершины в связном ацикличном графе.

8) Код Прюфера. Теорема Кэли

3 Эйлеровы пути и циклы в графах. 9) Эйлеров цикл, путь и эйлеров граф.

10) Последовательность де Брёйна и граф де Брёйна. Правило <<0 лучше 1>>

4 Планарные и плоские графы 11) Планарные и плоские графы. Грань плоского графа. Формула Эйлера .

12) Пример непланарного графа

13) Классификация правильных многогранников

14) Раскраска карт, хроматическое число планарного графа.

5 Хроматическое число графа 15) Соотношения между хроматическим числом, числом независимости и кликовым числом.

16) Связь между хроматическим числом и максимальной степенью вершины

17) Хроматическое число пространства. Доказательство конечности. Известные нижние и верхние оценки (б/д). Связь с хроматическим числом дистанционного графа.

6 Паросочетания в графе 18) Максимальное и совершенное паросочетания. Теорема Холла о совершенном паросочетании в двудольном графе

19) Теорема Кёнига о максимальном паросочетании и минимальном вершинном покрытии в двудольном графе

7 Гамильтоновы циклы и пути 20) Гамильтонов путь и цикл, гамильтонов граф.

21) Достаточное условие Дирака и Оре гамильтоновости графа.

22)Вершинная связность и число независимости графа. Признак Эрдёша-Хватала.

23)Гамильтоновость графа 1-пересечений 3-элементных подмножеств n-элементного множества при всех всех достаточно больших n.

8 Введение в экстремальную комбинаторику 24) Теорема Турана о числе ребер в графе с данным числом вершин и числом независимости.

25) Асимптотика наибольшего числа ребер в графе с n вершинами без k-клик.


Вопросы/Задания к промежуточной аттестации в устной/письменной форме:

1)Граф, ориентированный граф, мультиграф.

2) Вершина, ребро, степень вершины. Полный граф. Лемма о рукопожатиях.

3) Маршруты, пути, циклы, простые пути, простые циклы.

4) Связность, компонента связности. Изоморфизм графов, подграфы, индуцированные подграфы

5) Дерево, висячая вершина, остов.

6) Эквивалентные определения деревьев

7)Существование висячей вершины в связном ацикличном графе.

8) Код Прюфера. Теорема Кэли

9) Эйлеров цикл, путь и эйлеров граф.

10) Последовательность де Брёйна и граф де Брёйна. Правило <<0 лучше 1>>

11) Планарные и плоские графы. Грань плоского графа. Формула Эйлера .

12) Пример непланарного графа

13) Классификация правильных многогранников

14) Раскраска карт, хроматическое число планарного графа.

15) Соотношения между хроматическим числом, числом независимости и кликовым числом.

16) Связь между хроматическим числом и максимальной степенью вершины

17) Хроматическое число пространства. Доказательство конечности. Известные нижние и верхние оценки (б/д). Связь с хроматическим числом дистанционного графа.

18) Максимальное и совершенное паросочетания. Теорема Холла о совершенном паросочетании в двудольном графе

19) Теорема Кёнига о максимальном паросочетании и минимальном вершинном покрытии в двудольном графе

20) Гамильтонов путь и цикл, гамильтонов граф.

21) Достаточное условие Дирака и Оре гамильтоновости графа.

22)Вершинная связность и число независимости графа. Признак Эрдёша-Хватала.

23)Гамильтоновость графа 1-пересечений 3-элементных подмножеств n-элементного множества при всех всех достаточно больших n.

24) Теорема Турана о числе ребер в графе с данным числом вершин и числом независимости.

25) Асимптотика наибольшего числа ребер в графе с n вершинами без k-клик.


Перечень учебно-методического обеспечения дисциплины

Список основной литературы:

Lovasz L., Vesztergombi K. Discrete Mathematics. Lecture Notes, Yale University. — 1999. — URL: http://www.cs.elte.hu/lovasz/dmbook.ps.

Лекции по дискретной математике / М. Вялый, В. Подольский, А. Рубцов, Д. Шварц, А. Шень. — ИД НИУ ВШЭ. Черновик: https://publications.hse.ru/mirror/pubs/share/direct/393719078.pdf, 2021.

Харари Ф. Теория графов. Изд. 2-е. — М.: Эдиториал УРРС, 2003.

К. Берж. Теория графов и ее применения. – М.:Изд. иностр. лит., 1962.

Р.Уилсон. Введение в теорию графов. – М.: Мир, 1977.

Оре О. Теория графов. М.: Наука, 1968. – 352 с.


Методические указания для обучающихся по освоению дисциплины

Вид учебных
занятий/деятельности
Деятельность обучающегося
Лекция Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
Практическое (семинарское) занятие При подготовке к семинарскому (практическому) занятию необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. На основании обработанной информации постараться сформировать собственное мнение по выносимой на обсуждение тематике. Обосновать его аргументами, сформировать список источников, подкрепляющих его.

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

Устный/письменный опрос Отвечать, максимально полно, логично и структурировано, на поставленный вопрос. Основная цель – показать всю глубину знаний по конкретной теме или ее части.
Контрольная работа При подготовке к контрольной работе необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме.

Методы и технологии обучения, способствующие формированию компетенции

Методы и технологии обучения, способствующие формированию компетенции
Информационно – коммуникационная технология, Педагогика сотрудничества, Традиционные технологии, Модульная технология