Комбинаторный анализ Задачи. Комбинаторный анализ. Биография И. Б. Листинга Вклад индийцев в математику вначале столетий Задачи по теории множеств Часть a Часть b Задачи по комбинаторике Часть a Часть b Часть c Часть d Задачи по теории графов Часть a Часть b Часть c Часть d Часть e Список литературы
 Скачать 1.13 Mb.
|
|
Федеральное государственное бюджетное образовательное учреждение высшего образования Московский авиационный институт (национальный исследовательский университет Факультет №1 Авиационная техника Кафедра б Внешнее проектирование и эффективность авиационных комплексов Преобразование произвольного графа к виду графа Кенинга Вариант 15 Выполнил Коркин Г. Е. Группа МС Проверила Малинина Н.Л Москва 2020 1 Оглавление Биография И. Б. Листинга. ..................................................................................... Вклад индийцев в математику вначале столетий. ....................................... Задачи по теории множеств. .................................................................................... Часть a. .................................................................................................................. Часть b. .................................................................................................................. Задачи по комбинаторике. ....................................................................................... Часть a. .................................................................................................................. Часть b. .................................................................................................................. Часть c. .................................................................................................................. Часть d. .................................................................................................................. Задачи по теории графов. ........................................................................................ Часть a. .................................................................................................................. Часть b. .................................................................................................................. Часть c. .................................................................................................................. Часть d ................................................................................................................. Часть e. ................................................................................................................ Список литературы ................................................................................................ 23 2 Биография И. Б. Листинга. Иоганн Бенедикт Листинг родился 25 июля 1808 года в Геттингене. С ранних лет он был умным мальчиком, и благодаря своим талантам он получил помощь в получении образования от нескольких меценатов, включая фонд Штеделя, сторонников искусства и музеев. Он получил хорошую основу для своего образования в образцовой школе, которую ребенок посещал с восьми лет. В этой школе он впервые заинтересовался наукой, а именно математикой, главным образом благодаря своему талантливому учителю Мюллеру, также у него был настоящий талант к искусству. Листинг порадовал своих родителей, помогая семье финансово, зарабатывая деньги рисованием и каллиграфией с тринадцатилетнего возраста. В 1825 году Листинг поступил в гимназию, где проучился пять лет. Он освоил английский, французский, итальянский и латинский языки, а также расширил свои знания по математике и естествознанию. Уже в гимназии он решил продолжить академическую карьеру, и его таланты были отмечены присуждением стипендии фондом Штеделя. Будучи художественным фондом, они не могли поддержать Листинга в получении степени по математике, которая была бы его предпочтительным вариантом, но вместо этого ему была предоставлена стипендия для изучения архитектуры(основное направление) и математики(сопутствующий предмет к другим изучаемым наукам. Хотя было время, когда архитектура рассматривалась как раздел математики, она, конечно, не считалась таковой. Во времена Листинга архитектура уже не рассматривалась как раздел математики, поэтому такая комбинация была довольно своеобразной и продиктованной компромиссом между пожеланиями Листинга и сферой деятельности фонда Штеделя. В 1830 году Листинг поступил в Геттингенский университет и посещал спектр курсов, гораздо более широкий, чем математика и архитектура, определенные его стипендией. В дополнение к этим двум темам он также прошел курсы по астрономии, анатомии, физиологии, ботанике, минералогии, геологии и химии. Вскоре Листинг посещал курсы по математике, которые проводил Карл 3 Гаусс, ион был быстро замечен преподавателем как очень способный и трудолюбивый студент. Гаусс пригласил Бенедикта присоединиться к его кругу друзей, сформированного из лучших студентов и выдающихся умов того времени. Влияние Гаусса на Листинга было очень заметным. Именно с подачи преподавателя он начал изучать топологические концепции. Бенедикт также был талантливым экспериментатором и сотрудничал с Гауссом в физических экспериментах, особенно, связанных с земным магнетизмом. Гаусс стал научным руководителем диссертации Листинга Поверхности второго порядка. Он получил докторскую степень в июне 1834 года. Друг Листинга по университету, Вальтерхаузен отправлялся на Сицилию для изучения вулканов. Он также согласился собрать данные о земном магнетизме для Гаусса в этой поездке. Это было путешествие, в котором Листинг поддерживал свои интересы во многих различных темах, а также в геологии и физике, которые были целью поездки. В свободное время он работал над математикой, в частности, работая над топологическими идеями, впервые предложенными Гауссом. Он решил обобщить свои мысли по этой теме и сделал это в длинном письме своему старому школьному учителю Мюллеру. Именно в этом письме слово топология появляется впервые. Он не любил термина затем использовал его для топологических идей и Поскольку вся доктрина была довольно новой, он счел оправданным дать ей новое имя и поэтому назвал ее топологией, которая была более уместна. Вовремя своих поездок к Листингу обратился Высшая профессиональная школа Ганновера с вопросом, будет ли он заинтересован в должности преподавателя прикладной математики. Не говоря да или нет, он вежливо поблагодарил их за предложение. Из-за эпидемии холеры Сарториус и Листинг задержали их возвращение в Геттинген. На самом деле они взяли корабль в Англию, где провели некоторое время, прежде чем вернуться в Германию. Листинг отправился в Ганновер для собеседования на должность преподавателя в школу торговли и начал свою педагогическую карьеру в ноябре 1837 года. 4 Позже как профессор физики Листинг мог выбрать свою область для исследований. Будучи универсальным ученым, он выбрал еще одну область из тех, в которых он уже работали начал изучать оптику человеческого глаза. В 1845 году он опубликовал Вклад в физиологическую оптику, ставшую классикой. Помимо того, что он содержал данные тщательной экспериментальной работы, книга была прекрасно иллюстрирована Листингом, в котором использовались все его навыки рисования и каллиграфии. В сентябре 1846 года Листинг женился на Полине Элверс. Листинг продолжал думать о топологических идеях и написал книгу Предварительные исследования по топологии в 1847 году. Это было первое опубликованное использование слова топология. В течение многих лет оно был известен как «analysis situs», и только в конце х годов английское слово топология впервые использовалось другим ученым – Лефшецем. В этой книге в качестве предварительной работы Листинг пишет Под топологией мы понимаем учение о модальных особенностях объектов или законах связи, относительного положения и последовательностей точек, линий, поверхностей, тел и их частей или совокупностей в пространстве, всегда безотносительно к измерению или количеству ". В 1848 Листинг был повышен до обычного профессора математической физики, а Вебер стал профессором экспериментальной физики. Хотя в исследовании, проведенном Листингом, мало что изменилось, поскольку он всегда шел в том направлении, которое его интересовало, ему все же пришлось отдать большую часть своей лаборатории Веберу. В 1858 году Листинг открыл свойства ленты Мебиуса почти одновременно и независимо от самого Мебиуса. В 1862 году он опубликовал трактат Описание пространственных комплексов или обобщение теоремы Эйлера о многогранниках, в котором обсуждаются расширения формулы Эйлера для эйлеровой характеристики ориентированных трехмерных многогранников на случай некоторых четырехмерных симплициальных комплексов. 5 Объем вклада в науку, внесенный Листингом, весьма примечателен. Брайтенбергер пишет «... он изучал фигуру земли в мельчайших деталях он проводил наблюдения в области метеорологии, земного магнетизма и спектроскопии он писало количественном определении сахара в моче диабетиков он поддерживал зарождающуюся оптическую промышленность в Германии и уличное освещение в Геттингене, он путешествовал на всемирные выставки в Лондоне 1851 года, Вене 1873 года и Лондоне 1876 года в качестве наблюдателя от своего правительства он помогал в геодезических изысканиях он изобрел множество терминов кроме топологии, некоторые из которых стали актуальными "энтропийное явление, "узловые точки, "гомоцентрический свет, "телескопическая система, "геоид, он придумал один микрон за миллионную метра. Среди почестей, которые получил Листинг, были выборы в Геттингенскую академию и Королевское общество Эдинбурга. Он был удостоен звания почетного доктора Тюбингена. Умер от инсульта 24 декабря 1882 года в Геттингене. 6 Вклад индийцев в математику вначале столетий. Квадратные уравнения были созданы Шридхарачарией в 11 веке. Шрипати Мишра (1019-1066) написал неполный арифметический трактат в 125 стихах, основанный на работе Шридхары. Он работал главным образом над перестановками и комбинациями, общими решение одновременного неопределенного линейного уравнения. Чакравати (около 1100 г) является автором математического трактата под названием Gome-mat Saar. Бхаскара II (1114-1185) был математиком-астрономом, который написал ряд важных трактатов. Ряд его вкладов был впоследствии направленна Ближний Восток ив Европу. Его вклад включает в себя расчет процентов, арифметические и геометрические прогрессии, планиметрия, стереометрия, тень гномона, решения комбинаций, дал доказательство для деления на ноль, являющегося бесконечностью, распознавание положительного числа, имеющего два квадратных корня, сурды, операции с продуктами нескольких неизвестных, решения квадратных и кубических уравнений, квадратичные уравнения с более чем одним неизвестным, общая форма уравнения Пелла с использованием метода чакравалы, неопределенные кубические уравнения, неопределенные квартильные уравнения, неопределенные полиномиальные уравнения более высокого порядка, дал доказательство теоремы Пифагора, задумано о дифференциальном исчислении, открыл производную, обнаружен дифференциальный коэффициент, сформулирована теорема Ролля, частный случай теоремы о среднем значении (одна из важнейших теорем исчисления и анализа, выведен дифференциал функции синуса, вычисляется π, правильно до пяти десятичных знаков, рассчитали длину вращения Земли вокруг Солнца до 9 десятичных знаков. Древние и средневековые индийские математические труды, все состоящие в санскрите, как правило, состояли из раздела сутр, в котором набор правил или проблем, был сформулированы в стихах, чтобы помочь запоминанию студента. 7 Задачи по теории множеств. Часть a. 𝐴 = {1, 2, 6}; 𝐵 = {𝑐, 𝑑} 𝐴 × 𝐵 = {{1, 𝑐}, {2, 𝑐}, {6, 𝑐}, {1, 𝑑}, {2, 𝑑}, {6, 𝑑}} 𝐵 × 𝐵 = {{𝑐, 𝑑}, {𝑑, 𝑐}} 𝐴 × ∅ = {∅} 𝐴 × 𝐴 = {{1,1}, {2,1}, {6,1}, {1,2}, {2,2}, {6,2}, {1,6}, {2,6}, {6,6}} 𝐵 × 𝐴 = {{1, 𝑐}, {2, 𝑐}, {6, 𝑐}, {1, 𝑑}, {2, 𝑑}, {6, 𝑑}} Часть b. 𝐴 = {2, 3,5,7,9}; 𝐵 = {10,5,2,6} 𝐴 ∪ 𝐵 = {2, 3, 5, 6,7,9,10} 𝐴 ∩ 𝐵 = {2, 5} 𝐴 \ 𝐵 = {3,7,9} 𝐴̅ = {6,10} 𝐵̅ = {3,7,9} 8 Задачи по комбинаторике. Часть a. Всего 15 команд 15 × 14 × 13 = 2730 Ответ 2730. Часть b. Двузначные числа, не содержащие цифры 1,3 и 5: 6 × 7 = 42 Ответ 42. Часть c. 𝐶 7 3 = 𝑛! (𝑛 − 𝑚)! × 𝑚! = 7! 4! × 3! = 7 × 6 × 5 × 4! 4! × 3! = 7 × 6 × 5 3! = 210 6 = 35 Ответ 35. Часть d. Двузначные числа, не содержащие цифры 1,3 и 6: 6 × 7 = 42 Ответ 42. 9 Задачи по теории графов. Часть a. Рис. 1 Рис. 2 Часть b. Граф содержит 11 вершин, поэтому перебираем различные варианты заполнения 55 ячеек таблицы смежности. Данный перебор будет содержать всевозможные варианты, в том числе и с изолированными вершинами. Часть c. Рис. 3 Рис. 4 10 В данном графе слишком много возможных путей, поэтому ниже представлены некоторые возможные варианты Замкнутых контуров в этом графе нет. Часть d Подграф графа – это граф, образованный из подмножества вершин графа вместе со всеми рёбрами, соединяющими пары вершин из этого подмножества Выделим в исходном графе два подграфа: Рис. 7 Рис. 8 Рис. 5 Рис. 6 11 Далее выделим два частичных графа Рис. 9 Рис. 10 12 Часть e. Сделаем нормализацию. Находим суммы по строками столбцам матрицы и записываем рядом. Рис. 11 Далее рассчитываем матрицу S последующей формуле и выписываем рядом минимальный элемент в каждом столбце и строке s 𝑖𝑗 = l 𝑖𝑗 ∙ (∑ l 𝑖𝑗 𝑘 𝑖=1 + ∑ l 𝑖𝑗 𝑘 𝑗=1 ) Рис. 12 13 Затем рассчитываем матрицу C: C 𝑖𝑗 = l 𝑖𝑗 ∗ (D 1 + D 2 ) Где D 1 и D 2 превышение элемента над минимальным элементом в строке и столбце соответственно. Рис. 13 Исходя из матрицы C проводим нормализацию, разделяя дуги, в которых значение неравно нулю и получаем Рис. 14 14 Дописываем в матрицу L новые вершины и ребра и считаем матрицы S и C. Рис. 15 Рис. 16 15 Рис. 17 Проводим нормализацию. Рис. 28 Добавляем в матрицу L еще строку и снова пересчитываем остальные матрицы. 16 Рис. 18 Рис. 19 17 Рис. 20 На данном этапе нормализация графа завершена. Теперь его необходимо упорядочить. Матрица должна иметь один пустой столбец и одну пустую строку. Номер столбца вписывается в строку и столбец бег. Q i столбец вершин графа. Определение номеров конечных событий фин для каждой работы (дуги) выполняется путем проецирования строки 𝑁 𝑏𝑒𝑔 на элементы R ij = 1 матрицы R k и далее путем проецирования полученного элемента (бег) ij на столбец фин. 18 Рис. 213 Вычеркнутые на первом этапе элементы входят в подматрицу. Всем соответствующим столбцам присваивается очередной номер, в данном случае 2. Этот же номер присваивается соответствующим строкам. Пронумерована вершина 2. Рис. 22 Просматриваем следующую пронумерованную строку и исключаем из нее элементы, которые в ней содержатся. Переписываем заново матрицу. Делаем упорядочение вершины. Эти столбцы получат 3. Переходим к следующей строке и повторяем действия 19 Рис. 23 Снова переписываем матрицу с новым порядком рядов. Рис. 24 20 Рис. 25 Рис. 26 21 Рис. 47 Рис. 58 В конце заполняем боковые таблицы по описанному выше правилу. Таким образом мы получаем упорядоченный матрицу упорядоченного графа. 22 Поданной таблице можно построить упорядоченный граф. Рис. 69 23 Список литературы 1. Методические указания в электронном виде. 2. К. Берж Теория графов и ее применение, Москва, Иностранная литература, 1962 3. О. Оре Теория графов, Москва, Наука, 1968 4. А. А. Зыков Основы теории графов, Москва, Наука, 1987 5. Ф. Харари, Э. Палмер Перечисление графов, Москва, Мир, 1976 |