Difference between revisions of "BSc: DiscreteMath"

From IU
Jump to navigation Jump to search
(Created page with "= <span style="color:red;">Название дисциплины</span> = : '''Квалификация выпускника''': <span style="color:red;">бакалавр/ма...")
 
 
(2 intermediate revisions by the same user not shown)
Line 1: Line 1:
  +
= Дискретная математика=
= <span style="color:red;">Название дисциплины</span> =
 
: '''Квалификация выпускника''': <span style="color:red;">бакалавр/магистр</span>
+
: '''Квалификация выпускника''': бакалавр
: '''Направление подготовки''': __________________
+
: '''Направление подготовки''': 09.03.01 - “Информатика и вычислительная техника”
: '''Направленность (профиль) образовательной программы''': <span style="color:red;">(Указывается направленность (профиль) образовательной программы</span>
+
: '''Направленность (профиль) образовательной программы''': Математические основы ИИ
: '''Программу разработал(а)''': __________________
+
: '''Программу разработал(а)''':
   
 
== 1. Краткая характеристика дисциплины ==
 
== 1. Краткая характеристика дисциплины ==
Изучение дисциплины обеспечивает формирование и развитие компетенций обучающихся в области <span style="color:red;">(указывается область изучаемой дисциплины. Например: программного обеспечения и его разработки; робототехники и т.д.)</span>, их применение для решения различных прикладных задач в рамках профессиональной деятельности. В ходе освоения дисциплины обучающиеся рассматривают <span style="color:red;">(краткое описание содержания дисциплины)</span>.
+
Изучение дисциплины обеспечивает формирование и развитие компетенций обучающихся в области дискретной математики, их применение для решения различных прикладных задач в рамках профессиональной деятельности. Большая часть курса посвящена теории графов. Изучаются как базовые определения и классические задачи, так и современные результаты и тенденции. В частности, рассматриваются вероятностный и линейно-алгебраический методы.
   
 
== 2. Перечень планируемых результатов обучения ==
 
== 2. Перечень планируемых результатов обучения ==
  +
: '''Целью освоения дисциплины''' является изучение математических основ современной комбинаторики, а также подготовка слушателей к дальнейшей самостоятельной работе в области комбинаторных задач прикладной математики, физики и информационных технологий.
: '''Целью освоения дисциплины''' ...
 
  +
  +
: '''Задачами дисциплины''' являются изучение математических основ современной комбинаторики;
  +
приобретение слушателями теоретических знаний в области комбинаторного анализа задач, возникающих на практике; освоение аналитического и алгебраического аппарата дискретной математики и получение навыков работы с основными дискретными структурами.
   
: '''Задачами дисциплины''' вляются ... <span style="color:red;">(перечислить задачи дисциплины, например: изучение принципов организации подсистем обработки естественного языка для различных прикладных задач и тенденций развития лингвистических ресурсов в сфере интеллектуальных информационных технологий и т.д.).</span>
 
   
 
=== Общая характеристика результата обучения по дисциплине ===
 
=== Общая характеристика результата обучения по дисциплине ===
: '''Знания:''' сформированы систематические знания ...
+
: '''Знания:''' сформированы систематические знания по комбинаторике и дискретной математике
  +
<span style="color:red;">(информация, которой обладает обучающийся в определенных областях, полученная в процессе обучения, то есть это информация для осуществления какой-либо деятельности (действия))</span>
 
  +
: '''Умения:''' сформированы умения понять поставленную задачу; использовать свои знания для решения фундаментальных и прикладных задач; оценивать корректность постановок задач; строго доказывать или опровергать утверждение; самостоятельно находить алгоритмы решения задач, в том числе и нестандартных, и проводить их анализ; самостоятельно видеть следствия полученных результатов; точно представить математические знания в области в устной и письменной форме.
  +
  +
: '''Навыки (владения):''' сформировано владение навыками освоения большого объема информации и решения задач ( в том числе, сложных); навыками самостоятельной работы и освоения новых дисциплин;
  +
культурой постановки, анализа и решения математических и прикладных задач, требующих для своего решения использования математических подходов и методов; предметным языком дискретной математики и навыками грамотного описания решения задач и представления полученных результатов.
   
: '''Умения:''' сформированы умения ...
 
<span style="color:red;">(предполагает целенаправленное выполнение действий, по изученной информации)</span>
 
   
: '''Навыки (владения):''' сформировано владение навыками ...
 
<span style="color:red;">(автоматизированные устойчивые умения выполнять определенную работу, то есть действие выполняется без контроля сознания, автоматически)</span>
 
   
 
== 3. Структура и содержание дисциплины ==
 
== 3. Структура и содержание дисциплины ==
  +
<span style="color:red;">(Указываются: 1) порядковый номер раздела (количество разделов зависит от содержания Вашей дисциплины); 2) наименования разделов дисциплины; 3) темы указанных разделов (количество тем в каждом разделе зависит от содержания Вашей дисциплины)</span>
 
 
{| class="wikitable" style="width:70%;"
 
{| class="wikitable" style="width:70%;"
 
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
 
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
Line 30: Line 32:
 
| style="width:30%" | Наименование раздела <br> дисциплины
 
| style="width:30%" | Наименование раздела <br> дисциплины
 
| style="width:60%" | Содержание дисциплины по темам
 
| style="width:60%" | Содержание дисциплины по темам
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 1. || Базовые понятия теории графов || - определение графа, орграфа, мультиграфа
| style="text-align:center;" | 1. || || &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>
 
  +
|- style="background-color:#F8F9FA; color:#202122;"
 
  +
- вершины, рёбра, степень вершины, лемма о рукопожатиях
| style="text-align:center;" | 2. || || &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>
 
  +
|- style="background-color:#F8F9FA; color:#202122;"
 
  +
- маршрут, путь, цикл
| style="text-align:center;" | 3. || || &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>
 
  +
|- style="background-color:#F8F9FA; color:#202122;"
 
  +
- связность, компонента связности
| style="text-align:center;" | 4. || || &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>
 
  +
|- style="background-color:#F8F9FA; color:#202122;"
 
  +
- подграф, индуцированный подграф, изоморфизм
| style="text-align:center;" | 5. || || &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>
 
|- style="background-color:#F8F9FA; color:#202122;"
+
|- style="background-color:#F8F9FA; color:#202122;"
| style="text-align:center;" | ... || || &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;-<br>
+
| style="text-align:center;" | 2. || Деревья || - эквивалентные определения дерева
  +
  +
- количество рёбер в дереве
  +
  +
- остов графа
  +
  +
- лес, унициклический граф
  +
  +
- теорема Кэли
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 3. || Эйлеровы пути и циклы в графах. || - Эйлеров обход графа
  +
  +
- критерий эйлерова цикла, пути, в том числе в орграфе
  +
  +
- применения: последовательности де Брёйна
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 4. || Планарные и плоские графы || - укладка графа на плоскости. понятие грани
  +
  +
- формула Эйлера для связного и не связного графа
  +
  +
- примеры непланарных графов
  +
  +
- критерий Понтрягина-Куратовского
  +
  +
- графы на сфере, классификация правильных многогранников
  +
  +
- задача о четырёх красках. Хроматическое число планарного графа, верхняя оценка 5 и 6.
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 5. || Хроматическое число графа || - клики и независимые множества
  +
  +
- правильная раскраска, хроматическое число графа, тривиальные оценки
  +
  +
- связь хроматического числа с максимальной степенью вершины
  +
  +
- жадный алгоритм правильной раскраски, его точность
  +
  +
- хроматическое число графа не больше 2 и двудольность
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 6 || Паросочетания в графе || - паросочетания, максимальное паросочетания, совершенное паросочетание
  +
  +
- лемма Холла о совершенном паросочетании в двудольном графе
  +
  +
- задача о системах различных представителей, перманент
  +
  +
- чередующиеся цепи
  +
  +
- минимальное вершинное покрытие, связь с максимальным паросочетанием в двудольном графе (т. Кёнига)
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 7 || Гамильтоновы циклы и пути || - Гамильтоновы циклы и пути
  +
  +
- критерии Оре и Дирака гамильтоновсти
  +
  +
- критерий Эрдеша-Хватала
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 8 || Введение в экстремальную комбинаторику || - максимальное количество рёбер в графе без l-клик (т. Турана)
  +
  +
- структура графа без l-клик
  +
  +
- дистанционные графы, оценка числа ребер у дистанционного графа в произвольной размерности
  +
  +
 
|}
 
|}
   
