close

Вход

Забыли?

вход по аккаунту

?

Графы

код для вставкиСкачать
Муниципальное казенное общеобразовательное учреждение средняя
общеобразовательная школа п.Речной Куменского района Кировской области
Исследовательская работа
«Применение графов к решению задач»
Выполнила ученица 10 класса
Гырдымова Мария Андреевна
Учитель Герасимова Надежда
Васильевна
2014г.
Оглавление:
1.Введение…………………………………………………………………3
2. Содержание…………………………………………………………….. 4
3.История графов………………………………………………………….4
4.Свойства и разновидности графов……………………………………. .5
5.Применение графов…………………………………………………… ..9
6.Заключение……………………………………………………………...20
Литература………………………………………………………………...21
2
1.Введение.
Теория графов – наука сравнительно молодая. Графы, о которых пойдет
речь, к аристократам былых времен никакого отношения не имеют. Эти
«графы» имеют корень греческого слова «графо», что значит «пишу». Тот
же корень в словах «график», «биография», «голография».
Однажды услышав о графах, я ими заинтересовалась. Я решила узнать,
как можно применить теорию графов на практике в жизни, и поделиться
этим с одноклассниками.
Графы — сети линий, соединяющих заданные точки, — широко
используются в разных разделах математики и в приложениях. В последнее
время теория графов стала простым, доступным и мощным средством решения
вопросов, относящихся к широкому кругу проблем, это проблемы
исследования автоматов, логических цепей, блок-схем программ, экономики и
статистики, химии и биологии, поэтому я рассматриваю теорию графов с
целью поиска рациональных способов решения этих задач.
Проблема: Неизвестны знания в области применении графов.
Объект исследования: графы.
Предмет исследования: свойства графов и их применение.
Гипотеза: я предполагаю, что графы используются во многих
областях науки.
Цель: изучить теорию графов с целью поиска рациональных способов
решения задач. Выяснить, в каких еще областях применяется теория графов.
Задачи:
1.
познакомиться с теорией графов;
2.
рассмотреть способы решения задач с помощью графов;
3.
показать применение теории графов в различных областях.
Актуальность: решение многих математических задач упрощается, если
удается использовать графы. Представление данных в виде графа придает им
наглядность и простоту. Теория графов в настоящее время является
интенсивно развивающимся разделом математики. Это объясняется тем, что в
виде графовых моделей описываются многие объекты и ситуации. Многие
математические
доказательства
также
упрощаются,
приобретают
убедительность, если пользоваться графами.
3
2. Содержание:
1. Введение.
2 . История графов.
3 . Свойства и разновидности графов.
4 Применение графов.
5 . Вывод.
3.История графов.
Родоначальником теории графов принято считать математика Леонарда
Эйлера(1707-1783). Он предложил изящное решение знаменитой задачи о 7
Кенигсбергских мостах в 1736 году, а также придумал общий метод решения
подобных задач.
Философ Иммануил Кант, гуляя по городу Кенигсбергу (сейчас этот
город называется Калининград), поставил задачу (1736), известную в
математике как задача о семи кенигсбергских мостах: можно ли пройти по
всем этим мостам и при этом вернуться в исходную точку так, чтобы по
каждому мосту пройти только один раз. Наш петербургский знаменитый
математик швейцарского происхождения Леонард Эйлер блестяще решил эту
задачу.
Причем, он не только решил эту конкретную задачу, но придумал общий
метод решения подобных задач. Эйлер поступил следующим образом: он
"сжал" сушу в точки, а мосты "вытянул" в линии. В задаче о семи
кенигсбергских мостах все четыре вершины соответствующего графа
нечетные, т.е. нельзя пройти по всем мостам один раз и закончить путь там,
где он был начат.
Задача о Кенигсбергских мостах и подобные ей задачи вместе с
совокупностью методов их исследования составляют очень важный в
практическом отношении раздел математики, называемый теорией графов.
Первая работа о графах принадлежала Л. Эйлеру и появилась в 1736 году. В
дальнейшем над графами работали Кениг (1774-1833), Гамильтон (1805-1865),
из современных математиков - К. Берж, О. Оре, А. Зыков.
4
4.Свойства и разновидности графов.
Граф - конечная совокупность вершин, некоторые из
которых соединены ребрами.
Объекты представляются как вершины, или узлы графа, а связи - как дуги,
или рёбра. Для разных областей применения виды графов могут различаться
направленностью, ограничениями на количество связей и дополнительными
данными о вершинах или рёбрах.
Элементы графа:
Гр
A
аф
B
Пе
C тл
я
Реб
ро
D
Верш
ина
Маршрут графа – последовательность чередующихся вершин и ребер.
Замкнутый маршрут (цикл) – маршрут, в котором начальная и конечная
вершины совпадают.
Простая цепь – маршрут, в котором все ребра и вершины различны.
5
Связный граф – это граф, в котором каждая вершина достижима из
любой другой.
Точки называются вершинами, или узлами графа, линии – ребрами
графа
A
cdeC
abB
G
1
Виды графов:
Граф называется:
* связным, если для любых вершин u, v есть путь из u в v.
* сильно связным или ориентировано связным, если он ориентированный,
и из любой вершины в любую другую имеется ориентированный путь.
* деревом, если он связный и не содержит простых циклов.
* полным, если любые его две (различные, если не допускаются петли)
вершины соединены ребром.
* двудольным, если его вершины можно разбить на два не пересекающихся
подмножества V1 и V2 так, что всякое ребро соединяет вершину из V1 с
вершиной из V2.
* k-дольным, если его вершины можно разбить на k не пересекающихся
подмножества V1, V2, ..., Vk так, что не будет рёбер, соединяющих вершины
одного и того же подмножества.
* полным двудольным, если каждая вершина одного подмножества
соединена ребром с каждой вершиной другого подмножества.
* планарным, если граф можно изобразить диаграммой на плоскости без
пересечений рёбер.
* взвешенным, если каждому ребру графа поставлено в соответствие
некоторое число, называемое весом ребра.
* хордальным, если граф не содержит индуцированных циклов с длиной
больше трех.
Степени вершин и подсчет числа ребер.
6
Количество рёбер, выходящих из вершины графа, называется
степенью вершины. Вершина графа, имеющая нечётную степень,
называется нечетной, а чётную степень – чётной.
Если степени всех вершин графа равны, то граф называется
однородным. Таким образом, любой полный граф — однородный.
Закономерности, присущие определенным графам.
Закономерность 1.
Степени вершин полного графа одинаковы, и каждая из них на 1
меньше числа вершин этого графа.
Закономерность 2.
Сумма степеней вершин графа число четное, равное удвоенному числу
ребер графа.
Эта закономерность справедлива не только для полного, но и для
любого графа.
ТЕОРЕМА.
Число нечетных вершин любого графа четно.
Эйлеровы графы.
Граф, который можно нарисовать, не отрывая карандаша от бумаги,
называется эйлеровым.
Такими графы названы в честь учёного Леонарда Эйлера.
7
Закономерность 3
Невозможно начертить граф с нечетным числом нечетных вершин.
Закономерность 4.
Если все вершины графа четные, то можно не отрывая карандаш от
бумаги («одним росчерком»), проводя по каждому ребру только один раз,
начертить этот граф. Движение можно начать с любой вершины и
закончить его в той же вершине.
Закономерность 5.
Граф, имеющий всего две нечетные вершины, можно начертить, не
отрывая карандаш от бумаги, при этом движение нужно начать с одной из
этих нечетных вершин и закончить во второй из них.
Закономерность 6.
Граф, имеющий более двух нечетных вершин, невозможно начертить
«одним росчерком».
Графы широко используются во многих областях науки и техники,
в частности:

