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

Квалификация выпускника: бакалавр

Направление подготовки: 09.03.01 - “Информатика и вычислительная техника”

Направленность (профиль) образовательной программы: Математические основы ИИ

Программу разработал(а):

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

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

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

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

Задачами дисциплины являются изучение математических основ современной комбинаторики;

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

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

Знания: сформированы систематические знания по комбинаторике и дискретной математике

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

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

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

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

№ п/п	Наименование раздела дисциплины	Содержание дисциплины по темам
1.	Базовые понятия теории графов	- определение графа, орграфа, мультиграфа - вершины, рёбра, степень вершины, лемма о рукопожатиях - маршрут, путь, цикл - связность, компонента связности - подграф, индуцированный подграф, изоморфизм
2.	Деревья	- эквивалентные определения дерева - количество рёбер в дереве - остов графа - лес, унициклический граф - теорема Кэли
3.	Эйлеровы пути и циклы в графах.	- Эйлеров обход графа - критерий эйлерова цикла, пути, в том числе в орграфе - применения: последовательности де Брёйна
4.	Планарные и плоские графы	- укладка графа на плоскости. понятие грани - формула Эйлера для связного и не связного графа - примеры непланарных графов - критерий Понтрягина-Куратовского - графы на сфере, классификация правильных многогранников - задача о четырёх красках. Хроматическое число планарного графа, верхняя оценка 5 и 6.
5.	Хроматическое число графа	- клики и независимые множества - правильная раскраска, хроматическое число графа, тривиальные оценки - связь хроматического числа с максимальной степенью вершины - жадный алгоритм правильной раскраски, его точность - хроматическое число графа не больше 2 и двудольность
6	Паросочетания в графе	- паросочетания, максимальное паросочетания, совершенное паросочетание - лемма Холла о совершенном паросочетании в двудольном графе - задача о системах различных представителей, перманент - чередующиеся цепи - минимальное вершинное покрытие, связь с максимальным паросочетанием в двудольном графе (т. Кёнига)
7	Гамильтоновы циклы и пути	- Гамильтоновы циклы и пути - критерии Оре и Дирака гамильтоновсти - критерий Эрдеша-Хватала
8	Введение в экстремальную комбинаторику	- максимальное количество рёбер в графе без l-клик (т. Турана) - структура графа без l-клик - дистанционные графы, оценка числа ребер у дистанционного графа в произвольной размерности

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

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