Line 50: Line 112:
 
| style="width:10%" | №<br>п/п
 
| style="width:10%" | №<br>п/п
 
| style="width:30%" | Наименование раздела<br>дисциплины (модуля)
 
| style="width:30%" | Наименование раздела<br>дисциплины (модуля)
| style="width:60%" | Перечень рассматриваемых тем (вопросов)<br><span style="color:red;">(Указываются ВСЕ задания для практических занятий по разделам дисциплины подробно в соответствии с темами)</span>
+
| style="width:60%" | Перечень рассматриваемых тем (вопросов)<br>
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 1. || Базовые понятия теории графов || Как связаны сумма степеней вершин любого графа и количество его рёбер?
| style="text-align:center;" | 1. || ||
 
  +
Верно ли, что число вершин нечётной степени любого графа чётно?
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
  +
| style="text-align:center;" | 2. || ||
 
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
  +
| style="text-align:center;" | 3. || ||
 
  +
Существует ли граф с заданным набором степеней
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
  +
<math>(2,2,2,3,3)</math>; <math>(0,1,2,3,4) </math>; <math>(1,2,3,3,4,4) </math>;
| style="text-align:center;" | 4. || ||
 
  +
<math> (7,7,6,4,4,2,2,2)</math>; <math>(6,6,6,7,7,5,5,5,4,3) </math>?
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
  +
| style="text-align:center;" | 5. || ||
 
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
  +
| style="text-align:center;" | ... || ||
 
  +
В группе 21 студент. Докажите, что хотя бы двое из них имеют поровну друзей в классе. Ученик Ян заметил: у остальных 20-ти разное число друзей в классе. Сколько из них дружат с Яном?
  +
  +
  +
  +
Сколько в графе <math>K_n</math> рёбер?
  +
Сколько в графе <math>K_n</math> простых циклов/циклов/путей длины <math>3 </math>? длины <math>n </math>?
  +
  +
  +
  +
Докажите, что любой цикл содержит простой цикл.
  +
Верно ли, что любой цикл нечётной длины содержит простой цикл нечётной длины? Верно ли аналогичное утверждение для циклов чётной длины?
  +
  +
  +
  +
Пусть в графе есть простой цикл проходящий через рёбра <math>a</math> и <math>b </math>, а также простой цикл, проходящий через рёбра <math>b</math> и <math>c</math>. Докажите, что есть простой цикл, проходящий через рёбра <math>a</math> и <math>c</math>.
  +
  +
  +
  +
В графе на <math>400</math> вершинах степень каждой вершины равна <math>201</math>. Докажите, что в этом графе есть цикл длины <math>3</math>.
  +
  +
  +
  +
Докажите, что отношение <<соединённость некоторым путём>> является отношением эквивалентности на множестве вершин графа.
  +
  +
  +
  +
Турист приехал на вокзал и пошёл гулять по улицам. Докажите, что он в любой момент может вернуться на вокзал, проходя лишь те участки улиц, которые он уже прошёл нечётное число раз.
  +
  +
  +
  +
В графе <math>n</math> вершин, степень каждой не менее <math>\frac{n-1}{2}</math>. Докажите, что он связен.
  +
  +
  +
  +
Перечислите все попарно неизоморфные графы с четырьмя вершинами, связные графы с пятью вершинами и пятью ребрами, несвязные графы с пятью вершинами.
  +
  +
  +
  +
Сколько существует попарно неизоморфных графов, имеющих 8 вершин и 25 рёбер?
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 2. || Деревья || Существует ли дерево на 9 вершинах, в котором 2 вершины имеют степень 5?
  +
  +
  +
  +
В дереве нет вершин степени 2. Докажите, что количество висячих вершин больше половины общего количества вершин.
  +
  +
  +
  +
Докажите, что каждый связный граф содержит остов.
  +
  +
  +
  +
Всегда ли в связном графе можно удалить некоторую вершину вместе со всеми выходящими из неё рёбрами так, чтобы граф остался связным?
  +
  +
  +
  +
Волейбольная сетка имеет вид прямоугольника размером <math>50 \times 600</math> клеток. Какое наибольшее число верёвочек можно перерезать так, чтобы сетка не распалась на куски?
  +
  +
  +
  +