Файловая система компьютера. Иерархия файлов и папок во
многих операционных системах имеет вид дерева, которое является частным
случаем графа;

Молекулы всех химических веществ можно изобразить в виде
графа, где атомы являются вершинами, а связи между ними – ребрами;

Карта автомобильных или любых других путей также является
графом, причем каждая дорога может иметь определенное значение "веса"
(например, плотность транспортного потока), тогда такой граф является
взвешенным;

Социальные сети также можно представить в виде графа, где
каждая человека или социальная группа является вершиной, а связи между
ними - ребрами;

Генеалогические деревья являются примером бинарных деревьев,
что также является частным случаем графа;

Турнирные таблицы спортивных чемпионатов также могут быть
изображены в виде графов;
8

В биологии и экологии графы также используются уже давно.
Примерами могут быть цепи питания, экосистемы, генетические
последовательности и карты таксономическая иерархия живых организмов и
т.п.;

В археологии и геологии графы используются в стратиграфии для
изучения геологических пластов;
Использование графов в повседневной жизни:
 Строительство
железных дорог, мостов, дорог.
 Построение географических карт.
 Блок – схемы ЭВМ.
 Сетевые графики строительства.
 Схемы движения городского транспорта.
 Схемы авиалиний.
 Карты звёздного неба.
 Составление генеалогического древа.
