Поделиться
Проектная работа ЭЙЛЕРОВЫ И ГАМИЛЬТОНОВЫ ГРАФЫ .pdf
МАОУ ―Центр образования №51 им. В. М. Паращенко‖ городского округа город Уфа республики Башкортостан
Проектно-исследовательская работа по математике на тему:
Выполнили: Харисов. М,
Бикметов. А, учащиеся 10А класса
МАОУ ЦО №51 имени В. М. Паращенко
ГО город Уфа РБ Научный руководитель: Егорова Н.Т., учитель математики высшей категории
МАОУ ЦО №51 имени В. М. Паращенко
ГО город Уфа РБ
2026
ВВЕДЕНИЕ………………………………………………………………………3
1. ИСТОРИЯ ВОЗНИКНОВЕНИЯ ГРАФОВ.
1.1 «ЗАДАЧА О КЕНИГСБЕРГСКИХ МОСТАХ»…………………4
1.2 ИСТОРИЧЕСКИЕ СВЕДЕНИЯ………………………………….4
2.1. ВИДЫ ГРАФОВ…………… …………………………………..5
2.2. СПОСОБЫ ЗАДАНИЯ ГРАФОВ… ……………………….....10
2.3. РЕШЕНИЕ ЗАДАЧИ О МАРШРУТИЗАЦИИ АВТОБУСНОГО
ТРАНСПОРТА В МИКРОРАЙОНЕ ИНОРС г. УФЫ……… 11
3.1. ДОДЕКАЭДР ГАМИЛЬТОНА. ………………………………...12
3.2. ЗАДАЧА КОММИВОЯЖЕРА……………………………………12
3.3. ЗАДАЧА ЭЙЛЕРА О ШАХМАТНОМ КОНЕ…………….........13
3.4. ПРОГРАММЫ НА ЯЗЫКЕ ПРОГРАММИРОВАНИЯ
PYTHON……………………………………………………………14
3.5. ЗАДАЧИ, РЕШАЕМЫЕ С ПОМОЩЬЮ ГРАФОВ……………..14
3.6. ЗАДАЧИ ИЗ ВПР ПО МАТЕМАТИКЕ ПО ТЕМЕ ГРАФЫ…..14
ЗАКЛЮЧЕНИЕ………………………………………………………………….17
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ…………………………….18
ПРИЛОЖЕНИЯ…………………………………………………………………19 ВВЕДЕНИЕ
Прогуливаясь по родному микрорайону Инорс мы задумались, почему не ходят маршрутные автобусы по всем улицам микрорайона. И выдвинули следующее предположение, можно ли решить задачу маршрутизации автобусного транспорта математическими методами. Изучая эту задачу, мы узнали, что подобную задачу решал великий ученый Леонард Эйлер (ПРИЛОЖЕНИЕ 1)
Теория графов в настоящее время является интенсивно развивающимся разделом математики. Это объясняется тем, что в виде графовых моделей описываются многие объекты и ситуации, что очень важно для нормального функционирования общественной жизни. Именно этот фактор определяет актуальность их более подробного изучения. Теория графов широко применяется в решении экономических и управленческих задач, в программировании, химии, конструировании и изучении электрических цепей, коммуникации, психологии, социологии, лингвистике и в других областях.
Для чего строят графы? Чтобы отобразить отношения на множествах. По сути, графы помогают визуально представить всяческие сложные взаимодействия: аэропорты и рейсы между ними, разные отделы в компании, молекулы в веществе.
В практической части узнаем, как решаются задачи с помощью графов. Цель работы: выяснить особенности применения теории графов в различных областях знаний и при решении логических задач.
Задачи:
* Познакомиться с историей теории графов;
* Изучить виды и свойства графов;
* Изучить всемирно известные задачи, решаемые с помощью графов;
* Рассмотреть способы решения задач с помощью графов;
* Показать практическое применение теории графов в различных областях знаний;
* Составить математический справочник для школьников
Методы работы: Работа с различными источниками информации. Описание, сбор, систематизация материала.
Датой рождения теории графов можно считать 1736 год, когда была опубликована статья Леонарда Эйлера, посвящѐнная решению головоломки под названием «Задача о кѐнигсбергских мостах». Издавна среди жителей Кѐнигсберга (теперь Калининграда) была распространена такая загадка: как пройти по всем мостам, не проходя ни по одному из них дважды? Многие кѐнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок. Но никому это не удавалось, однако не удавалось и доказать, что это даже теоретически невозможно. В 1736 году задача о семи мостах заинтересовала выдающегося математика, члена Петербургской академии наук Леонарда Эйлера, о чѐм он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым легко определить, можно ли пройти по всем мостам, не проходя дважды ни по одному из них (в случае семи мостов Кѐнигсберга это невозможно). Для того, чтобы решить эту задачу, Эйлер сделал специальные обозначения. Каждую часть суши (остров или берег реки) он обозначил кружком на бумаге, а затем соединил линиями те кружки, между которыми существуют мосты. (ПРИЛОЖЕНИЕ 2). Такие обозначения подчеркивают, что в этой задаче фактическое расположение, форма, длина и другие свойства объектов не представляют интереса, важны только связи между ними. Такая картинка на бумаге или на экране компьютера называется графом. Кружки — это его вершины, а линии — рѐбра.
Долгое время методы, аналогичные эйлеровым, использовались для исследования подобных развлекательных задач. Но в XIX веке Г.Кирхгоф и А.Кэли нашли им более достойное применение. Первый с помощью графов стал описывать электрические, а второй – химические «цепи» и «деревья». Существующее название закрепилось за этой наукой с 1936 года, после выхода в свет монографии венгерского математика Д.Кѐнига. Термин «граф» происходит от греческого слова «графио» – пишу. С своей книге Д.Кѐнига говорит о 5 наглядной графической интерпретации основных понятий этой теории, и во-вторых, о тесной связи еѐ с геометрией. И действительно, этот раздел дискретной математики находится на стыке геометрии, топологии, комбинаторики и ряда других математических дисциплин и интенсивно использует их методы.
Важнейший способ задания графа – графический. Его преимущества следуют из наглядности всех элементов графа, что позволяет быстро визуально анализировать его строение. Это явное превосходство метода предопределило его широкое использование. В первую очередь, это относится к тем сферам применения графов, которые связаны с передачей какой-то информации большому числу людей. Например, схемы движений различных видов транспорта, (ПРИЛОЖЕНИЕ 3) эвакуации людей из помещений в чрезвычайных ситуациях, размещения экспозиций выставок и т.д. даются только в графическом виде, иначе их не сможет воспринять большая масса народа, что, неизбежно, создаст очевидные проблемы. Однако у этого метода представления графов есть и свои недостатки. К ним относятся громоздкость и трудность машинного восприятия. Второе особенно важно при обработке графа с помощью ЭВМ.
Термин «граф» в математике определяется следующим образом:
Граф – это конечное множество точек – вершин, которые могут быть соединены линиями – ребрами.
В качестве примеров графов могут выступать чертежи многоугольников, электросхемы, схематичное изображение авиалиний, метро, дорог и т.п. Генеалогическое дерево также является графом, где вершинами служат члены рода, а родственные связи выступают в качестве ребер графа
(ПРИЛОЖЕНИЕ 3).
Число ребер, которое принадлежит одной вершине, называется степенью вершины графа. В некоторой литературе вместо степени говорится валентность графа. Если степень вершины нечетное число, вершина называется – нечетной. Если степень вершины число четное, то и вершина называется четной.
Нуль-граф – это граф, состоящий только из изолированных вершин, не соединенных ребрами.
Полный граф – это граф, каждая пара вершин которого соединена ребром. N-угольник, в котором проведены все диагонали, может служить примеров полного графа.(РИС.1)
РИС.1
Если в графе каждые две вершины связаны ребром, то это связный граф. Граф называется несвязным, если в нем есть хотя бы одна пара несвязанных вершин.
Граф, в которых все ребра являются звеньями, то есть порядок двух концов ребра графа не существенен, называется неориентированным.
Неориентированный граф можно представить в виде ориентированного графа, если каждое его звено заменить на две дуги с противоположным направлением.
Мультиграф — такой граф, в котором пары вершин соединены более, чем одним ребром. То есть, есть кратные рѐбра, но нет петель.
Граф, содержащий петли и кратные ребра, называется псевдографом.
Граф называется двудольным, если множество его вершин можно разбить на два подмножества так, чтобы никакое ребро не соединяло вершины одного и того же подмножества.
Если в графе выбрать такой путь, когда начальная и конечная точка совпадают, то такой путь называется циклом графа. Если прохождение через каждую вершину графа происходит не более одного раза, то цикл называется простым.
Если граф связный, но не содержит циклов, то такой граф называется деревом.
Лесом называют граф, связные компоненты которого являются деревьями. В частности, дерево не может иметь петель и кратных ребер.
Последовательность из ребер графа (не обязательно различных) называется маршрутом длины , если любые два рядом стоящие в этой последовательности ребра смежные. Кроме того, если эти два рядом стоящие ребра ориентированные, то в инцидентную им вершину ребро, стоящее слева, должно входить, а ребро, стоящее справа, из нее выходить.
Эйлеровым графом называется граф, в котором можно обойти все вершины и при этом пройти одно ребро только один раз. В нѐм каждая вершина должна иметь только чѐтное число рѐбер.
Граф называется полуэйлеровым, если ровно две вершины графа нечетные. Его можно обвести, не отрывая карандаша от бумаги, начав в одной нечетной вершине, а закончив в другой.
Эйлеровый граф Полуэйлеровый граф
Гамильтоновом графом (или гамильтоновым циклом) называется такой простой цикл в графе, который проходит через каждую его вершину ровно один раз, и возвращается в начальную точку.
Граф называется полугамильтоновым, если существует маршрут, содержащий каждую его вершину ровно один раз. Этот граф не замкнутый.
Существуют следующие способы задания графов:
1) ГРАФИЧЕСКИЙ – все элементы множества V, обозначаются точками на плоскости, проводятся линии, соединяющие вершины;
2) МАТРИЧНЫЙ – с помощью матрицы смежности и матрицы инцидентности;
3)АНАЛИТИЧЕСКИЙ – задается список ребер и список вершин.
2.3. РЕШЕНИЕ ЗАДАЧИ О МАРШРУТИЗАЦИИ АВТОБУСНОГО
Изучая задачи Эйлера, и труды других ученых, мы пришли к следующим выводам о графах:
1).Число нечѐтных вершин (вершин, к которым ведѐт нечѐтное число рѐбер) графа должно всегда быть чѐтно. То есть, просто не может существовать графа, который имел бы нечѐтное число нечѐтных вершин.
2).Если все вершины графа чѐтные, то его можно начертить, не отрывая карандаша от бумаги, при этом начинать можно с любой вершины графа и завершить его в ней же (эйлеровый граф).
3) Если ровно две вершины графа нечетные, то его можно обвести, не отрывая карандаша от бумаги, начав в одной нечетной вершине, а закончив в другой (полуэйлеровый граф).
4).Граф с более чем двумя нечѐтными вершинами невозможно начертить одним росчерком.
В своей работе мы составили граф микрорайона Инорс, (ПРИЛОЖЕНИЕ 3) и убедились, что задача маршрутизации микрорайона Инорс по всем улицам невозможно решить. Граф микрорайона имеет более 2 (точнее 18) нечѐтных вершин, следовательно, невозможно пройти по всем улицам микрорайона, не проходя ни по одному из них дважды. Так как данный граф не является эйлеровым и гамильтоновым, то невозможно проходить через все ребра по одному разу. Можно организовать автобусные маршруты, которые могут пройти только по отдельным улицам. Поэтому делаем вывод, нельзя составить маршрут для автобусного транспорта который будет проходить по всем улицам Инорса. Мы рекомендуем при строительстве новых микрорайонов, сначала начертить граф, который является эйлеровым и гамильтоновым, чтобы по всем улицам микрорайона смогли составить маршрут автобусного транспорта.
3.1. ДОДЕКАЭДР ГАМИЛЬТОНА
Название «гамильтонов цикл» произошло от задачи «Кругосветное путешествие», предложенной ирландским математиком Вильямом Гамильтоном в 1859 году. Нужно было, выйдя из исходной вершины графа, обойти все его вершины и вернуться в исходную точку. Граф представлял собой укладку додекаэдра, каждой из 20 вершин графа было приписано название крупного города мира. В 1859 году была выпущена в продажу головоломка – деревянный додекаэдр (двенадцатигранник), двадцать вершин которого были обозначены гвоздиками. Каждая вершина имела название одного из крупнейших городов мира – Кантон, Дели, Брюссель, и т.д. Задача заключалась в нахождении замкнутого пути, который проходит по ребрам многогранника, побывав в каждой вершине только один раз. Для отмечания пути использовался шнур, который цепляли за гвоздики. (ПРИЛОЖЕНИЕ 4)
По аналогии головоломке Гамильтона мы создали свою головоломку. Нужно обойти все вершины додекаэдра с названиями городов Башкортостана и вернуться в исходную точку. Можно начинать с города Уфа. Мы смогли решить данную задачу, рассмотрели 20 крупных городов Башкортостана. Решение сначала выполнила на развертке додекаэдра (додекаэдра имеет 20 вершин) (ПРИЛОЖЕНИЕ 5).
Одна из самых известных и важных задач транспортной логистики (и комбинаторной оптимизации) – задача коммивояжера или «задача о странствующем торговце» (англ. «Travelling Salesman Problem», TSP). Также встречается название «задача китайского почтальона» (англ. «Chinese Postman Problem», CPP). Суть задачи сводится к поиску оптимального (кратчайшего, быстрейшего или самого дешевого) пути, проходящего через промежуточные пункты по одному разу и возвращающегося в исходную точку. К примеру, нахождение наиболее выгодного маршрута, позволяющего коммивояжеру посетить со своим товаром определенные города по одному разу и вернуться обратно. Мерой выгодности маршрута может быть минимальное время поездки, минимальные расходы на дорогу или минимальная длина пути. В наше время, когда стоимость доставки часто бывает сопоставима со стоимостью самого товара, а скорость доставки — один из главных приоритетов, задача нахождения оптимального маршрута приобретает огромное значение. Кто и когда впервые начал исследовать проблему задачи коммивояжера неизвестно, но уже в 1832 году была издана книга, содержащая советы для коммивояжеров. В этой книге была описана задача нахождения кратчайшего пути для торговца или курьера, которому необходимо доставить товар в ряд городов, и предлагались примеры маршрутов. Однако математический аппарат для решения задачи не приводился. Одним из первых, кто сформулировал ранний вариант этой задачи, был выдающийся ирландский математик, физик и механик XIX в. — Уильям Роуэн Гамильтон. В 1930 году австрийско-американский математик Карл Менгер сформулировал задачу коммивояжера как «задачу найти кратчайший путь между конечным множеством мест, расстояние между которыми известно». Современное название «задача коммивояжера» или «задача странствующего торговца» (англ. «Traveling Salesman Problem») было предложено американским математиком Хасслером Уитни. Пример практического приложения задачи коммивояжера: фирме требуется развести товары со склада по списку магазинов, используя одну машину, и вернуть эту машину на склад, причем машина должна пройти минимально возможное расстояние. Представление задачи коммивояжера графом очевидно: города — это вершины, а дороги — ребра. Как и в случае задачи китайского почтальона, для полного представления задачи нужен взвешенный граф, в котором ребрам-дорогам приписаны их длины. Однако можно заметить, что любой (не обязательно оптимальный) маршрут коммивояжера представляет собой гамильтонов цикл. Следовательно, справедливо замечание: задача коммивояжера разрешима тогда и только тогда, когда граф этой задачи гамильтонов.
Задача о шахматном коне: можно ли, начиная из произвольного поля на шахматной доске, ходить конем в такой последовательности, чтобы, пройдя через каждое из шестидесяти четырех полей доски, вернуться в исходное положение (ПРИЛОЖЕНИЕ 6).
3.4. ПРОГРАММЫ НА ЯЗЫКЕ ПРОГРАММИРОВАНИЯ PYTHON.
Для решения задачи о коммивояжера и задачи о шахматном коне мы создали программы на языке программирования PYTHON (ПРИЛОЖЕНИЕ 7).
В своей работе мы подобрали занимательные логические и олимпиадные задачи для учащихся 5-8 классов с подробным решением (ПРИЛОЖЕНИЕ 8).
3.6. ЗАДАЧИ ИЗ ВСЕРОССИЙСКОЙ ПРОВЕРОЧНОЙ РАБОТЫ
Начиная с 2026 года, в программу ВПР по математике 7 и 8 классов включены задачи по теме Графы. Некоторые из этих задач из ВПР представляют собой задачу коммивояжера. Применение задачи коммивояжера довольно обширно. Вот лишь некоторые возможные варианты применения задачи коммивояжера на практике в экономике: определение оптимального маршрута грузоперевозок; расчет наилучших маршрутов для курьеров и почтальонов. Кроме логистики, задачи коммивояжера находит применение и в других областях экономики и человеческой деятельности: финансы (оптимизация денежных потоков, например, поиск путей перевода денежных средств с минимальными транзакционными издержками), туризм (расчет маршрутов экскурсий и туров), шоу-бизнес (организация турне музыкальных групп), биология (сборка генома), телекоммуникации и связь (управление спутникам, проектирование телекоммуникационных сетей), информатика (кластеризация массивов данных), энергетика и коммунальное хозяйство (соединение населенных пунктов линиями электропередач и газоснабжения), электроника (проектирование топологий микросхем). Поэтому полезно уметь решать данные задачи.
Для учащихся 5-8 классов мы разработали математический справочник с задачами по теме Графы и алгоритмами решения данных задач (ПРИЛОЖЕНИЕ ).
Графы широко используются в градостроительстве при проектировании сетей водо-, газо-, тепло-, электроснабжения и в экономике, например, в «сетевом» планировании.
Теория информации широко использует свойства двоичных деревьев.
Например, если нужно закодировать некоторое число сообщений в виде определенных последовательностей нулей и единиц различной длины. Код считается наилучшим, для заданной вероятности кодовых слов, если средняя длина слов наименьшая в сравнении другими распределениями вероятности. Для решения такой задачи Хаффман предложил алгоритм, в котором, код представляется деревом-графом в рамках теории поиска. Для каждой вершины предлагается вопрос, ответом на который может быть либо, «да», либо «нет» – что соответствует двум ребрам, выходящим из вершины. Построение такого дерева завершается после установления того, что требовалось. Это может применяться в интервьюировании нескольких человек, когда заранее неизвестен ответ на предыдущий вопрос, план интервью представляется в виде двоичного дерева (ПРИЛОЖЕНИЕ 10).
Еще А.Кэли рассмотрел задачу о возможных структурах насыщенных (или предельных) углеводородов, молекулы которых задаются формулой:
Каждую молекулу предльного углеводорода можно представить в виде дерева. При удалении всех атомов водорода, атомы углеводорода, которые остались, образуют дерево с вершинами, степень которых не выше четырех. Значит, количество возможных искомых структур (гомологов данного вещества) равняется числу деревьев, степени вершин которых, не больше 4. Это задача сводится к задаче о перечислении деревьев отдельного вида (ПРИЛОЖЕНИЕ ).
Процесс размножения бактерий – это одна из разновидностей ветвящихся процессов, встречающихся в биологической теории. Пусть каждая бактерия по истечению определенного времени или погибает, или делится на две. Следовательно, для одной бактерии мы получим двоичное дерево размножения ее потомства. Вопрос задачи заключается в следующем: какое количество случаев содержит k потомков в n-м поколение одной бактерии? Данное соотношение в биологии носит название процесс Гальтона - Ватсона, которое обозначает необходимое количество нужных случаев (ПРИЛОЖЕНИЕ ).
Сложная утомительная задача для любого радиолюбителя – создание печатных схем (пластина диэлектрика – изолирующего материала и вытравленные дорожки в виде металлических полосок). Пересечение дорожек происходит только в определенных точках (местах установления триодов, резисторов, диодов и пр.) по определенным правилам. В результате перед ученым стоит задача вычертить плоский граф, с вершинами (ПРИЛОЖЕНИЕ ).
Интернет – всемирная система объединенных компьютерных сетей для хранения и передачи информации. Сеть интернет можно представить в виде графа, где вершины графа – это интернет сайты, а ребра – это ссылки (гиперссылки), идущие с одних сайтов на другие.
Веб-граф (Интернет), имеющий миллиарды вершин и ребер, постоянно меняется – спонтанно добавляются и исчезают сайты, пропадают и добавляются ссылки. Однако Интернет имеет математическую структуру, подчиняется теории графов и имеет несколько «устойчивых» свойств. Веб-граф разрежен. Он содержит всего лишь в несколько раз больше ребер, чем вершин (ПРИЛОЖЕНИЕ ).
ЗАКЛЮЧЕНИЕ.
В данной работе изучена и проанализирована познавательная и научная литература, рассмотрены области практического применения графов. В работе была подробно изучена теория графов, доказана предположение, что задачу маршрутизации автобусного транспорта можно решить математическими методами. Мы показали, что изучение графов может помочь в решении логических задач, кроме того, показаны применение графов в разных областях науки. Также в работе рассмотрены всемирно известные задачи по нахождению гамильтоновых циклов: головоломка Гамильтона, задача коммивояжера и задача Эйлера про шахматного коня. Составлены программы на языке программирования PUTON для решения
задач коммивояжера и задачи про шахматного коня.
В своей работе мы изучили новые задания из ВПР по математике для 7 и 8
классов по теме Графы. Конечный результат оформлен в виде Математического справочника по теме ГРАФЫ для школьников 4 – 8 классов с подборкой задач, и алгоритмами решения задач с применением свойств эйлеровых и полуэйлеровых графов.
С материалами нашей работы по теме «Эйлеровы и гамильтоновы графы» можно ознакомиться на образовательных порталах ЗНАНИО и ИНФОУРОК.
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ
1. Березина Л. Ю. «Графы и их применение» – М.: «Просвещение», 1979
2. Зыков А. А. Основы теории графов. — М.: «Вузовская книга», 2004. — С. 664
3. Оре О. «Графы и их применения», М. «Мир», 1965 4. Харари Ф. Теория графов / Пер.с англ. и предисл. В. П. Козырева. Под ред. Г. П. Гаврилова. Изд. 2-е. - М.: Едиториал УРСС, 2003. - 296 с.
Интернет-ресурсы:
1. https://www.sites.google.com/a/labore.ru/teoria-grafov-i-eeprimenenie/vvedenie-v-teoriu/gamiltonov-cikl-i-gamiltonov-graf
2. https://skysmart.ru/articles/mathematic/osnovnye-ponyatiya-teorii-grafov
3. https://knastu.ru/media/files/page_files/page_421/posobiya_2013/_Nekrasov a_Diskretnaya_matematika_Chast2.pdf
4. https://zaytsev.net/4xx/course-2/Discrete%20maths/lections_theme_02.pdf
5. http://galyautdinov.ru/post/zadacha-kommivoyazhera
ПРИЛОЖЕНИЕ 1
ПРИЛОЖЕНИЕ 2
ПРИЛОЖЕНИЕ 3
ПРИЛОЖЕНИЕ 4
ПРИЛОЖЕНИЕ 4
Уильям Роуэн Гамильтон (1805 – 1865) – ирландский математик, физик. (William Rowan Hamilton)
 |
