Проект на тему "Графы и области их применения"

Выполняя работу в рамках исследовательского проекта по математике на тему «Графы и области их применения» учащаяся 11 класса подробно изучает Теорию графов: рассматривает основные понятия (вершины, рёбра, пути, циклы). А также автор изучает виды графов (ориентированные и неориентированные, взвешенные) и способы их представления, ключевые задачи и алгоритмы, например поиск кратчайшего пути и связности, и анализирует, как графы применяются на практике в различных областях.

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

Оглавление

Введение
Глава 1. История возникновения графов
Глава 2. Понятие и виды графов
Глава 3. Графовый анализ
Глава 4. Области применения графов
Глава 5. Использование теории графов для решения задач ЕГЭ
Заключение

Графы – это математический инструмент, который используется для моделирования и анализа различных систем и отношений. Они позволяют составить сложные взаимосвязи между объектами и решать разнообразные задачи, такие как: поиск кратчайшего пути, определение связанности.

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

Цель проекта – изучение понятие графа, областей их применения графов и использования на практике.

Для реализации указанной цели были поставлены следующие задачи:

1. Изучить историю возникновения графов, понятие и виды графов,
2. Понять методы графового анализа,
3. Проанализировать области применения графов.

Объектом исследования являются графы и графовый анализ.

Предметом исследования – анализ областей применения графов и методов графового анализа.

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

Родоначальником теории графов считается выдающийся математик, член Петербургской академии наук Леонард Эйлер. В 1736 году в одном из своих писем он формулирует и предлагает решение задачи о семи кенигсбергских мостах, ставшей впоследствии одной из классических задач графов.

Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам (через реку Преголя), не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.

В 1736 году задача о семи мостах заинтересовала Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них. Ответ был «нельзя».

На упрощённой схеме части города (графе) мостам соответствуют линии (дуги графа), а частям города — точки соединения линий (вершины графа). В ходе рассуждений Эйлер пришёл к следующим выводам: число нечётных вершин (вершин, к которым ведёт нечётное число рёбер) графа должно быть чётно. Не может существовать граф, который имел бы нечётное число нечётных вершин.

Если все вершины графа чётные, то можно, не отрывая карандаша от бумаги, начертить граф, при этом можно начинать с любой вершины графа и завершить его в той же вершине.
Граф с более чем двумя нечётными вершинами невозможно начертить одним росчерком.
Граф кёнигсбергских мостов имел четыре нечётные вершины (то есть все), следовательно, невозможно пройти по всем мостам, не проходя ни по одному из них дважды.

Граф - математический объект, который изображает отношения между сущностями. Граф состоит из вершин (объектов) и рёбер (связей). Вершины обычно обозначаются буквами или числами, а ребра – линиями, которые соединяют вершины.

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

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

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

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

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

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

Графовый (также сетевой) анализ - это набор методов, направленных на изучение связей между сущностями. При помощи этих методов исследуется структура графа и выявляются неочевидные зависимости. Извлекать из графов полезную информацию позволяют графовые алгоритмы. Графовый анализ эффективен, когда объекты рассматриваются в контексте связей с другими объектами.

Преимущества графового анализа:

• Понятность и наглядность: графы представляют информацию в виде узлов и ребер, что облегчает восприятие сложных взаимосвязей. Графическое представление позволяет легко увидеть и понять структуру данных.
• Эффективность поиска и обработки информации: графы обладают мощными алгоритмами поиска, обхода и обработки данных. Они позволяют быстро находить пути между узлами, определять связи и отношения, а также выполнять различные операции над графами.
• Масштабируемость: графы позволяют легко добавлять новые узлы и ребра, а также изменять структуру и связи между объектами без необходимости внесения глобальных изменений в систему. Это делает графы гибким инструментом для моделирования сложных и динамических систем.
• Анализ и визуализация данных: графы позволяют проводить различные аналитические исследования. Визуализация графов помогает наглядно представить результаты анализа и обнаружить скрытые зависимости.
• Решение задач оптимизации: графы применяются для решения различных задач оптимизации, таких как построение оптимальных маршрутов, планирование задач, распределение ресурсов и др. Оптимизация на графах позволяет экономить время, деньги и ресурсы.
• Использование в сетевых и социальных анализах: графы широко применяются в сетевом и социальном анализе для изучения взаимосвязей между участниками сети или людьми. Графовый подход позволяет выявить ключевые сообщества, влиятельных пользователей и другие важные характеристики сети или социальной структуры.

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

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

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

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

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

Задача 1.
Пятеро ученых, участвующих в научной конференции, обменялись рукопожатиями. Сколько всего было сделано рукопожатий?

Решение: Обозначим ученых вершинами графа и проведем от каждой вершины линии к четырем другим вершинам. Получаем 10 линий, которые и будут считаться рукопожатиями

