Задания по теор. курсу «Теории Графов»
Философ Иммануил Кант, гуляя по городу Кенигсбергу (сейчас этот город называется Калининград), поставил задачу (1736), известную в математике как задача о семи кенигсбергских мостах: можно ли пройти по всем этим мостам и при этом вернуться в исходную точку так, чтобы по каждому мосту пройти только один раз.
Рис.1.1 Кенигсбергские мосты
Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно.
В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кёнигсберга это невозможно).
На рис.1.2 изображена схема семи мостов Кенигсберга (заметим, что сейчас осталось только два из них).
Рис.1.2 Иллюстрация к задаче о Кенигсбергских мостах
В ходе рассуждений Эйлер пришёл к следующим выводам:
На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города — точки соединения линий (вершины графа).
На рисунке 1.3 изображен мультиграф, соответствующий этой схеме (при построении графа считалось, что мостам соответствуют линии (дуги графа), а частям города — точки соединения линий (вершины графа)).
Рис.1.3 Решение задачи о Кенигсбергских мостах
Граф кёнигсбергских мостов имел четыре нечётные вершины (то есть все), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.
Артур Кэли (1821-1895), английский математик. Родился 16 августа 1821 в Ричмонде, но вырос в Петербурге, где его отец был купцом. Окончил Тринити-колледж Кембриджского университета, членом совета которого стал в 1842. Первые работы по математике Кэли опубликовал в 1841 в "Кембриджском журнале" ("Cambridge Journal"). В 1843 переменил род профессиональной деятельности: стал адвокатом в Лондоне и в течение следующих 20 лет совмещал адвокатскую практику с занятиями математикой. Именно в это время были созданы его основополагающие труды. В 1863 принял предложение занять кафедру чистой математики в Кембриджском университете, где преподавал почти 30 лет. Кэли принадлежит более 200 работ, посвященных самым разнообразным вопросам математики. Наиболее известны его девять Мемуаров о формах (Memoirs on Quantics, 1854-1878), в которых он развивает теорию алгебраических инвариантов. Кэли первым начал исследования геометрии n-мерного пространства и достиг значительных успехов в уяснении взаимоотношений между проективной и метрической геометриями. Он ввел принятое ныне обозначение для определителя, исследовал дифференциальные уравнения и эллиптические функции. Его именем названы теорема и кривая.
Умер Кэли в Кембридже 26 января 1895. Кэли — один из плодовитейших учёных XIX века, написавший более 700 работ. Большая часть его работ относится к линейной алгебре, дифференциальным уравнениям и эллиптическим функциям. В частности, он доказал теорему Гамильтона-Кэли о том, что каждая квадратная матрица является корнем своего характеристического многочлена. Он был первым, кто сформулировал определение группы в том виде, как она определяется сегодня — множество с бинарной операцией, удовлетворяющей определённым законам. Прежде же, когда математики говорили о группе, они подразумевали группу перестановок. В 1882 Лондонское королевское общество присудило ему Медаль Копли.
Исторически первым понятие графа – сети, как совокупности вершин и связей ввел в 1736 году Леонард Эйлер.
Проблема четырёх красок — математическая задача, предложенная Фрэнсисом Гутри (англ.) в 1852 году, сформулированная следующим образом:
| Выяснить, можно ли всякую расположенную на сфере карту раскрасить четырьмя красками так, чтобы любые две области, имеющие общий участок границы, были раскрашены в разные цвета. |
|
Стоит отметить две необходимые характеристики этой карты:
История доказательства
Кеннет Аппель и Вольфганг Хакен из Иллинойского университета доказали в 1976 году, что так можно раскрасить любую карту. Это была первая крупная математическая теорема, для доказательства которой был применён компьютер. Несмотря на последующие упрощения, доказательство практически невозможно проверить, не используя компьютер. Поэтому некоторые математики отнеслись к этому доказательству с недоверием, что объяснялось не только использованием компьютера, но и громоздкостью описания алгоритма первых доказательств (741 страница); впоследствии были предложены более компактные алгоритмы и скорректирован ряд ошибок.
Наиболее известные попытки доказательства:
· Альфред Кэмпе предложил доказательство в 1879 году, его опровергли в 1880 году, на основе его идей удалось доказать, что любую карту можно раскрасить в 5 цветов.
· Питер Тэт предложил другое доказательство в 1880 году, его опровергли в 1891 году.
· В своей книге В. А. Горбатов утверждает, что предложил классическое доказательство ещё в 1964 году (объёмом около 30 стр.). Однако опровержений, как и подтверждений, это доказательство пока не получило.
Густав Роберт Кирхгоф (нем. Gustav Robert Kirchhoff; 12 марта 1824, Кёнигсберг — 17 октября 1887, Берлин) — один из великих физиков XIX века. Родился 12 марта 1824 года в Кёнигсберге; с 1842 по 1846 г. изучал математику и физику в Кёнигсбергском университете, а в 1847 году уже выступил в качестве приват-доцента в Берлине; в 1850—1854 гг., в качестве экстраординарного профессора, читал лекции в Бреславле, затем до 1874 года исполнял должность ординарного профессора в Гейдельберге, откуда в 1875 году перешёл в Берлин; в 1875 году избран членом Берлинской академии наук, с 1862 года состоял членом-корреспондентом Санкт-Петербургской академии наук. Умер в Берлине 17 октября 1887 году.
Научный вклад
Кирхгоф, будучи прекрасным знатоком математики, обладал в то же время редким умением плодотворно прилагать эти знания к труднейшим вопросам математической физики, в области которой преимущественно работал. Уже первые его работы о распространении электричества по пластинкам (1845—1847) послужили исходным пунктом для множества работ других учёных. Целый ряд последующих работ по электричеству был посвящён вопросам о распределении электричества на проводниках, о разряде конденсаторов, о течении электричества по подводным кабелям и т. д.; особенно важна работа об индукции токов (1849), содержащая описание способа определения электрического сопротивления проводников в абсолютной мере, и два больших мемуара об индуктированном магнетизме (1853 и 1876). Одновременно Кирхгоф обнародовал ряд замечательных работ по механике, относящихся главным образом к теории деформации, равновесия и движения упругих тел.
Свои взгляды на основные принципы механики Кирхгоф изложил в весьма известных лекциях по механике, содержащих и решение множества трудных вопросов теорий упругости и течения жидкости; в этом сочинении Кирхгоф старался отрешиться от необходимости введения в основу механики понятий о массе и силе в причинной связи с движением. Наибольшей известностью пользуются работы Кирхгофа над радиацией (излучением); ряд опытных (совместно со знаменитым химиком Бунзеном) и теоретических работ над этим вопросом (1858—1860) привели к блестящему открытию обращения линий спектра, к объяснению Фраунгоферовых линий и к созданию целого метода, чрезвычайно важного по своим приложениям в физике, химии и астрономии, — спектрального анализа. Затем следовал целый ряд работ по термодинамике паров и растворов и по оптике. Последние исследования Кирхгофа касались изменений формы тел под влиянием магнитных и электрических сил (1884—1885).
Работы Кирхгофа напечатаны главным образом в «Poggendorfs Annalen der Physik», в «Crelles Journal für Mathematik» и последние в отчетах берлинской академии; большинство из них собрано в его «Gesammelte Abhandlungen» (Лейпциг, 1882). Кроме этого, им издано несколько томов его «Vorlesungen über Mathematische Physik» (Лейпциг, 1876 и сл.) и знаменитое исследование над спектрами: «Untersuchungen über das Sonnenspectrum und die Spectren der chemischen Elemente» (Берлин, 1861; 3 изд., 1876), переведённое и на английский язык.
Гамильтонов граф — в теории графов это граф, содержащий гамильтонову цепь или гамильтонов цикл.
Гамильтонов путь (или гамильтонова цепь) — путь (цепь), содержащий каждую вершину графа ровно один раз. Гамильтонов путь, начальная и конечная вершины которого совпадают, называется гамильтоновым циклом. Гамильтонов цикл является простым остовным циклом. Задача определения содержит ли данный граф гамильтонов цикл является NP-полной. Гамильтоновы путь, цикл и граф названы в честь ирландского математика У. Гамильтона, который впервые определил эти классы, исследовав задачу «кругосветного путешествия» по додекаэдру, узловые вершины которого символизировали крупнейшие города Земли, а рёбра — соединяющие их дороги.
Рис. 1.4 Додекаэдр Гамильтона
Додека́эдр — двенадцатигранник, составленный из двенадцати правильных пятиугольников. Каждая вершина додекаэдра является вершиной трёх правильных пятиугольников.
Таким образом, додекаэдр имеет 12 граней (пятиугольных), 30 рёбер и 20 вершин (в каждой сходятся 3 ребра). Сумма плоских углов при каждой из 20 вершин равна 324°.
В основном, матрица инциндентности, как способ задания графа, применяется для доказательства теорем.
Depth-First Search (DFS) – поиск в глубину.
Best-First Search (BFS) – поиск в ширину («лучший первый поиск»).
Дата добавления: 2015-10-21; просмотров: 24 | Нарушение авторских прав
| <== предыдущая лекция | | | следующая лекция ==> |
| -10ед. выносливости за 1сек. -0.5ед. самочувствия за 15сек. | | |