ПРИЛОЖЕНИЕ 5
ПРИЛОЖЕНИЕ 6
ПРИЛОЖЕНИЕ 7 ПРОГРАММЫ НА ЯЗЫКЕ ПРОГРАММИРОВАНИЯ PYTHON 1. ЗАДАЧА КОММИВОЯЖЕРА
ПРИЛОЖЕНИЕ 8
№1 . В агентстве по недвижимости работают менеджеры Игорь, Сергей и Пѐтр. Обслуживаются объекты О1, О2, О3, О4, О5, О6, О7, О8. Построить граф для отображения отношений "Игорь работает с объектами О4, О7", "Сергей работает с объектами О1, О2, О3, О5, О6", "Пѐтр работает с объектом О8".
Решение. Граф, отображающий данные отношения, будет двудольным, так как менеджер не работает с менеджером и объект не работает с объектом. Но граф будет ориентированным. Например, Игорь работает с объектом О4, но не объект О4 работает с Игорем. Часто, когда такое свойство отношений очевидно, необходимость давать рѐбрам направления может показаться "математической тупостью". Но всѐ же, и это вытекает из строгого характера математики, если отношение носит односторонний характер, то давать направления рѐбрам нужно. В приложениях отношений эта строгость окупается, например, в программах, предназначенных для планирования, где тоже применяются графы и маршрут по вершинам и рѐбрам должен проходить строго в заданном направлении. Итак, получаем следующий ориентированный двудольный граф:
№2. Лист бумаги Плюшкин разрезает на 3 части. Некоторые из полученных листов он также разрезает на 3 части. Несколько новых листиков он вновь разрезает на 3 и более мелкие и т.д. Сколько Плюшкин получает листиков бумаги, если разрезает k листов?
Решение. Листы бумаги обозначим на рисунке кружками. Кружки, соответствующие листам, которые разрезаются, закрасим целиком, остальные оставим незакрашенными. При разрезании одного листка на 3 части число листков увеличивается на 2 (появляются 3 новых вместо одного). Если же было разрезано k листов, то образовалось 1+2 k листов. №3. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Е?
Решение. Заметим, что количество путей в город Е является суммой путей в города Ж, Г и Д. Количество путей в город Ж — сумма путей в города Г и Б. Таким образом получаем: Г = Б + В Д = Г + В Ж = Б + Г Е = Ж + Г + Д Заметим, что в пункты Б и В можно попасть единственным способом — из города А. Отметим на рисунке индексами сверху каждого пункта количество путей, с помощью которых в него можно попасть и посчитаем итоговое.
Ответ:8.
№4. На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город М, проходящих через город В?
Решение. Из рисунка видно, что любой путь из А в М проходит через И. По условию задачи мы должны искать только те пути, которые проходят через В. Обозначим число путей через N. По теореме: Пусть G — ориентированный граф без циклов, x, y и z — три вершины этого графа. Тогда число путей из x в y, проходящих через z, равно p(x, z)p(z, y). В частности, если все пути из x в y проходят через z, то p(x, y) = p(x, z)p(z, y) видно, что имеется четыре пути из А в В (А→Б→В, А→В, А→Г→В, А→Д→Г→В), три пути из В в И (В→Е→И, В→Ж→И, В→Е→Ж→И) и три пути из И в М (И→К→М, И→М, И→Л→М).
Получаем N=4*3*3=36.
Ответ: 36.
№5. На рисунке справа схема дорог Н-ского района изображена в виде графа; в таблице содержатся сведения о протяженности каждой из этой дорог (в км). Определите, какова протяженность дороги из пункта Б в пункт В. В ответе указать целое число.
Решение. Из рисунка видно, что у вершины Е есть ровно один сосед – вершина Д. Найдем в таблице вершину с единственным соседом, это вершина П3, а еѐ сосед – П4. Следовательно, П3=Е, П4=Д. Точно так же замечем, что только В и П5 имеют по четыре соседа. Следовательно, П5=В. У вершины Д есть ещѐ один сосед, помимо В и Е – это вершина Г. Третьим соседом вершины П4 является П2, значит П2=Г. Только вершина А и П6 имеют по два соседа, поэтому П6=А. Остается только вершина Б=П1. Итак, мы доказали, что П1=Б, П5=В, следовательно, длина дороги из Б в В равна 8.Ответ: 8 км.
ПРИЛОЖЕНИЕ 9
ЗАДАЧИ ИЗ ВПР ПО МАТЕМАТИКЕ ПО ТЕМЕ ГРАФЫ
 |
ПРИЛОЖЕНИЕ 10 Математический справочник по теме ГРАФЫ
ПРИЛОЖЕНИЕ 11
Генеалогическое древо
Электрическая схема
Схема Санкт-Петербургского метро
ПРИЛОЖЕНИЕ 12
Публикация на образовательном портале «ЗНАНИО»
Материалы на данной страницы взяты из открытых источников либо размещены пользователем в соответствии с договором-офертой сайта. Вы можете сообщить о нарушении.
