Графы при решении задач


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

Рис. 13
Если нечетных точек в фигуре нет, то она всегда поддается вырисовыванию одним росчерком пера, безразлично, с какого места ни начинать черчение. Таковы фигуры 1 и 5.
Если в фигуре имеется только одна пара нечетных точек, то такую фигуру можно нарисовать одним росчерком, начав черчение в одной из нечетных точек (безразлично вкакой).
Легко сообразить, что вычерчивание должно оканчиваться во второй нечетной точке. Таковыфигуры 2, 3, 6. В фигуре 6, например, вычерчивание надо начинать либо из точки А, либо из точки В.

Рис. 14
Если фигура имеет более одной пары нечетных точек, то она вовсе не может быть нарисована одним росчерком. Таковы фигуры 4 и 7, содержащие по две пары нечетных точек. Сказанного достаточно, чтобы безошибочно распознавать, какие фигуры нельзя нарисовать однимросчерком и какие можно, а также, с какой точки надо начинать вычерчивание.
Предлагаем начертить одним росчерком следующие фигуры. (рис 14)
2. Комбинаторные задачи.Несколько мальчиков встретились на вокзале, чтобы поехать за город в лес. При встрече все они поздоровались друг с другом за руку. Сколько мальчиков поехали за город, если всего было 10 рукопожатий?
Решение: Сделаем рисунок. Точки будут изображать мальчиков, а отрезки рукопожатия.
1) 2) 3) 4)
Рис. 15
Из рисунка видно, что на вокзале встретились 5 мальчиков.
3. Задача о нахождении кратчайшего пути в графе.Во многих задачах, особенно решаемых на ЭВМ, графы удобно описывать матрицами.Матрица – это прямоугольная таблица чисел.
a b c d
a 0 1 1 0
b 1 0 1 0
c 1 1 0 1
d 0 0 1 0
Рис. 17 Для хранения информации об узлах и связях графа можно использовать матрицу смежности. Единица на пересечении строки А и столбца В означает, что между узлами А и В есть связь.
ACDB128465 A B C D
A 12 8 0
B 12 5 6
C 8 5 4
D 0 6 4 Рис. 17 Если в примере с дорогами между населенными пунктами нас интересуют еще и расстояния между поселками, каждой связи нужно сопоставить число – километры между населенными пунктами. В графе это число называется весом, а сам граф - взвешенным. Хранить информацию о таком графе необходимо в весовой матрице – в таблицу необходимо записывать не 1 или 0 (есть связь или нет связи), а вес ребра. Если связи между двумя узлами нет, на бумаге можно оставить ячейку таблицы пустой.
Широко распространены задачи нахождения кратчайшего пути. В таких задачах задается граф (сеть дорог) и начальная вершина (пункт отправления). Каждому ребру можно присвоить вес - длина дороги.
а) Между населёнными пунктами A, B, C, D, E, F построены дороги,
протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
2349524765Определите длину кратчайшего пути между пунктами A и F (при условии, что передвигаться можно только по построенным дорогам).
1) 92) 103) 114) 12
Решение:Построим граф
АВСDEF21332474 АВСDEF21332474
Рис. 18 Рис. 19
Найдем все пути из А в F
1) АBEF2+7+2 = 11
2) ABCEF2+1+4+2 = 9
3) ABCDEF2+1+3+3+2 = 11
4) ACEF4+4+2 = 10
5) ACDEF4+3+3+2 = 12
Кратчайший путь ABCEF = 9Ответ: 1
б) Дана карта дорог между городами, где указана длина каждой дороги (данные не совпадают с настоящими). Найти: а) все кратчайшие пути из Санкт-Петербурга до Омска; б) все кратчайшие пути из Санкт-Петербургадо Магнитогорска.
Решение:
а) По данному графу можно рассмотреть все возможные варианты пути от Санкт-Петербурга до Омска, но таких вариантов получается очень много.

Рис. 20
200+50+30+90+90=460 или
150+100+30+90+90=460
Т. е., кратчайшее рас-стояние от Санкт-Петербур-га до Омска равно 460.
б) 200+50+30+90=370.
Получаем, что кратчайшее расстояние от Санкт-Петербурга до Магнитогорска равно 370.
Ориентированные графы.Существуют значительные классы практических задач, которые решить с помощью ранее рассмотренных типов графов невозможно.Так, например, схема дорог и площадей города изображается с помощью плоского графа. Но если нужно этой схемой воспользоваться с целью проезда по городу на автомашине, а движение на отдельных (или на всех) улицах одностороннее?
Граф, на рёбрах которого расставлены стрелки, называется ориентированным.
4. Задача на нахождение количества дорогНа рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К.
По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.Сколько существует различных путей из города А в город К?