Найдите количество деревьев с данными <math>n</math> вершинами, в которых вершина с номером <math>1</math> имеет степень <math>k</math>.
  +
  +
  +
  +
Найдите число лесов на множестве <math>\{1,2,\ldots,n\} </math>, состоящих из <math>k</math> деревьев, в которых вершины из <math>\{1,2,\ldots,k\}</math> принадлежат различным деревьям.
  +
  +
  +
  +
Последовательность из <math>n</math> натуральных чисел является последовательностью степеней вершин некоторого дерева тогда и только тогда, когда сумма ее членов равна <math>2n-2</math>.
  +
  +
  +
  +
Каких графов с данными <math>n</math> вершинами больше:
  +
  +
* имеющих изолированную вершину или не имеющих?
  +
  +
* связных или несвязных?
  +
  +
  +
  +
Каких графов больше, деревьев с данными <math>100</math> вершинами или унициклических графов с данными <math>98</math> вершинами?
  +
  +
  +
  +
Выразите число унициклических графов с данными <math>n</math> вершинами в виде суммы не более чем <math>n</math> слагаемых.
  +
  +
  +
  +
Найдите асимптотику числа унициклических графов с данными <math>n</math> вершинами.
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 3. || Эйлеровы пути и циклы в графах. || Сколькими способами рёбра в графе <math>K_5</math> можно разбить на непересекающиеся циклы?
  +
  +
  +
  +
При каком условии на ориентированный граф <math>G</math> в нём существует эйлеров цикл?
  +
  +
  +
  +
При каком условии на граф <math>G</math> в нём существует ‘’эйлеров путь’’, т.е. путь, проходящий по всем рёбрам графа?
  +
  +
  +
  +
  +
При каких <math>m,n</math> граф <math>K_n</math> эйлеров? граф <math>K_{m,n}</math> эйлеров?
  +
  +
  +
  +
На ребрах графа, у которого степень каждой вершины четна, можно поставить стрелки так, что у каждой вершины входящая степень будет совпадать с исходящей.
  +
  +
  +
  +
Если количество вершин нечетной степени в связном графе равно <math>2k </math>, то множество его ребер можно представить в виде объединения <math>k</math> путей, никакие два из которых не имеют общих ребер.
  +
  +
  +
  +
Математик забыл трехзначный код своего замка.
  +
Замок открывается, если три цифры кода набраны подряд (даже если перед этим были набраны другие цифры). Математик набирает одну цифру в секунду; набранная цифра добавляется в конец. Докажите, что математик сможет открыть замок за
  +
* <math>29</math> секунд, если в коде могут быть использованы только цифры <math>1 </math>, <math>3</math> и <math>7</math>.
  +
* <math>1002</math> секунды, если в коде могут быть использованы только десять цифр.
  +
Сформулируйте и докажите правило <math>0 < 1 < 2 \dots < 8 < 9</math> открытия замка за <math>1002</math> секунды.
  +
  +
  +
  +
Постройте двоичную последовательность Де Брёйна порядка
  +
<math>3 </math>, начинающуюся с <math>111 </math>,
  +
<math>4 </math>, начинающуюся с <math>1011 </math>,
  +
<math>4 </math>, заканчивающуюся на <math>1010</math>.
  +
  +
  +
  +
Дан связный ориентированный граф с вершинами <math>1,\ldots,n </math>, у которого входящая степень <math>d_k </math> каждой вершины <math>k</math> равна исходящей.
  +
  +
  +
  +
Существует дерево, содержащее все вершины ориентированного графа, у которого все ребра направлены в сторону вершины 1.
  +
  +
Фиксируем дерево <math>T</math> из \textbf{а)} .
  +
Будем обходить ориентированный граф (по стрелкам), проходя по каждому ребру не более одного раза.
  +
  +
Сначала выйдем из вершины 1 в произвольном направлении.
  +
  +
Далее, пусть мы пришли в некоторую вершину <math>v</math>.
  +
  +
Выходим из нее по любому ребру, не принадлежащему <math>T </math>, если это возможно.
  +
  +
А если невозможно, то выходим из нее по ребру, принадлежащему <math>T</math> (такое ребро единственно).
  +
  +
Докажите, что обход закончится в вершине 1 и что в результате обхода получится эйлеров цикл.
  +
  +
  +
  +
Число эйлеровых циклов в ориентированном графе кратно числу <math>(d_1-1)!\cdot\ldots\cdot(d_n-1)!. </math>
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 4. || Планарные и плоские графы || Для связного плоского графа без петель и кратных рёбер при <math>E \geq 2</math> выполнено неравенство <math>2E \geq 3F</math>.`
  +
  +
если <math>V \geq 3 </math>, то выполнено неравенство <math>E \leq 3V-6</math>.
  +
  +
Как можно улучшить неравенство в пункте а),
  +
если минимальная длина цикла равна <math>r </math>?
  +
  +
  +
  +
‘’Применения формулы Эйлера’’.
  +
Ни один из графов <math>K_5</math> и <math>K_{3,3}</math> невозможно без самопересечений нарисовать на плоскости.
  +
  +
  +
Для каких <math>r,s</math> полный двудольный граф <math>K_{r,s}</math> не планарный?
  +
  +
  +
  +
  +
В выпуклом многограннике все грани --- квадраты и шестиугольники.
  +
В каждой вершине встречаются ровно три грани. Какое количество квадратных граней может быть у данного многогранника?
  +
  +
  +
  +
(‘’Футбольный мяч’’) У выпуклого многогранника все грани — правильные пятиугольники или правильные шестиугольники. Докажите, что в каждой вершине этого многогранника сходятся ровно три грани.
  +
Сколько пятиугольных граней у данного многоугольника?
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 5. || Хроматическое число графа || Если в графе степень каждой вершины не превосходит <math>d </math>, то его можно правильно раскрасить в <math>d + 1</math> цвет.
  +
  +
Если в связном графе степень каждой вершины не превосходит <math>d </math>, и есть вершина степени меньше <math>d </math>, то его можно правильно
  +
раскрасить в <math>d</math> цветов.
  +
  +
Если в связном графе степень каждой вершины не превосходит <math>d </math>, и есть вершина, после удаления которой граф перестает
  +
быть связным, то граф можно правильно раскрасить в <math>d</math> цветов.
  +
  +
Если для графа с <math>n</math> вершинами и <math>e</math> ребрами при удалении
  +
любой вершины хроматическое число уменьшается, то граф можно
  +
правильно раскрасить в <math>1 + [2e/n]</math> цветов.
  +
  +
Если связный граф <math>G </math>, имеющий более двух вершин, при
  +
удалении некоторого ребра распадается на два графа, каждый из
  +
которых можно правильно раскрасить в <math>d</math> цветов, то и исходный
  +
граф можно правильно раскрасить в <math>d</math> цветов.
  +
  +
‘’Теорема Брукса’’ В графе степень каждой вершины не превосходит <math>d \geq 3</math> и нет полного подграфа с <math>d+1</math> вершиной. Докажите, что его можно правильно раскрасить в <math>d</math> цветов.
  +
  +
Если граф невозможно правильно раскрасить в <math>k-1</math> цвет, то для любой его правильной раскраски в <math>k</math> цветов существует путь, в котором встречается ровно по одной вершине каждого цвета.
  +
  +
Если максимальный несамопересекающийся путь в графе
  +
проходит через <math>d</math> вершин, то граф можно правильно раскрасить в <math>d</math> цветов.
  +
  +
Если максимальный нечетный несамопересекающийся цикл
  +
в графе проходит через <math>d - 1</math> вершину, то граф можно правильно раскрасить в <math>d</math> цветов.
  +
  +
Ориентированный граф, из каждой вершины выходит не более <math>d</math> ребер, можно правильно раскрасить в <math>2d + 1</math> цвет.
  +
  +
Вершины произвольного графа <math>G</math> можно перенумеровать так, чтобы жадный алгоритм его раскраски использовал ровно <math>\chi(G) </math> цветов.
  +
  +
  +
  +
Для каждого натурального <math>k</math> постройте двудольный граф <math>G </math>, раскраска которого, построенная жадным алгоритмом, имеет не менее <math>k</math> цветов.
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 6. || Паросочетания в графе || Какое минимальное количество рёбер можно удалить из графа <math>K_{n,n} </math>, чтобы не осталось ни одного совершенного паросочетания?
  +
  +
  +
  +
В каждой клетке доски <math>n \times n</math> написано неотрицательное вещественное число таким образом, что суммы в каждой горизонтали и вертикали равны <math>1</math>. Докажите, что можно расставить <math>n</math> небьющих друг друга ладей, под которыми стоят ненулевые числа
  +
  +
  +
  +
(Старинная задача) Есть <math>n</math> юношей и <math>n</math> девушек. Каждый юноша знает в точности <math>k</math> девушек и каждая девушка знает в точности <math>k</math> юношей. Докажите, что можно провести <math>k</math> танцев, в каждом танце юноша танцует со знакомой девушкой, все молодые люди разбиваются на пары, и никакая пара не повторяется (то за вечер юноша потанцует со всеми своими знакомыми).
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 7. || Гамильтоновы циклы и пути || Приведите пример гамильтонова не эйлерова графа; эйлерова не гамильтонова графа.
  +
  +
  +
  +
Связный граф <math>G</math> с <math>|V| \geq 3</math> вершинами и <math>2 + \frac{1}{2}(|V|-1)(|V|-2)</math> является гамильтоновым.
  +
  +
  +
  +
Существует ли негамильтонов граф с <math>1 + \frac{1}{2}(|V|-1)(|V|-2)</math> рёбрами?
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 8. || Введение в экстремальную комбинаторику || Если граф не содержит треугольников, то <math>e\le n^2/4. </math>
  +
  +
Если <math>e=[n^2/4]+1 </math>, то в графе есть по крайней мере <math>[n/2]</math> треугольников.
  +
  +
Если <math>n=km</math> и граф не содержит полного подграфа с <math>k+1</math> вершинами, то <math>2e\le k(k-1)m^2</math>.
  +
  +
(Переходя к дополнительному графу, получаем, что если <math>n=km</math> и среди любых <math>k+1</math> вершин некоторые две соединены ребром, то <math>2e\ge km(m-1)</math>.)
  +
  +
Eсли среди любых <math>k+1</math> вершин некоторые две соединены ребром, <math>m:=[n/k]</math> и <math>r:=k\{n/k\} </math>, то <math>2e\ge km(m-1)+2mr</math>.
  +
  +
Если граф двудолен и не содержит цикла длины 4, то <math>e\le n^{3/2}/2</math>.
  +
  +
В любом графе есть двудольный подграф, содержащий не менее половины ребер графа.
  +
  +
Если граф не содержит цикла длины 4, то <math>e\le n^{3/2}</math>.
  +
  +
Если граф не содержит подграфа <math>K_{2,3} </math>, то <math>e\le 2n^{3/2}</math>.
  +
  +
Если граф не содержит подграфа <math>K_{3,3} </math>, то <math>e\le 2n^{5/3}</math>.
  +
  +
Для любых целых <math>s,t </math>, \ <math>0<s\le t </math>, если граф с не содержит подграфа <math>K_{s,t} </math>, то <math>e\le (s+t)v^{2-1/s}</math>. Если ни один граф из последовательности графов <math>G_v</math> с <math>v</math> вершинами и <math>e_v</math> ребрами не содержит подграфа <math>K_{s,t} </math>, то <math>e_v=O(v^{2-1/s})</math> при <math>v\to\infty</math>.
  +
  +
Для любых <math>n</math> точек на плоскости существует не более <math>n</math> диаметров, т.е. (неупорядоченных) пар точек, расстояние между которыми равно диаметру множества этих точек.
  +
  +
  +
  +
Пусть дано множество <math>V</math> из <math>n</math> точек на плоскости диаметра <math>d</math>. Графом диаметров <math>G=(V,E)</math> на этом множестве точек называется граф, у которого ребрами соединены точки, отстоящие друг от друга на расстояние <math>d</math>. Докажите, что для любого <math>V</math> мощности <math>n</math> верно, что <math>|E|\le n.</math> Приведите пример графа, для которого эта оценка достигается.
  +
  +
  +
  +
Для любых <math>n</math> точек <math>A_1,\dots,A_n</math> в <math>\R^d</math> обозначим через <math>D(A_1,\dots,A_n) </math>, число (неупорядоченных) пар точек, расстояние между которыми равно 1.
  +
  +
Обозначим <math>E_n(d)=\max\{D(A_1,\dots,A_n) \ :\ A_1,\dots,A_n\in\R^d\}.</math>
  +
  +
Обозначим через <math>E_n </math> максимальное, по всем наборам из <math>n</math> точек в <math>\R^d </math>, число (неупорядоченных) пар точек набора, расстояние между которыми равно 1.
  +
  +
<math>E_n(2)>n[\log_2n]/4</math>.
  +
  +
<math>E_n(2)\le 2n^{3/2}</math>.
  +
  +
<math>E_n(3)\le 2n^{5/3}</math>.
  +
  +
<math>\dfrac {(n-1)^2}4\le E_n(4)\le \dfrac{2(n+4)^2}5. </math>
  +
  +
Пусть <math>V</math> --- <math>11^k</math>-элементное подмножество пространства <math>\R^k </math>, любое <math>10^k</math>-эле\-мент\-ное подмножество которого содержит две точки <math>x,y</math> на расстоянии 1: <math>|x-y|=1</math>.
  +
  +
Докажите, что для достаточно большого <math>k</math> количество единичных расстояний между точками множества <math>V</math> больше, чем <math>12^k/2</math>: <math>\frac12\left|\{(x,y)\in V\times V\colon\, |x-y|=1\}\right|>\frac{12^k}2. </math> где через <math>\#A</math> обозначено число элементов в множестве <math>A</math>.
  +
  +
То же больше, чем <math>12.1^k</math>.
  +
  +
 
|}
 
|}
  +
 
'''Текущий контроль успеваемости обучающихся по дисциплине:'''
 
'''Текущий контроль успеваемости обучающихся по дисциплине:'''
   
<span style="color:red;">(К формам текущего контроля можно отнести собеседование, коллоквиум, тест, контрольную работу, лабораторную работу, эссе, реферат и иные творческие работы.)</span>
 
 
{| class="wikitable" style="width:70%;"
 
{| class="wikitable" style="width:70%;"
 
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
 
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
 
| style="width:5%" | №<br>п/п
 
| style="width:5%" | №<br>п/п
 
| style="width:20%" | Наименование раздела<br>дисциплины
 
| style="width:20%" | Наименование раздела<br>дисциплины
| style="width:25%" | Форма текущего контроля<br><br><span style="color:red;">(выберите соответствующие формы контроля)</span>
+
| style="width:25%" | Форма текущего контроля<br>
| style="width:50%" | Материалы текущего контроля<br><br><span style="color:red;">(Указываются ВСЕ ЗАДАНИЯ/ВОПРОСЫ текущего контроля успеваемости обучающихся по разделам дисциплины подробно в соответствии с требованиями)</span>
+
| style="width:50%" | Материалы текущего контроля<br>
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 1 || Базовые понятия теории графов || Домашние работы || В домашние работы включаются задачи, нерешенные во время семинарских занятий.
| style="text-align:center;" | 1.
 
  +
|- style="background-color:#F8F9FA; color:#202122;"
|
 
  +
| style="text-align:center;" | 2 || Деревья || Домашние работы || В домашние работы включаются задачи, нерешенные во время семинарских занятий.
| style="text-align:center;" | <span style="color:red;">Проверка выполнения домашних заданий;<br>Устный / письменный опрос;<br>Тестирование (письменное или компьютерное);<br>Эссе;<br>Доклад;<br>Защита проекта; Коллоквиум;<br>Проверка разработки отдельных частей кода программного продукта и другие формы текущего контроля, используемые Вами на занятиях</span>
 
  +
|- style="background-color:#F8F9FA; color:#202122;"
| Например:
 
  +
| style="text-align:center;" | 3 || Эйлеровы пути и циклы в графах. || Домашние работы || В домашние работы включаются задачи, нерешенные во время семинарских занятий.
Устный / письменный опрос:<br>-<br>-<br>-<br>...<br>
 
  +
|- style="background-color:#F8F9FA; color:#202122;"
Тематика групповых проектов:<br>-<br>-<br>-<br>...<br>
 
  +
| style="text-align:center;" | 4 || Планарные и плоские графы || Домашние работы || В домашние работы включаются задачи, нерешенные во время семинарских занятий.
Темы докладов:<br>-<br>-<br>-<br>...<br>
 
  +
|- style="background-color:#F8F9FA; color:#202122;"
Тематика эссе:<br>-<br>-<br>-<br>...<br>
 
  +
| style="text-align:center;" | 5 || Хроматическое число графа || Домашние работы || В домашние работы включаются задачи, нерешенные во время семинарских занятий.
Задания, в том числе, для групповых проектов:<br>-<br>-<br>-<br>...<br>
 
  +
|- style="background-color:#F8F9FA; color:#202122;"
Тестирование (письменное или компьютерное):<br>-<br>-<br>-<br>...<br><br>
 
  +
| style="text-align:center;" | 6 || Паросочетания в графе || Домашние работы || В домашние работы включаются задачи, нерешенные во время семинарских занятий.
Проверка разработки отдельных частей кода программного продукта.
 
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 7 || Гамильтоновы циклы и пути || Домашние работы || В домашние работы включаются задачи, нерешенные во время семинарских занятий.
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 8 || Введение в экстремальную комбинаторику || Домашние работы || В домашние работы включаются задачи, нерешенные во время семинарских занятий.
   
Другие формы текущего контроля, используемые Вами на занятиях<br>-<br>-<br>-<br>...<br>
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 2.
 
|
 
| style="text-align:center;" | <span style="color:red;">Проверка выполнения домашних заданий;<br>Устный / письменный опрос;<br>Тестирование (письменное или компьютерное);<br>Эссе;<br>Доклад;<br>Защита проекта; Коллоквиум;<br>Проверка разработки отдельных частей кода программного продукта и другие формы текущего контроля, используемые Вами на занятиях</span>
 
|
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 3.
 
|
 
| style="text-align:center;" | <span style="color:red;">Проверка выполнения домашних заданий;<br>Устный / письменный опрос;<br>Тестирование (письменное или компьютерное);<br>Эссе;<br>Доклад;<br>Защита проекта; Коллоквиум;<br>Проверка разработки отдельных частей кода программного продукта и другие формы текущего контроля, используемые Вами на занятиях</span>
 
|
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 4.
 
|
 
| style="text-align:center;" | <span style="color:red;">Проверка выполнения домашних заданий;<br>Устный / письменный опрос;<br>Тестирование (письменное или компьютерное);<br>Эссе;<br>Доклад;<br>Защита проекта; Коллоквиум;<br>Проверка разработки отдельных частей кода программного продукта и другие формы текущего контроля, используемые Вами на занятиях</span>
 
|
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 5.
 
|
 
| style="text-align:center;" | <span style="color:red;">Проверка выполнения домашних заданий;<br>Устный / письменный опрос;<br>Тестирование (письменное или компьютерное);<br>Эссе;<br>Доклад;<br>Защита проекта; Коллоквиум;<br>Проверка разработки отдельных частей кода программного продукта и другие формы текущего контроля, используемые Вами на занятиях</span>
 
|
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | ... || || ||
 
 
|}
 
|}
  +
 
'''Контрольные вопросы для подготовки к промежуточной аттестации:'''
 
'''Контрольные вопросы для подготовки к промежуточной аттестации:'''
 
{| class="wikitable" style="width:70%;"
 
{| class="wikitable" style="width:70%;"
Line 116: Line 445:
 
| style="width:25%" | Наименование <br> раздела дисциплины
 
| style="width:25%" | Наименование <br> раздела дисциплины
 
| style="width:65%" | Вопросы
 
| style="width:65%" | Вопросы
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
|- style="background-color:#F8F9FA; color:#202122;"
| style="text-align:center;" | 1. || ||
+
| style="text-align:center;" | 1 || Базовые понятия теории графов || 1)Граф, ориентированный граф, мультиграф.
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
  +
2) Вершина, ребро, степень вершины. Полный граф. Лемма о рукопожатиях.
| style="text-align:center;" | 2. || ||
 
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
  +
3) Маршруты, пути, циклы, простые пути, простые циклы.
| style="text-align:center;" | 3. || ||
 
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
  +
4) Связность, компонента связности. Изоморфизм графов, подграфы, индуцированные подграфы
| style="text-align:center;" | 4. || ||
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
+
|- style="background-color:#F8F9FA; color:#202122;"
| style="text-align:center;" | 5. || ||
+
| style="text-align:center;" | 2 || Деревья || 5) Дерево, висячая вершина, остов.
  +
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
  +
6) Эквивалентные определения деревьев
| style="text-align:center;" | ... || ||
 
  +
  +
7)Существование висячей вершины в связном ацикличном графе.
  +
  +
8) Код Прюфера. Теорема Кэли
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 3 || Эйлеровы пути и циклы в графах. || 9) Эйлеров цикл, путь и эйлеров граф.
  +
  +
10) Последовательность де Брёйна и граф де Брёйна. Правило <<0 лучше 1>>
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 4 || Планарные и плоские графы || 11) Планарные и плоские графы. Грань плоского графа. Формула Эйлера .
  +
  +
12) Пример непланарного графа
  +
  +
13) Классификация правильных многогранников
  +
  +
14) Раскраска карт, хроматическое число планарного графа.
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 5 || Хроматическое число графа || 15) Соотношения между хроматическим числом, числом независимости и кликовым числом.
  +
  +
16) Связь между хроматическим числом и максимальной степенью вершины
  +
  +
17) Хроматическое число пространства. Доказательство конечности. Известные нижние и верхние оценки (б/д). Связь с хроматическим числом дистанционного графа.
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 6 || Паросочетания в графе || 18) Максимальное и совершенное паросочетания. Теорема Холла о совершенном паросочетании в двудольном графе
  +
  +
19) Теорема Кёнига о максимальном паросочетании и минимальном вершинном покрытии в двудольном графе
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 7 || Гамильтоновы циклы и пути || 20) Гамильтонов путь и цикл, гамильтонов граф.
  +
  +
21) Достаточное условие Дирака и Оре гамильтоновости графа.
  +
  +
22)Вершинная связность и число независимости графа. Признак Эрдёша-Хватала.
  +
  +
23)Гамильтоновость графа 1-пересечений 3-элементных подмножеств n-элементного множества при всех всех достаточно больших n.
  +
|- style="background-color:#F8F9FA; color:#202122;"
  +
| style="text-align:center;" | 8 || Введение в экстремальную комбинаторику || 24) Теорема Турана о числе ребер в графе с данным числом вершин и числом независимости.
  +
  +
25) Асимптотика наибольшего числа ребер в графе с n вершинами без k-клик.
  +
  +
 
|}
 
|}
 
'''Вопросы/Задания к промежуточной аттестации в устной/письменной форме:'''
 
'''Вопросы/Задания к промежуточной аттестации в устной/письменной форме:'''
   
  +
1)Граф, ориентированный граф, мультиграф.
<span style="color:red;">(Указываются ВСЕ ЗАДАНИЯ/ВОПРОСЫ для промежуточной аттестации.)</span>
 
  +
  +
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-клик.
  +
  +
   
1.<br>2.<br>3.<br>...<br>48.<br>49.<br>50.<br>...
 
 
=== Перечень учебно-методического обеспечения дисциплины ===
 
=== Перечень учебно-методического обеспечения дисциплины ===
 
Список основной литературы:
 
Список основной литературы:
   
  +
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 с.
  +
  +
  +
 
=== Методические указания для обучающихся по освоению дисциплины ===
 
=== Методические указания для обучающихся по освоению дисциплины ===
<span style="color:red;">(Указываются рекомендации для обучающихся, которые раскрывают суть их работы при различных видах деятельности в рамках освоения дисциплины. Данные рекомендации должны охватывать работу с лекционным материалом, подготовку и работу во время проведения семинарских занятий, самостоятельную работу, подготовку к текущему контролю и промежуточной аттестации)</span>
 
   
<span style="color:red;">(Выберите соответствующие виды учебных занятий, которые используются при изучении Вашей дисциплины)</span>
 
 
{| class="wikitable" style="width:80%;"
 
{| class="wikitable" style="width:80%;"
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#FF0000; font-weight:bold;"
+
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; font-weight:bold;"
 
| style="width:20%" | Вид учебных<br>занятий/деятельности
 
| style="width:20%" | Вид учебных<br>занятий/деятельности
 
| style="width:80%" | Деятельность обучающегося
 
| style="width:80%" | Деятельность обучающегося
  +
|- style="background-color:#F8F9FA; color:#202122;"
|-
 
  +
| style="text-align:center;" | Лекция || Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
| style="vertical-align:middle; text-align:center; color:red;" | Лекция
 
  +
|- style="background-color:#F8F9FA; color:#202122;"
| style="vertical-align:middle; text-align:left; color:red;" | Написание конспекта лекций: кратко, схематично, последовательно фиксировать основные положения лекции, выводы, формулировки, обобщения; помечать важные мысли, выделять ключевые слова, термины. Обозначить вопросы, термины или другой материал, который вызывает трудности, пометить и попытаться найти ответ в рекомендуемой литературе. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия.
 
  +
| style="text-align:center;" | Практическое (семинарское) занятие || При подготовке к семинарскому (практическому) занятию необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. На основании обработанной информации постараться сформировать собственное мнение по выносимой на обсуждение тематике. Обосновать его аргументами, сформировать список источников, подкрепляющих его.
|-
 
  +
Во время семинарского (практического) занятия активно участвовать в обсуждении вопросов, высказывать аргументированную точку зрения на проблемные вопросы. Приводить примеры из источниковой базы и научной и/или исследовательской литературы.
| style="vertical-align:middle; text-align:center; color:red;" | Практическое (семинарское) занятие
 
  +
|- style="background-color:#F8F9FA; color:#202122;"
| style="vertical-align:middle; text-align:left; color:red;" | При подготовке к семинарскому (практическому) занятию необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме. На основании обработанной информации постараться сформировать собственное мнение по выносимой на обсуждение тематике. Обосновать его аргументами, сформировать список источников, подкрепляющих его.<br>Во время семинарского (практического) занятия активно участвовать в обсуждении вопросов, высказывать аргументированную точку зрения на проблемные вопросы. Приводить примеры из источниковой базы и научной и/или исследовательской литературы.
 
  +
| style="text-align:center;" | Устный/письменный опрос || Отвечать, максимально полно, логично и структурировано, на поставленный вопрос. Основная цель – показать всю глубину знаний по конкретной теме или ее части.
|-
 
  +
|- style="background-color:#F8F9FA; color:#202122;"
| style="vertical-align:middle; text-align:center; color:red;" | Устный/письменный опрос
 
  +
| style="text-align:center;" | Контрольная работа || При подготовке к контрольной работе необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме.
| style="vertical-align:middle; text-align:left; color:red;" | Отвечать, максимально полно, логично и структурировано, на поставленный вопрос. Основная цель – показать всю глубину знаний по конкретной теме или ее части.
 
  +
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Реферат
 
| style="vertical-align:middle; text-align:left; color:red;" | Поиск источников и литературы, составление библиографии. При написании реферата рекомендуется использовать разнообразные источники, монографии и статьи из научных журналов, позволяющие глубже разобраться в различных точках зрения на заданную тему. Изучение литературы следует начинать с наиболее общих трудов, затем следует переходить к освоению специализированных исследований по выбранной теме. Могут быть использованы ресурсы сети «Интернет» с соответствующими ссылками на использованные сайты.<br>Если тема содержит проблемный вопрос, следует сформулировать разные точки зрения на него. Рекомендуется в выводах указать свое собственное аргументированное мнение по данной проблеме. Подготовить презентацию для защиты реферата.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Эссе
 
| style="vertical-align:middle; text-align:left; color:red;" | Написание прозаического сочинения небольшого объема и свободной композиции, выражающего индивидуальные впечатления и соображения по конкретному поводу или вопросу и заведомо не претендующего на определяющую или исчерпывающую трактовку предмета. При работе над эссе следует четко и грамотно формулировать мысли, структурировать информацию, использовать основные понятия, выделять причинно-следственные связи. Как правило эссе имеет следующую структуру: вступление, тезис и аргументация его, заключение. В качестве аргументов могут выступать исторические факты, явления общественной жизни, события, жизненные ситуации и жизненный опыт, научные доказательства, ссылки на мнение ученых и др.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Подготовка к промежуточной аттестации
 
| style="vertical-align:middle; text-align:left; color:red;" | При подготовке к промежуточной аттестации необходимо проработать вопросы по темам, которые рекомендуются для самостоятельной подготовки. При возникновении затруднений с ответами следует ориентироваться на конспекты лекций, семинаров, рекомендуемую литературу, материалы электронных и информационных справочных ресурсов, статей.<br>Если тема вызывает затруднение, четко сформулировать проблемный вопрос и задать его преподавателю.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Практические (лабораторные) занятия
 
| style="vertical-align:middle; text-align:left; color:red;" | Практические занятия предназначены прежде всего для разбора отдельных сложных положений, тренировки аналитических навыков, а также для развития коммуникационных навыков. Поэтому на практических занятиях необходимо участвовать в тех формах обсуждения материала, которые предлагает преподаватель: отвечать на вопросы преподавателя, дополнять ответы других студентов, приводить примеры, задавать вопросы другим выступающим, обсуждать вопросы и выполнять задания в группах. Работа на практических занятиях подразумевает домашнюю подготовку и активную умственную работу на самом занятии. Работа на практических занятиях в форме устного опроса заключается прежде всего в тренировке навыков применять теоретические положения к самому разнообразному материалу. В ходе практических занятий студенты работают в группах для обсуждения предлагаемых вопросов.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Самостоятельная работа
 
| style="vertical-align:middle; text-align:left; color:red;" | Самостоятельная работа состоит из следующих частей: 1) чтение учебной, справочной, научной литературы; 2) повторение материала лекций; 3) составление планов устных выступлений; 4) подготовка видеопрезентации. При чтении учебной литературы нужно разграничивать для себя материал на отдельные проблемы, концепции, идеи. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Видеопрезентация
 
| style="vertical-align:middle; text-align:left; color:red;" | Подготовка видеопрезентаций по курсу. Видеопрезентации могут быть сделаны на любую тему, затронутую в ходе курса. Темы должны быть заранее согласованы с преподавателем. Видеопрезентации продолжительностью около 5 минут (300 секунд) должны быть подготовлены в группах, определяемых преподавателем. Несмотря на то, что это групповая работа, должен явно присутствовать вклад каждого члена группы.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Доклад
 
| style="vertical-align:middle; text-align:left; color:red;" | Публичное, развернутое сообщение по определенной теме или вопросу, основанное на документальных данных. При подготовке доклада рекомендуется использовать разнообразные источники, позволяющие глубже разобраться в теме. Учебную литературу можно найти в электронных библиотечных системах, на которые подписан АНО Университет Иннополис.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Дискуссия
 
| style="vertical-align:middle; text-align:left; color:red;" | Публичное обсуждение спорного вопроса, проблемы. Каждая сторона должна оппонировать мнение собеседника, аргументируя свою позицию.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Контрольная работа
 
| style="vertical-align:middle; text-align:left; color:red;" | При подготовке к контрольной работе необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Тестирование (устное/письменное)
 
| style="vertical-align:middle; text-align:left; color:red;" | При подготовке к тестированию необходимо проработать материалы лекций, семинаров, основной и дополнительной литературы по заданной теме. Основная цель тестирования – показать уровень сформированности знаний по конкретной теме или ее части.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Индивидуальная работа
 
| style="vertical-align:middle; text-align:left; color:red;" | При выполнение индивидуальной работы необходимо взять задание у преподавателя, ознакомиться с требованиями к выполнению работы, изучить поставленную проблему, найти решение проблемы. Если самостоятельно не удается разобраться в материале, необходимо сформулировать вопрос и задать преподавателю на консультации, во время семинарского (практического) занятия. Оформить результаты работы.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Разработка отдельных частей кода
 
| style="vertical-align:middle; text-align:left; color:red;" | Разработать часть кода, исходя из поставленной задачи и рекомендаций преподавателя. При выполнении работы рекомендуется обращаться к материалам лекций и семинарских (практических) занятий. Если возникают затруднения, необходимо проконсультироваться с преподавателем.
 
|-
 
| style="vertical-align:middle; text-align:center; color:red;" | Выполнение домашних заданий и групповых проектов
 
| style="vertical-align:middle; text-align:left; color:red;" | Для выполнения домашних заданий и групповых проектов необходимо получить формулировку задания от преподавателя и убедиться в понимании задания. При выполнение домашних заданий и групповых проектов необходимо проработать материалы лекций, основной и дополнительной литературы по заданной теме.
 
 
|}
 
|}
 
=== Методы и технологии обучения, способствующие формированию компетенции ===
 
=== Методы и технологии обучения, способствующие формированию компетенции ===
<span style="color:red;">(Указываются все используемые преподавателем методы и технологии обучения)</span>
 
 
{| class="wikitable"
 
{| class="wikitable"
 
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
 
|- style="vertical-align:middle; text-align:center; background-color:#EAECF0; color:#202122; font-weight:bold;"
 
| Методы и технологии обучения, способствующие формированию компетенции
 
| Методы и технологии обучения, способствующие формированию компетенции
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
 
|- style="vertical-align:middle; background-color:#F8F9FA; color:#202122;"
  +
| Информационно – коммуникационная технология, Педагогика сотрудничества, Традиционные технологии, Модульная технология
| &nbsp;
 
|}
 
<span style="color:red;">Например:</span>
 
{| class="wikitable" style="width:80%;"
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center; width:5%;" | 1.
 
| style="width:20%;" | Информационно – коммуникационная технология
 
| style="width:75%;" | &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 2.
 
| Технология развития критического мышления
 
| Основные методические приемы развития критического мышления
 
# Прием «Кластер»
 
# Таблица
 
#Учебно-мозговой штурм
 
#Интеллектуальная разминка
 
#Зигзаг, зигзаг -2
 
#Прием «Инсерт»
 
#Эссе
 
#Приём «Корзина идей»
 
#Приём «Составление синквейнов»
 
#Метод контрольных вопросов
 
#Приём «Знаю../Хочу узнать…/Узнал…»
 
#Круги по воде
 
#Ролевой проект
 
#Да – нет
 
#Приём «Чтение с остановками»
 
#Приём «Взаимоопрос»
 
#Приём «Перепутанные логические цепочки»
 
#Приём «Перекрёстная дискуссия»
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 3.
 
| Проектная технология
 
| &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 4.
 
| Технология проблемного обучения
 
| &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 5.
 
| Кейс – технология
 
| К методам кейс-технологий, активизирующим учебный процесс, относятся:
 
*метод ситуационного анализа (Метод анализа конкретных ситуаций, ситуационные задачи и упражнения; кейс-стадии)
 
*метод инцидента;
 
*метод ситуационно-ролевых игр;
 
*метод разбора деловой корреспонденции;
 
*игровое проектирование;
 
*метод дискуссии.
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 6.
 
| Технология интегрированного обучения
 
| &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 7.
 
| Педагогика сотрудничества
 
| &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 8.
 
| Технологии уровневой дифференциации
 
| &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 9.
 
| Групповая технология
 
| &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 10.
 
| Традиционные технологии (классно-урочная система)
 
| &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 11.
 
| Здоровьесберегающие технологии
 
| &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 12.
 
| Игровая технология
 
| &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 13.
 
| Модульная технология
 
|
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| style="text-align:center;" | 14.
 
| Технология мастерских
 
| &nbsp;
 
|- style="vertical-align:top; text-align:left; background-color:#F8F9FA; color:#202122;"
 
| &nbsp;
 
| и др.
 
| &nbsp;
 
 
|}
 
|}

Latest revision as of 02:28, 4 April 2024

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

Квалификация выпускника: бакалавр
Направление подготовки: 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. Планарные и плоские графы Для связного плоского графа без петель и кратных рёбер при выполнено неравенство .`

если , то выполнено неравенство .

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


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


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



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


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

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

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

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

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

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

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

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

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

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

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

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


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

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


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


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

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


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


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

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

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

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

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

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

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

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

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

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

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

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

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


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


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

Обозначим

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

.

.

.

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

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

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


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


п/п
Наименование раздела
дисциплины
Форма текущего контроля
Материалы текущего контроля
1 Базовые понятия теории графов Домашние работы В домашние работы включаются задачи, нерешенные во время семинарских занятий.
2 Деревья Домашние работы В домашние работы включаются задачи, нерешенные во время семинарских занятий.
3 Эйлеровы пути и циклы в графах. Домашние работы В домашние работы включаются задачи, нерешенные во время семинарских занятий.
4 Планарные и плоские графы Домашние работы В домашние работы включаются задачи, нерешенные во время семинарских занятий.
5 Хроматическое число графа Домашние работы В домашние работы включаются задачи, нерешенные во время семинарских занятий.
6 Паросочетания в графе Домашние работы В домашние работы включаются задачи, нерешенные во время семинарских занятий.
7 Гамильтоновы циклы и пути Домашние работы В домашние работы включаются задачи, нерешенные во время семинарских занятий.
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 с.


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

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

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

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

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

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