5.Применение графов
С помощью графов часто упрощается решение задач, сформулированных
в различных областях знаний
5.1 Анализ запутанных ситуаций
1)Боксёры с твёрдою походкой
Не моют пол зубною щёткой.
Кто моет пол зубною щёткой,
Тот наделён душою кроткой.
Кто пол мыть щёткой не желает,
Суровым нравом обладает.
Суровый нрав у тех бывает,
Кто книжек вовсе не читает.
Фосс враг и книжек и газет,
Ответь, боксёр он или нет?
• Для описания ситуации используем ряд утверждений и
используем граф.
Твёрдою походкой
Боксёр
Моет пол зубною щёткой
Не моет пол зубною щёткой
Имеет кроткую душу
Имеет суровый нрав
Не читает книг
9
2)Широкоплечие
Широкоплечие мужчины
Мужчины с узкими плечами
поют
молчат
Не отличаются терпеньем
Терпеливы
Чинит домики улиткам
Клей варят на эл.плитках
мужчины
Поют, садясь за руль машины.
Мужчины с узкими плечами,
Садясь за руль молчат как камень.
Те, кто за руль садятся с пеньем,
Не отличаются терпеньем.
Те кто в машине молчаливы,
Бывают очень терпеливы.
Терпенье тем дано с избытком.
Кто чинит домики улиткам.
Чтоб домик починить улитке,
Клей варят на электроплитке.
Фосс не выносит запах клея,
Он сразу падает, бледнея.
Прошу ответить на вопрос:
Широкоплеч ли мистер Фосс?
5.2 Смысловая структура фраз
• В искусственном интеллекте существует раздел, который называется
компьютерная лингвистика. Задача этой науки – научить компьютер
общаться с человеком на естественном языке.
• Смысл любой фразы зависит не только от слов её составляющих , но и
связей между словами.
• Для того, чтобы выяснить смысл фразы надо разобраться в её структуре.
А для этого используют графы.
10
11
Смысловая структура фраз
Подобные модели закладываются в компьютерную память и
используются для анализа текстов на естественных языках
Соседский
Какой-то
мальчик
друга
Кто-то
кулаком
Чем-то
Кого-то
Обидное слово
Что-то
«Соседский мальчик ударил кулаком друга за обидное
слово».
5.3.Графы в математике
В математике графы применяются для решения логических задач и
головоломок. Основой применения графов для решения логических задач
служит выявление и последовательное исключение возможностей, заданных в
условии. Это выявление логических возможностей часто может быть
истолковано с помощью построения и рассмотрения соответствующих
графов.
1) «Беседуют трое: Белокуров, Чернов, и Рыжов. Брюнет сказал
Белокурову: « Любопытно, что один из нас русый, другой - брюнет, а
третий - рыжий, но ни кого цвет волос не соответствует фамилии».
Какой цвет волос имеет каждый из беседующих?». Решение данной задачи
можно изобразить с помощью графа.
Белокуров
русый
Чернов
рыжий
Рыжов
брюнет
Т.О. Белокуров не русый и не брюнет, значит –рыжий, Чернов – русый,
Рыжов-брюнет
2)Мария работает в дневную смену.Сергей работает в вечернюю смену.
Борис работает в вечернюю смену Валентина работает в вечернюю
смену.Два служащих знают друг друга, если они работают в одну смену.
12
Определить:1) Знает ли Сергей Бориса 2) Кого знает Валентина 3)Кого
знает Мария?
Мария
Сергей
работает
дневная смена
работает
Борис
работает
Вечерняя смена
работает
Валентина
3) вычислить выражение, представленное в виде графа
5*(3+7)*(8-2) дерево будет иметь вид:
4) В таблице
представлено расстояние между населенными
пунктами в километрах. Определить кратчайшее расстояние между
пунктами A и E.
A
A
B
C
D
E
2
10
8
16
9
1
B
2
C
10
9
D
8
1
E
16
3
3
4
4
11
11
Представим таблицу в виде графа, наглядно видно кратчайшее
расстояние
13
28 9 1
1 3
1 4 1
0
6
1
5) А всегда ли можно так изобразить любой граф на плоскости,
чтобы его рёбра не пересекались? Впервые этот вопрос возник при решении
старой головоломки. Вот как её описывает Льюис Кэрролл.
Три человека жили в трех домиках, неподалеку от них находились три
колодца: один с водой, другой с маслом, а третий с повидлом, и ходили к ним
по тропинкам. Однажды эти люди перессорились и решили провести тропинки
от своих домов к колодцам так, чтобы эти тропинки не пересекались.
Первоначальный вариант, изображенный на рисунке, по этой причине их не
устраивал
На втором рисунке изображена очередная попытка продолжить тропинки,
на которых осталось непроверенных только одна тропинка. Но эта задача до сих
пор не решена.
6)Математическая задача, выполненная в виде блок-схемы ЭВМ
14
7) Дан кусок проволоки, длиной 120 см. Можно ли, не ломая проволоки,
изготовить каркас куба с ребром 10 см?
Если куб – граф, тогда он имеет более двух нечетных вершин (8). Значит,
невозможно изготовить такой каркас, не ломая проволоки.
8)Можно ли обвести карандашом, не отрывая его от бумаги и не проходя
по одной линии дважды, правильный пятиугольник с диагоналями?
15
Если пятиугольник – граф и все вершины его четные – то это выполнить можно.
9) Задача: Я задумал число. Если к нему прибавить 24, потом полученную
сумму умножить на 9, затем из произведения вычесть 76 и, наконец,
полученную разность разделить на 19, то получится число 23. Найти
задуманное число.
Видно, что решать задачу следует с конца, заменяя каждое действие на
обратное ему.
Получаем:
Ответ: 33.
10) Несколько мальчиков встретились на вокзале, чтобы поехать за город
в лес. При встрече все они поздоровались друг с другом за руку. Сколько
мальчиков поехали за город, если всего было 10 рукопожатий?
Сделаем рисунок. Точки будут изображать мальчиков, а отрезки рукопожатия.
16
1)
2)
3)
4)
Из рисунка видно, что на вокзале встретились 5 мальчиков.
11) В первом матче футболисты «Звездочки» забили в ворота противника
половину мячей, забитых ими во втором матче, и еще один мяч. Во
втором матче они забили вдвое меньше мячей, чем в третьем матче, и
еще один мяч. В третьем матче они забили вдвое меньше мячей, чем в
первом, и еще один мяч. Сколько всего мячей забили футболисты
«Звездочки» за три матча?
Из рисунка видно, что в каждой игре было забито одинаковое число мячей. В
каждой игре забито по 2 мяча.
Ответ: 6 мячей забито в 3-х играх.
5.4.Графы в повседневной жизни
1)Примерами графов могут служить схема метрополитена , схемы
дорог, планы выставок и т.д., т.е. схемы и планы.
17
2)Интернет - глобальная общемировая телефонная сеть - также является
графом. Если мы будем рассматривать все телефонные аппараты (а вернее,
номера, соответствующие
им) как узлы, а звонки, совершаемые с одного
телефонного аппарата на другой, - как ребра, то получим громадную, сложную
сеть, истинные размеры которой, наверное, не каждый сможет себе
представить.
3) Деревья
Двоичные деревья играют весьма важную роль в теории информации.
Двоичные кодовые деревья допускают интерпретацию в рамках теории
18
поиска. Каждой вершине при этом сопоставляется вопрос, ответить на
который можно либо "да", либо "нет".
Утвердительному и отрицательному ответу
соответствуют два ребра, выходящие из
вершины. "Опрос" завершается, когда удается
установить то, что требовалось. Таким образом,
если кому-то понадобится взять интервью у
различных людей, и ответ на очередной вопрос
будет зависеть от заранее неизвестного ответа
на предыдущий вопрос, то план такого
интервью можно представить в
виде двоичного дерева.
Дерево – это граф, в котором две
любые вершины соединены
ровно одним простым путём.
В дереве число вершин на одну
больше числа ребер.
Деревом называется любой
связный граф, не имеющий циклов.
Слово «дерево» в теории графов означает граф, в котором нет циклов, то есть
в котором нельзя из некоторой вершины пройти по нескольким различным
ребрам и вернуться в ту же вершину. Генеалогическое дерево будет деревом
и в смысле теории графов, если в этом семействе не было браков между
родственниками.
5.5. Графы и химия.
Еще А. Кэли рассмотрел задачу о возможных структурах насыщенных
(или предельных) углеводородов,
Все
атомы
углеводорода
19
четырехвалентны,
все
атомы
водорода одновалентны. Структурные
формулы простейших углеводородов показаны на рисунке.
H
I
H- C -H
I
H
(метан)
Молекула каждого предельного углеводорода представляет собой дерево.
Если удалить все атомы водорода, то оставшиеся атомы углеводорода также
будут образовывать дерево, каждая вершина которого имеет степень не выше 4.
Следовательно, число возможных структур
предельных углеводородов, т. е.
число гомологов данного вещества, равно числу деревьев с вершинами степени
не больше четырех.
Таким образом, подсчет числа гомологов предельных углеводородов также
приводит к задаче о перечислении деревьев определенного типа. Эту задачу и ее
обобщения рассмотрел Д. Пойа.
5.6.Графы и биология
1) Деревья играют большую роль в биологической теории ветвящихся
процессов. Я
рассмотрю одну
разновидность ветвящихся процессов
–
размножение бактерий. Предположим, что через определенный промежуток
20
времени каждая бактерия либо делится на две новые, либо погибает. Тогда
для потомства одной бактерии мы получим двоичное дерево.
Вопрос: в скольких случаях n-е поколение одной бактерии насчитывает
ровно
k
соотношение,
потомков?
Рекуррентное
обозначающее
число
необходимых случаев, известно в биологии
под названием процесса Гальтона-Ватсона.
Его можно рассматривать
как частный
случай многих общих формул.
2)Возможность переливания крови
разных групп отражены с помощью
графа. Глядя на который легко понять,
какие существуют варианты по переливанию крови.
5.7.Графы и физика
Еще недавно одной из наиболее сложных и утомительных задач для
радиолюбителей было конструирование печатных схем.
Печатной схемой называют пластинку
из
какого-либо
диэлектрика
(изолирующего материала), на которой в виде металлических полосок
21
вытравлены дорожки. Пересекаться дорожки могут только в определенных
точках, куда устанавливаются необходимые элементы (диоды, триоды, резисторы
и другие), их пересечение в других местах вызовет замыкание электрической
цепи.
6.Заключение
Чтобы найти ответ на интересующую меня вопрос, мне пришлось
познакомиться с новым разделом математики «Теорией графов», который не
изучается в школьном курсе.
Я узнала, что графы - это математические объекты, с помощью которых
можно решать математические, экономические и логические задачи,
различные головоломки. Задачи, поставленные перед собой, я выполнила:
1. познакомилась с историей теории графов;
2. изучила основные понятия теории графов и виды графов;
3. рассмотрела наиболее интересные задачи и их решения с помощью
графов;
4. познакомилась с применением метода графов в практической
деятельности человека.
Литература:
1. Энциклопедический словарь юного математика/ сост.А.П.СавинМ.:Педагогика.1989
2. М.Гарднер «Математические досуги» М.:Мир,1972
3. В.А.Носов Комбинаторика и теория графов, МГТУ, 1999
4. Уилсон Р. «Ведение в теорию графов», М, 1977г
5. Фарков А.В. «Математические олимпиады в школе», М, 2004
6. Вадченко Н.Л. «600 задач на сообразительность», М, 1997
22
7. Горячев А.В. «Информатика в играх и задачах», М, 2003
23
Автор
gerasimnad203
Документ
Категория
Математика
Просмотров
18
Размер файла
1 033 Кб
Теги
граф
1/--страниц
Пожаловаться на содержимое документа