№ п/п	Наименование раздела дисциплины (модуля)	Перечень рассматриваемых тем (вопросов)
1.	Базовые понятия теории графов	Как связаны сумма степеней вершин любого графа и количество его рёбер? Верно ли, что число вершин нечётной степени любого графа чётно? Существует ли граф с заданным набором степеней Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (2,2,2,3,3)} ; Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (0,1,2,3,4) } ; Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (1,2,3,3,4,4) } ; Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (7,7,6,4,4,2,2,2)} ; Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (6,6,6,7,7,5,5,5,4,3) } ? В группе 21 студент. Докажите, что хотя бы двое из них имеют поровну друзей в классе. Ученик Ян заметил: у остальных 20-ти разное число друзей в классе. Сколько из них дружат с Яном? Сколько в графе Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_n} рёбер? Сколько в графе Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_n} простых циклов/циклов/путей длины $3$ ? длины Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n } ? Докажите, что любой цикл содержит простой цикл. Верно ли, что любой цикл нечётной длины содержит простой цикл нечётной длины? Верно ли аналогичное утверждение для циклов чётной длины? Пусть в графе есть простой цикл проходящий через рёбра Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} и Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b } , а также простой цикл, проходящий через рёбра Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle b} и Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} . Докажите, что есть простой цикл, проходящий через рёбра Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a} и Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle c} . В графе на Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 400} вершинах степень каждой вершины равна Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 201} . Докажите, что в этом графе есть цикл длины Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3} . Докажите, что отношение <<соединённость некоторым путём>> является отношением эквивалентности на множестве вершин графа. Турист приехал на вокзал и пошёл гулять по улицам. Докажите, что он в любой момент может вернуться на вокзал, проходя лишь те участки улиц, которые он уже прошёл нечётное число раз. В графе Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} вершин, степень каждой не менее Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac{n-1}{2}} . Докажите, что он связен. Перечислите все попарно неизоморфные графы с четырьмя вершинами, связные графы с пятью вершинами и пятью ребрами, несвязные графы с пятью вершинами. Сколько существует попарно неизоморфных графов, имеющих 8 вершин и 25 рёбер?
2.	Деревья	Существует ли дерево на 9 вершинах, в котором 2 вершины имеют степень 5? В дереве нет вершин степени 2. Докажите, что количество висячих вершин больше половины общего количества вершин. Докажите, что каждый связный граф содержит остов. Всегда ли в связном графе можно удалить некоторую вершину вместе со всеми выходящими из неё рёбрами так, чтобы граф остался связным? Волейбольная сетка имеет вид прямоугольника размером Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 50 \times 600} клеток. Какое наибольшее число верёвочек можно перерезать так, чтобы сетка не распалась на куски? Найдите количество деревьев с данными Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} вершинами, в которых вершина с номером Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} имеет степень Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} . Найдите число лесов на множестве Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{1,2,\ldots,n\} } , состоящих из Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} деревьев, в которых вершины из Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \{1,2,\ldots,k\}} принадлежат различным деревьям. Последовательность из Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} натуральных чисел является последовательностью степеней вершин некоторого дерева тогда и только тогда, когда сумма ее членов равна Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2n-2} . Каких графов с данными Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} вершинами больше: имеющих изолированную вершину или не имеющих? связных или несвязных? Каких графов больше, деревьев с данными Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 100} вершинами или унициклических графов с данными Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 98} вершинами? Выразите число унициклических графов с данными Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} вершинами в виде суммы не более чем Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} слагаемых. Найдите асимптотику числа унициклических графов с данными Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} вершинами.
3.	Эйлеровы пути и циклы в графах.	Сколькими способами рёбра в графе Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_5} можно разбить на непересекающиеся циклы? При каком условии на ориентированный граф Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} в нём существует эйлеров цикл? При каком условии на граф Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} в нём существует ‘’эйлеров путь’’, т.е. путь, проходящий по всем рёбрам графа? При каких Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m,n} граф Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_n} эйлеров? граф Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_{m,n}} эйлеров? На ребрах графа, у которого степень каждой вершины четна, можно поставить стрелки так, что у каждой вершины входящая степень будет совпадать с исходящей. Если количество вершин нечетной степени в связном графе равно Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2k } , то множество его ребер можно представить в виде объединения Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} путей, никакие два из которых не имеют общих ребер. Математик забыл трехзначный код своего замка. Замок открывается, если три цифры кода набраны подряд (даже если перед этим были набраны другие цифры). Математик набирает одну цифру в секунду; набранная цифра добавляется в конец. Докажите, что математик сможет открыть замок за Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 29} секунд, если в коде могут быть использованы только цифры Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 } , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3} и Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 7} . Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1002} секунды, если в коде могут быть использованы только десять цифр. Сформулируйте и докажите правило Failed to parse (syntax error): {\displaystyle ‘0 < 1 < 2 \dots < 8 < 9’ } открытия замка за Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1002} секунды. Постройте двоичную последовательность Де Брёйна порядка Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 3 } , начинающуюся с Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 111 } , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 4 } , начинающуюся с Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1011 } , Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 4 } , заканчивающуюся на Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1010} . Дан связный ориентированный граф с вершинами Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1,\ldots,n } , у которого входящая степень Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d_k } каждой вершины Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} равна исходящей. Существует дерево, содержащее все вершины ориентированного графа, у которого все ребра направлены в сторону вершины 1. Фиксируем дерево Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} из \textbf{а)} . Будем обходить ориентированный граф (по стрелкам), проходя по каждому ребру не более одного раза. Сначала выйдем из вершины 1 в произвольном направлении. Далее, пусть мы пришли в некоторую вершину Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} . Выходим из нее по любому ребру, не принадлежащему Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T } , если это возможно. А если невозможно, то выходим из нее по ребру, принадлежащему Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle T} (такое ребро единственно). Докажите, что обход закончится в вершине 1 и что в результате обхода получится эйлеров цикл. Число эйлеровых циклов в ориентированном графе кратно числу Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle (d_1-1)!\cdot\ldots\cdot(d_n-1)!. }
4.	Планарные и плоские графы	Для связного плоского графа без петель и кратных рёбер при Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \E \geq 2} выполнено неравенство Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2\E \geq 3\F} .` если Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \V \geq 3 } , то выполнено неравенство Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \E \leq 3\V-6} . Как можно улучшить неравенство в пункте а), если минимальная длина цикла равна Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r } ? ‘’Применения формулы Эйлера’’. Ни один из графов Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_5} и Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_{3,3}} невозможно без самопересечений нарисовать на плоскости. Для каких Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r,s} полный двудольный граф Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_{r,s}} не планарный? В выпуклом многограннике все грани --- квадраты и шестиугольники. В каждой вершине встречаются ровно три грани. Какое количество квадратных граней может быть у данного многогранника? (‘’Футбольный мяч’’) У выпуклого многогранника все грани — правильные пятиугольники или правильные шестиугольники. Докажите, что в каждой вершине этого многогранника сходятся ровно три грани. Сколько пятиугольных граней у данного многоугольника?
5.	Хроматическое число графа	Если в графе степень каждой вершины не превосходит Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d } , то его можно правильно раскрасить в Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d + 1} цвет. Если в связном графе степень каждой вершины не превосходит Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d } , и есть вершина степени меньше Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d } , то его можно правильно раскрасить в Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} цветов. Если в связном графе степень каждой вершины не превосходит Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d } , и есть вершина, после удаления которой граф перестает быть связным, то граф можно правильно раскрасить в Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} цветов. Если для графа с Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} вершинами и Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e} ребрами при удалении любой вершины хроматическое число уменьшается, то граф можно правильно раскрасить в Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 + [2e/n]} цветов. Если связный граф Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G } , имеющий более двух вершин, при удалении некоторого ребра распадается на два графа, каждый из которых можно правильно раскрасить в Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} цветов, то и исходный граф можно правильно раскрасить в Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} цветов. ‘’Теорема Брукса’’ В графе степень каждой вершины не превосходит Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d \geq 3} и нет полного подграфа с Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d+1} вершиной. Докажите, что его можно правильно раскрасить в Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} цветов. Если граф невозможно правильно раскрасить в Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k-1} цвет, то для любой его правильной раскраски в Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} цветов существует путь, в котором встречается ровно по одной вершине каждого цвета. Если максимальный несамопересекающийся путь в графе проходит через Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} вершин, то граф можно правильно раскрасить в Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} цветов. Если максимальный нечетный несамопересекающийся цикл в графе проходит через Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d - 1} вершину, то граф можно правильно раскрасить в Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} цветов. Ориентированный граф, из каждой вершины выходит не более Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} ребер, можно правильно раскрасить в Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2d + 1} цвет. Вершины произвольного графа Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} можно перенумеровать так, чтобы жадный алгоритм его раскраски использовал ровно Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \chi(G) } цветов. Для каждого натурального Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} постройте двудольный граф Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G } , раскраска которого, построенная жадным алгоритмом, имеет не менее Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} цветов.
6.	Паросочетания в графе	Какое минимальное количество рёбер можно удалить из графа Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_{n,n} } , чтобы не осталось ни одного совершенного паросочетания? В каждой клетке доски Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n \times n} написано неотрицательное вещественное число таким образом, что суммы в каждой горизонтали и вертикали равны Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1} . Докажите, что можно расставить Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} небьющих друг друга ладей, под которыми стоят ненулевые числа (Старинная задача) Есть Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} юношей и Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} девушек. Каждый юноша знает в точности Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} девушек и каждая девушка знает в точности Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} юношей. Докажите, что можно провести Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} танцев, в каждом танце юноша танцует со знакомой девушкой, все молодые люди разбиваются на пары, и никакая пара не повторяется (то за вечер юноша потанцует со всеми своими знакомыми).
7.	Гамильтоновы циклы и пути	Приведите пример гамильтонова не эйлерова графа; эйлерова не гамильтонова графа. Связный граф Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G} с Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \|V\| \geq 3} вершинами и Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2 + \frac{1}{2}(\|V\|-1)(\|V\|-2)} является гамильтоновым. Существует ли негамильтонов граф с Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 + \frac{1}{2}(\|V\|-1)(\|V\|-2)} рёбрами?
8.	Введение в экстремальную комбинаторику	Если граф не содержит треугольников, то Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e\le n^2/4. } Если Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e=[n^2/4]+1 } , то в графе есть по крайней мере Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle [n/2]} треугольников. Если Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=km} и граф не содержит полного подграфа с Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k+1} вершинами, то Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2e\le k(k-1)m^2} . (Переходя к дополнительному графу, получаем, что если Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n=km} и среди любых Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k+1} вершин некоторые две соединены ребром, то Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2e\ge km(m-1)} .) Eсли среди любых Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k+1} вершин некоторые две соединены ребром, Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m:=[n/k]} и Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle r:=k\{n/k\} } , то Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 2e\ge km(m-1)+2mr} . Если граф двудолен и не содержит цикла длины 4, то Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e\le n^{3/2}/2} . В любом графе есть двудольный подграф, содержащий не менее половины ребер графа. Если граф не содержит цикла длины 4, то Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e\le n^{3/2}} . Если граф не содержит подграфа Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_{2,3} } , то Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e\le 2n^{3/2}} . Если граф не содержит подграфа Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_{3,3} } , то Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e\le 2n^{5/3}} . Для любых целых Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle s,t } , \ Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 0<s\le t } , если граф с не содержит подграфа Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_{s,t} } , то Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e\le (s+t)v^{2-1/s}} . Если ни один граф из последовательности графов Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G_v} с Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v} вершинами и Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e_v} ребрами не содержит подграфа Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle K_{s,t} } , то Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle e_v=O(v^{2-1/s})} при Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v\to\infty} . Для любых Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} точек на плоскости существует не более Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} диаметров, т.е. (неупорядоченных) пар точек, расстояние между которыми равно диаметру множества этих точек. Пусть дано множество Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} из Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} точек на плоскости диаметра Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} . Графом диаметров Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle G=(V,E)} на этом множестве точек называется граф, у которого ребрами соединены точки, отстоящие друг от друга на расстояние Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle d} . Докажите, что для любого Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} мощности Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} верно, что Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \|E\|\le n.} Приведите пример графа, для которого эта оценка достигается. Для любых Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} точек Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A_1,\dots,A_n} в Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \R^d} обозначим через Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle D(A_1,\dots,A_n) } , число (неупорядоченных) пар точек, расстояние между которыми равно 1. Обозначим Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_n(d)=\max\{D(A_1,\dots,A_n) \ :\ A_1,\dots,A_n\in\R^d\}.} Обозначим через Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_n } максимальное, по всем наборам из Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} точек в Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \R^d } , число (неупорядоченных) пар точек набора, расстояние между которыми равно 1. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_n(2)>n[\log_2n]/4} . Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_n(2)\le 2n^{3/2}} . Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle E_n(3)\le 2n^{5/3}} . Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \dfrac {(n-1)^2}4\le E_n(4)\le \dfrac{2(n+4)^2}5. } Пусть Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} --- Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 11^k} -элементное подмножество пространства Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \R^k } , любое Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 10^k} -эле\-мент\-ное подмножество которого содержит две точки Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x,y} на расстоянии 1: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \|x-y\|=1} . Докажите, что для достаточно большого Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle k} количество единичных расстояний между точками множества Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle V} больше, чем Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 12^k/2} : Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \frac12\left\|\{(x,y)\in V\times V\colon\, \|x-y\|=1\}\right\|>\frac{12^k}2. } где через Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \#A} обозначено число элементов в множестве Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A} . То же больше, чем Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 12.1^k} .

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

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

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

style="text-align:center;" | 1 || Базовые понятия теории графов || 1)Граф, ориентированный граф, мультиграф. 2) Вершина, ребро, степень вершины. Полный граф. Лемма о рукопожатиях. 3) Маршруты, пути, циклы, простые пути, простые циклы. 4) Связность, компонента связности. Изоморфизм графов, подграфы, индуцированные подграфы style="text-align:center;" | 2 || Деревья || 5) Дерево, висячая вершина, остов. 6) Эквивалентные определения деревьев 7)Существование висячей вершины в связном ацикличном графе. 8) Код Прюфера. Теорема Кэли style="text-align:center;" | 3 || Эйлеровы пути и циклы в графах. || 9) Эйлеров цикл, путь и эйлеров граф. 10) Последовательность де Брёйна и граф де Брёйна. Правило <<0 лучше 1>> style="text-align:center;" | 4 || Планарные и плоские графы || 11) Планарные и плоские графы. Грань плоского графа. Формула Эйлера . 12) Пример непланарного графа 13) Классификация правильных многогранников 14) Раскраска карт, хроматическое число планарного графа. style="text-align:center;" | 5 || Хроматическое число графа || 15) Соотношения между хроматическим числом, числом независимости и кликовым числом. 16) Связь между хроматическим числом и максимальной степенью вершины 17) Хроматическое число пространства. Доказательство конечности. Известные нижние и верхние оценки (б/д). Связь с хроматическим числом дистанционного графа. style="text-align:center;" | 6 || Паросочетания в графе || 18) Максимальное и совершенное паросочетания. Теорема Холла о совершенном паросочетании в двудольном графе 19) Теорема Кёнига о максимальном паросочетании и минимальном вершинном покрытии в двудольном графе style="text-align:center;" | 7 || Гамильтоновы циклы и пути || 20) Гамильтонов путь и цикл, гамильтонов граф. 21) Достаточное условие Дирака и Оре гамильтоновости графа. 22)Вершинная связность и число независимости графа. Признак Эрдёша-Хватала. 23)Гамильтоновость графа 1-пересечений 3-элементных подмножеств n-элементного множества при всех всех достаточно больших n. style="text-align:center;" | 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 с.

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

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

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

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

BSc: DiscreteMath

Contents