Войти в мой кабинет
Регистрация
ГОТОВЫЕ РАБОТЫ / ДИПЛОМНАЯ РАБОТА, ВЫСШАЯ МАТЕМАТИКА

Теоретико-методологические аспекты исследования математических графов.

irina_krut2019 1100 руб. КУПИТЬ ЭТУ РАБОТУ
Страниц: 44 Заказ написания работы может стоить дешевле
Оригинальность: неизвестно После покупки вы можете повысить уникальность этой работы до 80-100% с помощью сервиса
Размещено: 15.01.2020
Актуальность исследования: Интерес к проблемам исследования на практике концепции графов возник приблизительно в середине минувшего века в Великобритании, а понятие «связного графа» считается естественным обобщением понятия связного графа, данный факт обретает своё подтверждение в классической теореме Менгера, с которой в 1927году фактически и начались исследования по проблеме теории связности графов, их свойств, типы, компонент связности. В последующем, немного позже, исследования продолжились иными учёными, такими как: Уитни, Татт, Форд и Фалкерсон, Дирак, Халин, Мадер и другие. В 60-80 годы XX столетия прослеживается в истории всплеск заинтересованности к проблеме связности графов среди математиков того времени. Графы и сопутствующие с ним формы исследований пронизываются теперь на всесторонних уровнях науки современной математики и информатики 21 века. Математические графы в сегодняшнее время являются весьма продуктивно развивающимся разделом дискретной математики, данный аспект обуславливается тем, что в виде графовых моделей описываются различные объекты и ситуации, необходимые для нормальной жизнедеятельности общественной жизни. Что же касается в нашу эпоху, то в современное время хоть и продолжают постепенно появляться новые работы по этой тематике в небольшом количестве, но этого не так много, как это отмечалось раньше. К сожалению, нельзя не сказать, что в отечественной литературе и периодических изданиях по данной тематике уделяется незначительное внимание, вследствие этого встаёт проблема изучения и всестороннего детального анализа такой темы как связность графов. Изучение связности графов является одной из традиционных направлений в исследованиях теории графов, непосредственно исследование и всесторонний анализ по теме концепции связности графов способны раскрыть нам новые инварианты графов, которые в перспективе станут полезны и в иных областях математики и информатике. В виду этого неоспоримого факта встаёт вполне реальный вопрос о необходимости продолжать исследования в области концепции теории графов, а так же исследования основ и анализа связности графов, их типов. Наука не стоит на месте, новые технологии и открытия в той или иной области требуют и ждут прогрессивных начал и как следствие становится необходимым детальное изучение ещё не разработанных целых систем выстраивания новых структурных инвариантов графов, и раскрывать построенные ранее. Цель исследования: всесторонний анализ исследования основ связности графов в области дискретной математики. Объект исследования: Связность графов Предмет исследования: Элемент и свойства связности графов в области дискретной математики Гипотеза исследования: На наш взгляд детальное и всестороннее изучение процесса связности графов, и их использование облегчит процесс решения многих всевозможных логических и комбинаторных задач, сделает их процесс менее трудоёмким, облегчит их выстраивание, а детальное и углубленное изучение основ связности графов позволит развить мышление даже у самого младшего школьника. Процесс выстраивания творческого подхода к решению многих задач, с помощью теории графов способно облегчить пользование различными языковыми средствами в области математической науки в целом. Задачи исследования: -исследовать теоретико-методологические аспекты теории применения графов в области дискретной математике; -рассмотреть исторический контекст эволюции становления теории определения и сущности «графа»; -охарактеризовать основные понятия теории графов, проиллюстрировать их на примерах и прикладных задачах; -рассмотреть на примерах и задачах концепцию связности графов; -изучить типы и свойства графов в области дискретной математике; -проанализировать и раскрыть понятие о «связности графа»; - раскрыть и осветить свойства связанности графов; -разобрать алгоритмы выделения компонент связности, привести примеры. Теоретико-методологической основой исследования являются: исследования о роли современной дискретной математики в математизации наук и о методологии математического познания Болтянского В. Г., Виленкина Н.Я, Столяра А. А, Л. Калужнина А. Н. Я. Винера, В. М. Глушкова,Л. Д. Кудрявцева, Я. Г. Неуймина, Б. В. Гнеденко, А. Н. Колмогорова. Методы исследования: в процессе написания работы использовались ряд методов таких как: методы теоретического анализа математической литературы, анализ и изучение состояния исследуемой проблемы в теоретических основах информатики и дискретной математике, при исследовании и написании данной работы использовался аппарат системного анализа, теоретических основ информатики, дискретной математики, теории оптимизации. Практическая значимость исследования: практическая составляющая предложенной работы определяется тем, что результаты исследования вполне могут быть использованы в качестве методического материала на уроках информатики, математики, геометрии, и иных смежных математических науках. Научная новизна исследования: Данное курсовое исследование имеет хорошо выраженную практическую направленность, в предложенной работе предпринята попытка автором проиллюстрировать на примерах и прикладных задачах теорию применения связности графов. На практике разобраны процесс алгоритма выделения компонент связности графов. Теоретическая значимость исследования: работа носит теоретико-методологический характер, её итоги вполне могут быть использованы для дальнейшего изучения теории и практики применения связности графов в области дискретной математике. Структура курсовой работы. Курсовая работа имеет традиционный порядок, состоит из введения, трёх глав, заключения, библиографического списка, включающего 15 наименований. Во введении обоснована актуальность исследования, представлены данные анализа научно-теоретических предпосылок по теме курсовой работы, определены цель, объект, предмет, сформулированы задачи, гипотеза, методология и методы исследования, показаны новизна, охарактеризована практическая значимость работы. В главах курсовой работы исследованы теоретико-методологические и исторические аспекты, посвящённые процесса связности графов в области дискретной математике, приведены свойства, типы, исследованы теоремы, доказательства с применением примеров, таблиц, рисунков и исторической справки. Изучены основные понятия теории и виды графов, проиллюстрированы на примерах и прикладных задачах. В заключении работы подведены общие итоги курсовой работы, изложены основные выводы, определены проблемы, требующие дальнейшего детального изучения.
Введение