Рис. 21
Решение 1:Перебираем все возможные пути из А в К, подсчитываем их количество
АБДИК, АБДК, АБВДК, АБВДИК, … и т.д.
Ответ: 13
Решение 2:
Используем метод динамического программирования, который позволяет получить решение, не прибегая к полному перебору вариантов.
Будем последовательно находить количество путей от А до Б, В, Г, и т.д.
131
Рис. 22
В Б можно попасть одним способом, из А
В В можно попасть тремя способами, из А из Б и из Г
В Г можно попасть одним способом, из А (рис.22)
131441
Рис. 23
В Д можно попасть из Б и их В, количество путей равно 1+3=4
В Е можно попасть из Г, количество путей равно 1
В Ж можно попасть из В и из Е, количество путей равно 3+1=4 (рис. 23)
131441134
Рис. 24
В И можно попасть из Д, количество путей равно 4
В К можно попасть из И, из Д, из Ж и из Е, количество путей равно 4+4+4+1 = 13 (рис. 24)
Ответ: 13
5. Задачи на определениевремени по расписаниюПутешественник пришел в 08:00 на автостанцию населенного пункта КАЛИНИНО и обнаружил следующее расписание автобусов. Определите самое ранее время, когда путешественник сможет оказаться в пункте РАКИТИНО согласно этому расписанию.
1) 12:252) 12:30
3) 12:354) 12:40
Решение:
Рассмотрим все возможные варианты маршрутов:
1) КАЛИНИНО → БУКОВОЕ
→9:10 → 10:15
БУКОВОЕ → РАКИТИНО
→11:40 → 12:40
2) КАЛИНИНО → РАКИТИНО
→10:15 → 12:35
3) КАЛИНИНО → КАМЫШИ
→10:20 → 11:15
КАМЫШИ → РАКИТИНО
→11:25 → 12:30
Выбираем наименьшее время 12:30
Ответ: 2
6. Задача на нахождение стоимости проезда по таблицамперевозок.
Таблица стоимости перевозок устроена следующим образом: числа, стоящие на пересечениях строк и столбцов таблиц, означают стоимость проезда между соответствующими соседними станциями. Если пересечение строки и столбца пусто, то станции не являются соседними. Укажите таблицу, для которой выполняется условие: «Минимальная стоимость проезда из А в B не больше 6». Стоимость проезда по маршруту складывается из стоимостей проезда между соответствующими соседними станциями.

Решение:1) для каждой таблицы нарисуем соответствующую ей схему дорог, обозначив стоимость перевозки рядом с линиями, соединяющими соседние станции:
Рис. 25
2) по схемам определяем кратчайшие маршруты для каждой таблицы:
1: A3 C4 BилиА3 С 2 Е 2 В, стоимость 7
2: A 3C 4Bили A 1E 2C 4B, стоимость 7
3: А 4 Е2 В, стоимость 6
4: A 1 D 4 C 2 E 1B, стоимость 8
3) условие «не больше 6» выполняется только для таблицы 3
8) таким образом, правильный ответ – 3.
7. Задача на нахождение минимального времени по данным расстояния и скорости.Грунтовая дорога проходит последовательно через населенные пункты А, B, С и D. Длина дороги между А и В равна 80 км, между В и С – 50 км, и между С и D – 10 км. Между А и С построили новое асфальтовое шоссе длиной 40 км. Оцените минимально возможное время движения велосипедиста из пункта А в пункт В, если его скорость по грунтовой дороге – 20 км/час, по шоссе – 40 км/час.
1) 1 час 2) 1,5 часа 3)3,5 часа 4) 4 часа
Решение:

Рис. 26 Рис. 27
1) нарисуем схему дорог, обозначив данные в виде дроби (расстояние в числителе, скорость движения по дороге – в знаменателе) (рис. 26)
2) разделив числитель на знаменатель, получим время движения по каждой дороге (рис. 27)
3) ехать из А в B можно напрямую, это займет 4 часа, иличерез пункт C, это займет 1 час по шоссе (из А в С) и 2,5 часа по грунтовой дороге (из В в С), всего 1 + 2,5 = 3,5 часа
4) таким образом, правильный ответ – 3.
Выводы:Знание теории графов дает возможность приобрести навыки сведения реальных ситуаций к графовым моделям, научиться строить простейшие алгоритмы. Какую бы область человеческой жизни мы ни затрагивали, в этой области обязательно находилась проблема или задача, решаемая с помощью графов. Метод графов прост и удобен, поэтому так распространен.
Графы – это замечательные математические объекты, с помощью, которых можно решать математические, логические задачи. Теория графов играет очень важную роль в жизни человека.
ЗаключениеВ результате работы над проектом мы узнали, что Леонард Эйлер был основоположником теории графов, решил задачи с применением теории графов. Мы сделали вывод, что теория графов находит применение в различных областях современной математики и информатики. Не приходится сомневаться в полезности ознакомления нас, учащихся, с основными понятиями теории графов. Решение многих математических задач упрощается, если удается использовать графы. Представление данных в виде графа придает им наглядность. Многие доказательства также упрощаются, приобретают убедительность, если воспользоваться графами. В особенности это относится к таким областям математики, как математическая логика, комбинаторика.
Таким образом, изучение этой темы имеет большое общеобразовательное, общекультурное и общематематическое значение. В повседневной жизни все большее применение находят графические иллюстрации, геометрические представления и другие приемы и методы наглядности. С этой целью изучение элементов теории графов полезно во внеклассной работе, так как в программу по математике эта тема не включена.
Приложение 1Использование графов в повседневной жизни:Строительство железных дорог, мостов, дорог.
Построение географических карт.
Блок – схемы алгоритмов. (рис. 33)
Схемы движения городского транспорта. (рис. 34)
-21209054610Рис. 33 Рис. 34
Самым впечатляющим примером графа в современном мире выступает Интернет. Его узлы - это адреса страничеки файлов, находящихся в сети, а ребра -гиперссылки, связывающие их вместе. Компьютеры, связанные вместе и образующиеВсемирную паутину, также можно рассматривать как граф.
Другая сложная система, появившаяся гораздо раньше Интернета - глобальная общемировая телефонная сеть - также является графом. Если мы будем рассматривать все телефонные аппараты (а вернее, номера, соответствующиеим) как узлы, а звонки, совершаемые с одного телефонного аппарата на другой, - как ребра, то получим сложную сеть, истинные размеры которой, наверное, не каждый сможет себе представить.
И глобальной телефонной сетью, и Интернетом очень сложно управлять,предсказать все возможные звонки и связи невозможно.Если вы делаете звонок из Москвы в Нью-Йорк, существует множествоспособов соединить вас с тем абонентом, звонят. Телефонные станции должны выбирать кратчайший (с точки зрения графа)путь, соединяющий эти две точки. То же самое и в Интернете: чтобы браузер на вашем компьютере мог загрузить страничку, физически находящуюся в Южно-Африканской Республике, данные должны пройти через некоторое количество серверов, то есть маршрут в Сети. Он будет автоматически выбираться серверами такимобразом, чтобы его длина была минимальной (опять-таки, с точки зренияграфа), а данные по возможности проходили через незагруженные сегментыСети. Из-за того, что нагрузка в разных участках Сети постоянно и случайным образом меняется, даже если вы загрузите с одного и того сайта страничку двараза подряд с интервалом в 1 секунду, она может прийти к вам двумя разными путями. Кроме того, что по Сети гуляют не странички в готовом виде, а пакеты с данными, и даже одна страничка может состоять из нескольких пакетов, значит, фрагменты одной страницы могут приходить в Интернете с одного компьютера на другойразными путями. Задача доставки пакетов данных из одного узла Сети (хоста)в другой называется задачей маршрутизации, и она отнюдь не является простой.
Предположим, путешественнику по автодорогам надо попасть из Петербурга в Берлин. Можно придумать несколько маршрутов, пролегающих по территории разных государств и различных по своей длине. Они будут удовлетворять разным условиям: проехать из одной точки в другую максимально быстро, побывать в какой-нибудь стране, или, наоборот, объехать ее, так как нам не удалось получить визу; останавливаться каждую ночь в каком-нибудь городском мотеле и т. д.
Задача нахождения оптимального пути между двумя географическими точками, удовлетворяющего определенным условиям, известна в теории графов как задача нахождения кратчайшего пути. В качестве узлов графа выступают перекрестки и развязки дорог, они совпадают с городами и другими населенными пунктами. Ребра - это дороги, соединяющие узлы.
-5080-376555Еще один интересный пример, связанный с графами, это задачасоставления календаря. Предположим, есть некая организация, в которой работают 500 человек.
Каждый из них встречается сосвоими коллегами в рамках различных мероприятий, каждый день, или раз в неделю, или раз в месяц. Составить общее расписание рабочихвстреч нам может помочь теория графов. Самый простой вариант - разбить рабочее время каждогосотрудника на определенные интервалы по 15 минут, и установитьмежду ними для каждого сотрудника ориентированные последовательныесвязи, в результате получатся вертикальные цепочки из узлов – интерваловрабочего времени. Если два сотрудника в определенное время встречаются,нужно установить горизонтальные связи между соответствующимиинтервалами времени - узлами. Сегодня эту утомительную работу выполняют компьютеры, однако совсем недавно расписания икалендари составлялись вручную.

Приложенные файлы

  • docx 9503662
    Размер файла: 819 kB Загрузок: 0

Добавить комментарий