Задача 2.
Из города А в город Б ведут три дороги, а из города Б в город С - четыре дороги. Сколькими способами можно проехать из А в С через В?

Решение: Возьмем одну дорогу, ведущую из А в Б. Ее можно продолжить до С четырьмя различными способами. То же самое можно сделать с каждой из двух других дорог, ведущих из А в Б. Всего из А в С через Б можно проехать 3 · 4 = 12 способами.

Задача 3.
Сегодня учитель объявил отметки за контрольную работу. Члены математического кружка Витя, Коля, Петя, Наташа, Ира, Марина и др. решили наглядно показать, какую отметку кто получил. Как это сделать?
В данной задаче есть два множества. Следует установить зависимость между элементами этих множеств.
{В, К, П, Н, И, М} – множество учеников,
{1, 2, 3, 4, 5} – множество отметок.

Такой чертеж называют графом:

Решение задачи можно показать и в виде таблицы.

	В	К	П	Н	И	М
1
2
3	+
4		+	+		+
5				+		+

Задача 4.
В пяти корзинах лежали яблоки пяти разных сортов. Яблоки первого сорта лежат в корзинах Г и Д; в корзинах А, Б, В имеются яблоки пятого сорта, в корзине В имеются к тому же яблоки четвертого сорта, а в корзине Д – третьего. Пронумеруйте каждую корзину так, чтобы в корзине № 1 были яблоки первого сорта (хотя бы одно); в корзине № 2 - второго и т.д.

Решение:
Составим граф

Ответ: №1 – Г; №2 – А или №2 – Б; №3 – Д; №4 – В; №5 – Б или №5 – А.

Задача 1.
Между населенными пунктами A ,B, C, D, E, F построены дороги, протяженность которых приведена в таблице (отсутствие числа означает, что прямой дороги нет). Определить длину кратчайшего пути между пунктами E и F. (Передвигаться можно только по построенным дорогам).

	A	B	C	D	E	F
A		2	4
B	2		1		7
C	4	1		3	4
D			3		3
E		7	4	3		2
F					2

Решение:
В этом задании исходные данные представлены в виде таблицы, которую можно рассматривать как матрицу неориентированного взвешенного графа. Вершинами данного графа являются населенные пункты A, B, C, D, E, F. Элементы данной матрицы показывают, какие населенные пункты связаны дорогами и какова их длина.

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

Сначала изобразим конечный пункт F. В этот пункт можно попасть только из пункта Е. Соединяем пункты Е и F дугой и указываем вес этой дуги. Он равен двум, то есть расстоянию между пунктами Е и F. Соответственно по графу можно увидеть, что в пункт Е можно попасть из пунктов B, C и D. В пункт В можно попасть из А. В пункт С – из В и А. В пункт D – из С. В пункт В попадаем из А. В пункт С – из В и А. И в пункт В из А.

Данную схему можно рассматривать как ориентированный взвешенный граф, который наглядно показывает, что есть 5 путей из пункта А в пункт F. Подсчитываем длину каждого пути
1 путь: 2+7+2=11;
2 путь: 2+1+4+2=9;
3 путь: 4+4+2=10;
4 путь2+1+3+3+2=11;
5 путь: 4+3+3+2=12.

Так как нам надо определить длину кратчайшего пути, то выбираем второй путь, длина которого равна 9. Данный ответ находится под цифрой 1. Поэтому в ответе надо поставить крестик в клеточке, соответствующей первому ответу.

Задача 2.
У исполнителя Утроитель две команды, которым присвоены номера 1. Прибавь 1;
2.Умножь на 3. Запишите порядок команд в программе преобразования числа 1 в число 22, содержащей не более 5 команд.

Решение:
Для решения данного задания используем метод от обратного, то есть будем преобразовывать число 22 в 1. Соответственно команды исполнителя заменим командами антагонистами, то есть команду «Прибавь 1» заменим командой «Вычти 1», а «Умножь на 3» заменим командой «Раздели на 3».

Ход выполнения команд можно изобразить в виде дерева, каждая вершина которого имеет две ветки, соответствующие командам 1 и 2. Корнем этого дерева является число 22. Это дерево будет иметь 5 ярусов, так как программа должна содержать не более 5 команд. Но здесь нужно учесть один момент. Если число делится на 3, то вершина будет иметь 2 потомка, а если нет, то одного (то есть делить на 3 мы не можем, а можем только вычитать 1). Получаем следующее дерево.

Инвертируем теперь команды и преобразуем число 1 в 22.
1+1*3+1*3+1=22.
Учитывая номера команд, записываем программу решения данной задачи в виде последовательности соответствующих команд. Ответ: 12121.

В данном индивидуальном проекте по математике на тему «Графы и области их применения» учащейся 11 класса показано, что графы широко используются в различных областях нашей жизни: информатике, математике, логистики, экономике, в различных исследованиях.

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

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