Понятие «математический граф» весьма ёмко и сопряжено со многими основными понятиями, в частности, уже начиная начала с курса школьной математики. В процессе изучения окружающей нас действительности мы зачастую сталкиваемся с так называемыми абстракциями — объектами, весьма сложными для изучения, что охватить всю их специфику проявления мы заранее не можем. В этой связи на помощь приходят модели — математические, физические, химические, созданные на их основании компьютерные и иных. Одной из важнейших математических моделей и является «граф» как таковой. Понятие «граф» в математической науке означает иллюстрацию, где изображено несколько точек, некие из них объединены линиями, отрезками, вершинами. Графы как абстрактно-математический объект, встречается с нами во всех отраслях жизнедеятельности, мы сами того не замечаем, как порой сталкиваемся с ними в повседневной жизни, вот взять, к примеру, метрополитен Москвы, с помощью теории графов изображена схема самого метрополитена. Основы теории графов необходимы в различных областях, сопряжённых с производством управления, бизнесом, с помощью графов изображаются так же схемы дорог, газопроводов, тепло- и электросети. В современное быстротечное время мы уже не представляем себе нормальной жизни без знания фундаментальных основ информатики. Отсутствие базовых начал информатики усложняет процесс изучения многих технических областей. Информатикой пронизаны многие области наук. Графами являются блок – схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а рёбра, связывающие эти вершины, - означают работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения в перспективе. Графы изучает раздел дискретной математики. Дискретная математика - это раздел математики, который раздел занимается исследованием свойств объектов конечного характера, к их числу относят, к примеру, конечные группы, конечные графы, некие математические модели преобразователей информации. Термин «дискретный» берёт свои начала от латинского «discretus», что в переводе означает «разделённость», «прерывистость» и противопоставляется непрерывности. Необходимо отметить, что дискретная математика на сегодняшний день является интенсивно развивающейся частью математики, состоит из множества разделов: теория множеств, комбинаторика, теория графов, концепция возможностей. Наряду с перечисленными разделами дискретной математики именно раздел теории графов отличается своей наглядностью, её модификации просты для восприятия и зачастую допускают интересную игровую интерпретацию.
Содержание

Введение………………………………………………………………………………..3 1.Глава Теоретико-методологические аспекты исследования математических графов 1.1 Основные понятия теории графов……………………………………...……….8 1.2 Типы графов и область их применения………………………………………...18 2. Глава Различные понятия о связности 2.1 Связность графов………………………………………………………………….24 2.2 Маршруты и цепи…………………………………………………………...……28 3.Глава Алгоритмы выделения компонент связности……………………………..33 3.1 Алгоритм поиска минимального пути из в в ориентированном графе(алгоритм фронта волны)…………………………………………………...….38 Заключение…………………………………………………………………………….42 Список используемой литературы………………………………..………………….45
Список литературы

Учебники, и учебные пособия: 1. Березина Л.Ю. «Графы и их применения»: пособие для учителей. М. Просвещение, 2014. -144 с. 2. Белов В.В., Воробьев Е.М., Шаталов В.Е. «Теория графов». - М.: ВШ, 2015.-654с. 3. Новиков Ф.А.» Дискретная математика для программистов». – Спб.: Питер, 2003.-304с 4. Кузнецов О.П., Адельсон-Вельский Г.М. «Дискретная математика для инженера».- 2-е изд., перераб. и доп. – М.: Энергоатомиздат,2014.-480с 5. Новиков, Ф.А. «Дискретная математика для программистов» [Текст]/Ф.А. Новиков. – СПб.: Питер, 2016. – 304 с. 6. Овчинников, В.А. «Алгоритмизация комбинаторно-оптимизационных задач при проектировании ЭВМ и систем»: учебник для вузов [Текст]/В.А. Овчинников. - М.: Изд-во МГТУ им. Н.Э.Баумана, 2016. – 228 с. 7. Подготовка к ЕГЭ. «Информатика и ИКТ».[Текст]:учебное пособие / Под ред. Н. В. Макаровой. — СПб.: Питер, 2015.-160c. 8. Судоплатов С.В., Овчинниова Е.В. «Элементы дискретной математики»: Учебник. – М.: ИНФРА-М, Новосибирск. Изд-во НГТУ, 2015.-87-89 9. Клини С.К. «Введение в математику»/пер. с англ. М. Просвещение, 2016. -526. с. Монографии: 1. Акимова М.К., Козлова В.Т. «Индивидуальность учащегося и индивидуальный подход» // Новое в жизни, науке и технике. Сер. «Педагогика и психология» № 3. М. Знание, 2014. -80 с. 2. Широков П.А. «Очерк основ геометрии». Лобачевского. 2-е изд. М.Наука. Главная редакция физико-математической литературы. 2013. -80 с.
Отрывок из работы

1.Глава Теоретико-методологические аспекты исследования математических графов 1.1 Основные понятия теории графов Теория графов является фундаментальным разделом дискретной математики, которая занимается исследованием качеств и типы графов, концепция теории графов применяется обширно в информатике и программировании, экономике, логистике, химии и иных сферах науки. Следует отметить, что единое определение «граф» в науке отсутствует, нет общепризнанного определения, многие авторы подразумевают под определением «граф» разнообразные, предметы, объекты, хотя и весьма схожие, у каждого автора своя точка зрения, свой взгляд на это, но все они сходятся во мнении, что графы это математические объекты, с их помощью решаются не лёгкие, а временами и сложные типы задач. Слово «граф» в математике означает иллюстрацию, где изображено несколько точек, некоторые из которых соединены линиями. В математической науке отведён довольно таки обширный и фундаментальный раздел, посвящённый изучению концепции графов, данный раздел занимается исследованием и анализом теории графов, раскрывает их свойства, характеризует типы, анализирует область возможного применения, раскрывает исторические аспекты эволюции теории графов. Если мы проанализируем само слово «граф», и обратимся к словарю латинского языка то увидим, что в переводе с латинского слова получим название «графио» что в последствии означает, «пишу» или «писать». С помощью теории графов развиваются графические умения по совершенствованию решения задач. Вначале рассмотрим ряд определений более детально. У ориентированного графа или орграфа рёбра ориентированы, называют их дугами и изображают стрелками, дуга может быть обозначена упорядоченной парой вершин, которые она связывает, – начальной и конечной. Рис.1. Ориентированный граф Рис.2 Неориентированный граф Что же касается неориентированного графа, то у него рёбра иллюстрируются линиями без ориентации. Соответственно, пара вершин, которую ребро связывает, считается неупорядоченной. Две эти вершины есть концы ребра. Если вершины a и b – концы ребра (или начало и конец дуги) графа, то считается, что вершины a и b инцидентны этому ребру (дуге), также ребро (дуга) инцидентно вершинам a и b. Если вершины a и b – концы ребра, то они (a и b) называются смежными. Многие учёные в области математики полагают и этим сходятся в суждении, что математически граф по своей сути это есть совокупность вершин и рёбер и представляется как универсальный способ наглядного представления достаточно разнообразных по своей сути задач. (рис.1). А так же описывается в изданиях по дискретной математике что граф, в котором вершины прямоугольной формы и направление рёбер не заданы, описывает блок-схему или структуру технической системы (рис.2). Далее, обратим внимание, что на рисунке 3 изображён граф-дерево, например, описание метода ветвей и границ - многоуровневая иерархическая система, в которой все вершины распределенные по нескольким уровням. Ниже на рисунке 4 чётко показан граф с дугами, изображающими связь меж вершинами, - это сеть. В виде примера разновидностей определений графа далее рассмотрим некоторые общеизвестные понятия, которые описаны в учебных пособиях великими математиками: Пусть V-непустое множество, - множество всех его двухэлементных подмножеств, пара (V, E), где E - произвольное подмножество множества , называют графом - неориентированным графом. Граф G структурирован из конечного непустого множества V, содержащего р вершин, и заданного множества X, содержащего q неупорядоченных пар разных вершин из V, каждую пару x={u, v} вершин в X именуют ребром графа G и считают, что х соединяет к и v. Что же касается теории графов, то сама концепция графов является весьма значимой, интересной, увлекательной и динамично развивающимся курсом в наше время, но что хочется отметить, что существуют отдельные моменты, которые всё таки не совсем изучены и исследованы. Теория графов является мощным средством для решения обширного круга серьёзных и не мало важных фактических проблем, в особенности велико значение графов как универсального языка при создании точных модификаций. С математическими графами встречаются уже в школьном курсе математики, там графы прослеживаются уже с первого класса, когда школьникам предлагается, отыскать, например, «потерявшееся число». Рассмотрим этот вид задания на примере рисунка. Ниже представлен рисунок 5 «потерявшееся число». Рис. 5«Потерявшееся число». Что же касается свойства графов, то здесь решая задачу про кёнигсбергские мосты, великий арифметик мира по имени Эйлер установил и указал свойства графа, проанализируем их: ? если все вершины графа чётные, то возможно одним простым росчерком начертить граф, вероятно движение начать с любой вершины и закончить в той же вершине; ? граф с двумя нечётными вершинами так же вероятно начертить одним росчерком, необходимо движение начать от всякой нечётной вершины, а заканчивать на иной нечётной вершине. ? граф с более чем двумя нечётными вершинами не представляется возможным начертить сразу. Вернёмся к истории с мостами из Кёнигсберга, она имеет своё логическое современное продолжение, в учебных пособиях по математике мы зачастую встречаем задачи, чьё решение основано именно на предложенном Эйлером способе. Рассмотрим её более детально. Решение задачи по Леонарду Эйлеру о Кёнигсбергских мостах: На упрощённой схеме города (графе) мостам соответствуют линии (ребра графа), а долям города — точки соединения линий (вершины графа). В процессе рассуждений математик пришёл к следующим выводам: • цифра нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно, не может существовать граф, который имел бы нечётное число нечётных вершин. • если же все вершины графа чётные, то возможно, без отрыва карандаша от листа бумаги, начертить (нарисовать) граф, одновременно с этим можно начать с любой вершины графа и закончить его в той же вершине. • если ровно две вершины графа нечётные, то можно, без отрыва ручки от листа бумаги, начертить граф, одновременно с этим вероятно начинать с любой из нечётных вершин и завершить его в другой нечётной вершине. • граф с несколькими нечётными вершинами нельзя начертить одним росчерком. Граф кёнигсбергских мостов имел четыре нечётные вершины, то есть все, а значит, не представляется возможным пройти по всем мостам, не проходя ни по одному из них дважды. > > Схема 1 Задача о Кёнигсбергских мостах С графами, сами того не замечая, мы сталкиваемся постоянно в быту. Но вернёмся к теории, графом, к примеру, является схема линий метрополитена, обычными графами являются схемы авиалиний, которые не редко вывешивается в аэропортах, схемы метро, и иллюстрация железных дорог на географических картах. Графы по своей специфичности являются существенным элементом моделей математики в самых разнообразных научных. Графы нам в жизни помогают наглядно представить взаимоотношения меж объектами или событиями в не простых и сложных по своей сути системах. В концепции графов имеется не мало алгоритмических задач в области дискретной математике могут быть описаны как задачи, так или иначе связанные с графами, к примеру, задачи, в которых необходимо решить какую-либо специфику структуры графа, или же найти в графе часть, удовлетворяющую неким требованиям, или же выстроить граф с заданными свойствами. Ниже дадим определение простого графа G. Пара (V(G), Е(G)) называется простым графом, если V(G) — непустое конечное множество элементов, называемых вершинами или узлами, или точками, а Е(G) — конечное множество неупорядоченных пар различных элементов из V(G), называемых рёбрами или линиями. Иногда V(G) называют множеством вершин, а Е(G) — множеством рёбер графа G. Вершинами считаются выбранные точки графа, а линии их объединяющие – рёбрами. Приведём и проанализируем пример. На рисунке 2 изображён простой граф G, у которого множеством вершин V(G) является множество {u, v, w, z}, а множество ребёр Е(G) состоит из пар {u, v}, {v, w}, {u, w} и {w, z}. По общепринятому понятию, ребро {v, w} соединяет вершины v и w, отметим, что так как Е(G) есть множество, а не семейством, то в простом графе данную пару вершин не может соединять множество рёбер. Большая часть результатов, приобретённых для простых графов, в отсутствие трудностей, допустимо, перенести на общие объекты, в которых две вершины абсолютно имеют все шансы объединения более чем одним ребром. Кроме того, имеются факторы, когда удобно снять ограничение, заключающееся в том, что ребро должно соединять две различные вершины, и допускать наличие петель, то есть рёбер, соединяющих вершину с ней самой. Рис. 6. Рис. 7 Полученный объект при этом, в котором могут присутствовать петли и кратные рёбра, будет носить имя общего графа, или просто графом (рис. 2.) Необходимо сразу отметить, что каждый простой граф является графом, но не каждый граф есть простой граф. Более точно, графом G называется пара (V(G), Е(G)), где V(G) — непустое конечное множество элементов, называемых вершинами, а Е(G) — конечное семейство неупорядоченных пар элементов из V(G) не обязательно различных, называемых рёбрами. Обратим внимание, что употребление слова «семейство» говорит о том, что допускают кратные ребра. Будем называть V(G) множеством вершин, а Е(G) — семейством ребер графа G. На рисунке 2 V(G) — изображено множество {u, v, w, z}, а Е(G) — это семейство, состоящее из рёбер {u, v}, {v, v), {v, v), {v, w}, {v, w}, (v, w}, {u, w}, {u, w} и {w, z}. О каждом ребре вида {v, w} говорят, что оно соединяет вершины v и w, значит, каждая петля {v, v} соединяет вершину v саму с собой. Предметом изучения в концепции графов являются также ориентированные графы, называемые не редко орграфами или сетями, однако употребим слово «сеть» в неком ином смысле. Орграфом D называется пара (V(D), A (D)), где V(D) — непустое конечное множество элементов, именуемых вершинами, а А (D) — конечное семейство упорядоченных пар элементов из V(D), под названием дуги или ориентированными ребрами. Необходимо разобраться, и понять, так что же такое дуга? Дадим определение. Дуга, у которой вершина v является первым элементом, а вершина w — вторым, называется дугой из v в w и обозначается (v, w). Обратим внимание, на то, что дуги (v, w) и (w, v) различны, на рисунке 3 изображен орграф, дугами которого являются (u, v), (v, v), (v, w), (v, w), (w, v), (w, u) и (w, z) порядок вершин на дуге показан стрелкой. Рис. 8 Рис. 9 Графы и орграфы – сами по себе существенно разные. В отдельных взятых случаях графы необходимо рассматривать как орграфы, в которых каждому отдельно взятому ребру соответствуют две противоположно ориентированные дуги (рис. 4). Стоит сказать, что язык концепции графов, однозначно и бесспорно, ещё не вышел на стандартизацию, каждый автор выдвигает свою собственную терминологию и гипотезу. Есть мнения, что многие специалисты в области дискретной математике по теории графов называют графом то, что мы обозначили простым графом, есть случаи, и особенно они отмечаются в приложениях, которые говорят: «…под графом понимается орграф, а есть моменты, когда графом называют объект, который получается, если снять критерий конечности множества вершин или семейства рёбер».
Не смогли найти подходящую работу?
Вы можете заказать учебную работу от 100 рублей у наших авторов.
Оформите заказ и авторы начнут откликаться уже через 5 мин!
Похожие работы
Дипломная работа, Высшая математика, 41 страница
1025 руб.
Служба поддержки сервиса
+7(499)346-70-08
Принимаем к оплате
Способы оплаты
© «Препод24»

Все права защищены

Разработка движка сайта

/slider/1.jpg /slider/2.jpg /slider/3.jpg /slider/4.jpg /slider/5.jpg