Максимальный балл огэ по английскому языку. Критерии оценивания заданий устной части огэ по иностранным языкам. Правильно выбранное обращение
Среди жителей Кёнигсберга была распространена такая практическая головоломка: можно ли пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды? В 1736 году выдающийся математик Леонард Эйлер заинтересовался задачей и в письме другу привел строгое доказательство того, что сделать это невозможно. В том же году он доказал замечательную формулу, которая связывает число вершин, граней и ребер многогранника в трехмерном пространстве. Формула таинственным образом верна и для графов, которые называются "планарными". Эти два результата заложили основу теории графов и неплохо иллюстрируют направление ее развития по сей день.
О курсе
Этот курс служит введением в современную теорию графов. Граф как математический объект оказывается полезным во многих теоретических и практических задачах. Дело, пожалуй, в том, что сложность его структуры хорошо отвечает возможностям нашего мозга: это структура наглядная и понятно устроенная, но, с другой стороны, достаточно богатая, чтобы улавливать многие нетривиальные явления. Если говорить о приложениях, то, конечно, сразу же на ум приходят большие сети: Интернет, карта дорог, покрытие мобильной связи и т.п. В основах поисковых машин, таких, как Yandex и Google, лежат алгоритмы на графах. Помимо computer science, графы активно используются в биоинформатике, химии, социологии. В нашем курсе мы, конечно же, обсудим классические задачи, но и поговорим про более недавние результаты и тенденции, например, про экстремальную теорию графов.
Формат
Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
Информационные ресурсы
- В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. Лекции по теории графов. М.: Книжный дом «Либроком», 2009.
- А. А. Зыков. Теория конечных графов. Новосибирск: Наука, 1969.
- М. Свами, К. Тхуласираман. Графы, сети и алгоритмы. М.: Мир, 1984.
- M. Aigner, G. M. Ziegler. Proofs From THE BOOK. Fourth Edition. Springer, 2009.
- B. Bollobás. Modern Graph Theory. Springer, 1998.
- J. A. Bondy, U. S. R. Murty. Graph Theory. Springer, 2008.
Требования
Материал изложен с самых основ и на доступном языке. Целью этого курса является не только познакомить вас с вопросами и методами теории графов, но и развить у неподготовленных слушателей культуру математического мышления. Поэтому курс доступен широкому кругу слушателей. Для освоения материала будет достаточно знания математики на хорошем школьном уровне и базовых знаний комбинаторики.
Программа курса
- Понятие графа и виды графов.
- Различные применения графов: от Кенигсберских мостов до Интернета.
- Связность графа, подграфы и степень вершины.
- Эквивалентные определения деревьев.
- Планарность и критерий Куратовского
- Формула Эйлера.
- Хроматическое число планарного графа.
- Перечисление деревьев: код Прюфера и формула Кэли.
- Формула для числа унициклических графов.
- Эйлеровы циклы и критерий эйлеровости.
- Гамильтоновы циклы. Критерий Дирака и критерий Хватала.
- Паросочетания. Теорема Холла и Кенига.
- Экстремальная теория графов. Теорема Турана.
- Аналог теоремы Турана для графов на плоскости.
- Теория Рамсея. Знакомства среди шести человек.
- Определение числа Рамсея.
- Нижняя и верхняя оценки чисел Рамсея.
Результаты обучения
По итогам успешного прохождения курса слушатель познакомится с понятием графа, с видами и различными характеристиками и свойствами графов. Слушатель узнает о задаче о правильных раскрасках и о возможности нарисовать данный граф на плоскости без пересечений ребер, а также научится разными способами определять деревья и перечислять их. Наконец, слушатель познакомится с понятиями эйлеровых и гамильтоновых циклов, паросочетаний и даже прикоснется к задачам экстремальной теории графов.
Теория графов – это раздел дискретной математики, изучающий объекты, представимые в виде отдельных элементов (вершин) и связей между ними (дуг, рёбер).
Теория графов берет начало с решения задачи о кенигсбергских мостах в 1736 году знаменитым математиком Леонардом Эйлером (1707-1783: родился в Швейцарии, жил и работал в России).
Задача о кенигсбергских мостах.
В прусском городке Кенигсберг на реке Прегал семь мостов. Можно ли найти маршрут прогулки, который проходит ровно 1 раз по каждому из мостов и начинается и заканчивается в одном месте?
Граф, в котором найдется маршрут, начинающийся и заканчивающийся в одной вершине, и проходящий по всем ребрам графа ровно один раз, называется Эйлеровым графом.
Последовательность вершин (может быть с повторением), через которые проходит искомый маршрут, как и сам маршрут, называется Эйлеровым циклом .
Задача о трех домах и трех колодцах.
Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались. Эта задача была решена (показано, что решения не существует) Куратовским (1896 – 1979) в 1930 году.
Задача о четырех красках. Разбиение плоскости на непересекающиеся области называется картой . Области карты называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом. С конца XIX века известна гипотеза, что для этого достаточно четырех красок. Гипотеза не доказана до сих пор.
Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера.
Проверить «вручную» полученное решение невозможно – объем перебора выходит за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки…
Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они все сделали правильно.
Определение 7.1. Графом G = G (V , E ) называется совокупность двух конечных множеств: V – называемого множеством вершин и множества E пар элементов из V, т.е. EÍV´V, называемого множеством рёбер , если пары неупорядочены, или множеством дуг , если пары упорядочены.
В первом случае граф G (V , E ) называется неориентированным , во втором – ориентированным.
ПРИМЕР. Граф с множеством вершин V = {а,b,с} и множеством ребер Е ={{а, b}, {b, с}}
ПРИМЕР. Граф, у которого V = {a,b,c,d,e} и Е = {{а, b}, {а, е}, {b, е}, {b, d}, {b, с}, {с, d}},
Если e=(v 1 ,v 2), еÎЕ, то говорят, что ребро е соединяет вершины v 1 и v 2 .
Две вершины v 1 ,v 2 называются смежными , если существует соединяющее их ребро. В этой ситуации каждая из вершин называется инцидентной соответствующему ребру.
Два различных ребра смежны , если они имеют общую вершину. В этой ситуации каждое из ребер называется инцидентным соответствующей вершине.
Число вершин графа G обозначим v , а число ребер - e :
.
Геометрическое представление графов следующее:
1) вершина графа – точка в пространстве (на плоскости);
2) ребро неориентированного графа – отрезок;
3) дуга ориентированного графа – направленный отрезок.
Определение 7.2. Если в ребре e=(v 1 ,v 2) имеет место v 1 =v 2 , то ребро е называется петлёй . Если в графе допускается наличие петель, то он называется графом с петлями или псевдографом .
Если в графе допускается наличие более одного ребра между двумя вершинами, то он называется мультиграфом .
Если каждая вершина графа и (или) ребра помечена, то такой граф называется помеченным (или нагруженным ). В качестве пометок обычно используются буквы или целые числа.
Определение 7.3. Граф G (V , E ) называется подграфом (или частью ) графа G (V ,E ), если V V , E E . Если V = V , то G называется остовным подграфом G .
Пример 7 . 1 . Дан неориентированный граф.
Определение 7.4. Граф называется полным , если любые две его вершины соединены ребром. Полный граф с n вершинами обозначается через K n .
Графы К 2 , К 3, К 4 и К 5 .
Определение 7.5. Граф G =G (V , E ) называется двудольным , если V можно представить как объединение непересекающихся множеств, скажем V =A B , так что каждое ребро имеет вид (v i , v j ), где v i A и v j B .
Каждое ребро связывает вершину из А с вершиной из В, но никакие две вершины из А или две вершины из В не являются связанными.
Двудольный граф называется полным двудольным графом K m , n , если A содержит m вершин, B содержит n вершин и для каждого v i A , v j B имеем (v i , v j )E .
Таким образом, для каждого v i A , и v j B имеется связывающее их ребро.
K 12 K 23 K 22 K 33
Пример 7 . 2 . Построить полный двудольный граф K 2,4 и полный граф K 4 .
Граф единичного n -мерного куба В n .
Вершины графа - n-мерные двоичные наборы. Рёбра соединяют вершины, отличающиеся одной координатой.
Пример: