Научное общество учащихся
«Поиск»
40 Открытая областная научная конференция учащихся.
Секция математики
.
Научная работа по теме:
«Графы» в моей родословной
МОУ «Куломзинская СОШ»
Руководитель:
Лысенко Ольга Григорьевна
учитель математики
МОУ «Куломзинская СОШ»
Омск - 2008г.
II. ОСНОВНАЯ ЧАСТЬ
1.Понятие о графах
2.Свойства графов
3.Применение графов
III.Практическая часть
IV.Заключение
V.Литература
VI.Приложение
С О Д Е Р Ж А Н И Е
Введение………………………………………………………………..…….3
П.1.1. Актуальность и новизна……………………………………………..4
П.1.2.Цели и задачи…………………………………………………………4
Глава I.Теоретическаячасть …...………………………………….……….5
П.2.1.Понятие о графах……………………………………………………..5
Глава II. Практическая часть……………………………………………..11
П.2.1. «Графы» в моей родословной……………………………………..11
П.2.2.Решение логических задач методом графа………………………..11
Заключение…..……………………………………………………………...17
Литература……..……………………………………………………………..18
Приложения…………………………………………………………………..19
Введение
1.Актуальность и новизна
Теория графов находит применение в различных областях современной математики и ее многочисленных приложениях, в особенности это относится к экономике, технике, к управлению. Теория графов – важный раздел дискретной математики, практическая роль которой возросла за счёт развития различных АСУ и вычислительной техники дискретного действия, в теоретическом плане помимо связей с комбинаторикой и геометрией наметились сдвиги на стыке теории графов с алгеброй, математической логикой.
Исторически сложилось так, что теория графов зародилась в ходе решения головоломок двести с лишним лет назад. Очень долго она находилась в стороне от главных направлений исследований ученых. Толчок к развитию теория графов получила на рубеже XIX и XX столетий, когда резко возросло число работ в области топографии и комбинаторики, с которыми ее связывают самые тесные узы родства. Наиболее раннее упоминание о графах встречается в работе Л. Эйлера (1736г). В середине XIX века инженер-электрик Г. Кирхгоф разработал теорию деревьев для исследования электрических цепей, а математик А. Кэли в связи с описанием строения углеводородов решил перечислительные задачи для трех типов деревьев. Окончательно как математическая дисциплина теория графов оформилась в 1936г. после выхода монографии Д. Кёнига «Теория конечных и бесконечных графов».
В последнее время графы и связанные с ними методы исследований органически пронизывают на разных уровнях едва ли не всю современную математику. Теория графов находит массу приложений как в различных областях математики: алгебре, геометрии, топологии, комбинаторике, теории кодирования, исследовании операций, так и в физике, химии, лингвистике, экономике, психологии и других науках.
Решение многих математических задач упрощается, если удается использовать графы. Представление данных в виде графа придает им наглядность и простоту.
Новизной данной работы является доказательство эффективности метода графа при решении логических задач.
Главной целью школьного математического образования является развитие умственных способностей учеников. Нужен переход от информационно- объяснительной технологии к деятельно-развивающей, направленной на развитие личностных качеств каждого школьника. Важными должны стать не только усвоенные знания, но и сами способы усвоения и переработки учебной информации, развитие познавательной деятельности и творческого потенциала ученика. Большинство школьников свои приобретенные знания по математике вряд ли будут использовать в повседневной жизни, хотя многие из них закончат технические ВУЗы. Человек быстро забывает те знания, которыми постоянно не пользуется, но с ним навсегда остается логическое развитие. Именно этой актуальной теме развития личности учащегося посвящается моя работа.
Объектом исследования является процесс обучения учащихся методу «графа».
Гипотеза : по нашему предположению решение учащимися логических задач методом графа могут способствовать формированию и развитию логического мышления.
Исходя из гипотезы выдвинуты следующие цели и задачи исследования.
2. Цель и задачи.
Цель
: использовать метод графа для решения логических задач, тем самым способствовать развитию логического мышления, рассмотреть решение задач с использованием понятия «Граф», проверить выполнение «Графов» на родословных.
Задачи:
1)Изучить научно- популярную литературу по данному вопросу.
2)Исследовать выполнение «Графов» для выяснения родственных отношений.
3)Проанализировать результаты проведенных экспериментов.
4)Изучение метода «графа», как метода решения логических задач.
Гл.I. Теоретическая часть
П.2.1. Понятие о графах
Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. Математические графы с дворянским титулом «граф» связывает общее происхождение от латинского слова « графио » - пишу. Типичными графами являются схемы авиалиний, которые часто вывешивается в аэропортах, схемы метро, а на географических картах – изображение железных дорог (рис. 1). Выбранные точки графа называются его вершинами, а соединяющие их линии – ребрами.
Использует графы и дворянство. На рисунке 2 приведена часть генеалогического дерева знаменитого дворянского рода. Здесь его вершины – члены этого рода, а связывающие их отрезки – отношения родственности, ведущие от родителей к детям.
Слово «дерево» в теории графов означает граф, в котором нет циклов, то есть в котором нельзя из некоторой вершины пройти по нескольким различным ребрам и вернуться в ту же вершину. Генеалогическое дерево будет деревом и в смысле теории графов, если в этом семействе не было браков между родственниками.
Не трудно понять, что граф – дерево всегда можно изобразить так, чтобы его ребра не пересекались. Тем же свойством обладают графы, образованные вершинами и ребрами выпуклых многогранников. На рисунке 3 приведены графы, соответствующие пяти правильным многогранникам. В графе соответствующем тетраэдру, все четыре вершины попарно соединены ребрами.
Рассмотрим граф с пятью вершинами, попарно соединенными друг с другом (рис. 4). Здесь ребра графа пересекаются. Невозможно его изобразить так, чтобы пересечений не было, как невозможно выполнить намерения трех человек, описанных Льюсом Кэрроллом. Они жили в трех домиках, неподалеку от них находились три колодца: один с водой, другой с маслом, а третий с повидлом, и ходили к ним по тропинкам, изображенным на рисунке 5. Однажды эти люди перессорились и решили провести тропинки от своих домов к колодцам так, чтобы эти тропинки не пересекались. На рисунке 6 изображена очередная попытка проложить такие тропы.
Графы, изображенные на рисунках 4 и 5, как, оказалось, играют решающую роль при определении для каждого графа – является ли он плоским, то есть, может ли он быть изображен на плоскости без пересечения его ребер. Польский математик Г. Куратовский и академик
Л.С.Понтрягин независимо друг от друга доказали, что если граф не является плоским, то в нем «сидит» хотя бы один из графов, изображенных на рисунках 4 и 5, то есть «полный пятивершинник» или граф «домики – колодцы».
Графами являются блок – схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, - работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего.
Если на ребрах графа нанесены стрелочки, указывающие направление ребер, то такой граф называют направленным.
Стрелка от одной работы к другой на графе, изображенном на рис. 7, означает последовательность выполнения работ. Нельзя начинать монтаж стен, не закончив строить фундамент, чтобы приступить к отделке, нужно иметь на этажах воду и т. д.
рис.7.
Около вершин графа указаны числа – продолжительность в днях соответствующей работы. Теперь мы можем узнать наименьшую возможную продолжительность строительства. Для этого из всех путей по графу в направлении стрелок нужно выбрать путь, у которого сумма чисел при вершинах наибольшая. Он называется критическим путем (на рис. 7 он выделен коричневым цветом). В нашем случае получаем 170 дней. А если сократить время прокладки электросети с 40 до 10 дней, то и время строительства тоже сократится на 30 дней? Нет, в этом случае критический путь станет проходить не через эту вершину, а через вершины, соответствующие строительству котлована, укладке фундамента и т. д. И общее время строительства составит 160 дней, т. е. срок сократиться лишь на 10 дней.
На рис.8 изображена схема дорог между селами М, А, Б, В, Г.
Здесь каждые две вершины соединены между собой ребром. Такой граф называется полным. Числа на рисунке указывают расстояния между селами по этим дорогам. Пусть в селе М находится почта и почтальон должен развезти письма по остальным четырем селам. Существует много различных маршрутов поездки. Как из них выбрать наикратчайший? Проще всего проанализировать все варианты. Сделать это поможет новый граф (внизу), на котором легко увидеть возможные маршруты. Вершина М вверху – начало маршрутов. Из нее можно начать движение четырьмя различными способами: в А, в Б, в В, в Г. После посещения одного из сел остается три возможности продолжения маршрута, потом две, потом дорога в последнее село и вновь в М. Всего 4 ×3× 2× 1 = 24 способа.
Расставим вдоль ребер графа цифры, обозначающие расстояния между селами, а в конце каждого маршрута напишем сумму этих расстояний по маршруту. Из полученных 24 чисел наименьшими являются два числа по 28км, соответствующие маршрутам М-В-Б-А-Г-М и М-Г-А-Б-В-М. Это один и тот же путь, но пройденный в разных направлениях. Заметим, что граф на рис. 8 тоже можно сделать направленным, указав направление сверху вниз на каждом из ребер, что соответствовало бы направлению движения почтальона. Подобные задачи часто возникают при нахождении лучших вариантов развозки товаров по магазинам, стройматериалов по стройкам.
Графы часто используют для решения логических проблем, связанных с перебором вариантов. Для примера рассмотрим такую задачу. В ведре 8 л воды, и имеется две кастрюли емкостью 5 и 3 л. требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4 л, т. е. разлить воду поровну в ведро и большую кастрюлю. Решение: Ситуацию в каждый момент можно описать тремя числами, где А-количество литров воды в ведре, Б - в большой кастрюле, В - в меньшей. В начальный момент ситуация описывалась тройкой чисел (8, 0, 0), от нее мы можем перейти в одну из двух ситуаций: (3, 5, 0), если наполним водой большую кастрюлю, или (5, 0, 3), если наполним меньшую кастрюлю. В результате получаем два решения: одно в 7 ходов, другое в 8 ходов.
Подобным образом можно составить граф любой позиционной игры: шахмат, шашек, «крестиков – ноликов», где позиции станут вершинами, а направленные отрезки между ними будут означать, что одним ходом можно перейти от одной позиции к другой, по направлению стрелки. Однако для шахмат и шашек такой граф будет очень большим, поскольку различные позиции в этих играх исчисляются миллионами. А вот для игры «крестики – нолики» на доске 3×3 соответствующий граф нарисовать не так уж трудно, хотя и он будет содержать несколько десятков (но не миллионов) вершин. В терминах графов легко формулируется и решается задача о назначении на должности. А именно: если имеется несколько вакантных должностей и группа лиц, желающих их занять, причем каждый из претендентов имеет квалификацию для нескольких должностей, то при каких условиях каждый из претендентов сможет получить работу по одной из своих специальностей?
Свойства графов не зависят от того, соединены вершины отрезками или кривыми линиями. Это дает возможность изучения их свойств с помощью одной из молодых наук – топологии, хотя сами задачи теории графов являются типичными задачами комбинаторики.
Гл.II. Практическая часть.
П.2.1. «Графы» в моей родословной.
Методы работы:
Сравнение и анализ результатов эксперимента.
Методика работы:
Для проведения исследований были выбраны:
А) Родословная моей семьи, архивы данных, свидетельства о рождении.
Б) Родословная князей Голицыных, архивы данных.
Я провела исследование, результаты исследования поместила в схемы и проанализировала их.
Методика 1.
Цель: проверить выполнение ’’Графов” на своей родословной.
Результаты: схема 1(см. приложение 1).
Методика 2.
Цель: проверить выполнение ’’Графов’’ на родословной князей Голицыных.
Результат: схема 2 (см. приложение 2).
Вывод: я заметила, что родословная – типичный граф.
П. 2.2. Решение логических задач методом графа
В течение всех лет обучения в школе мы много решаем разнообразных задач, в том числе и логических: задачи занимательного характера, головоломки, анаграммы, ребусы и т.п. Чтобы успешно решать задачи такого вида, надо уметь выделять их общие признаки, подмечать закономерности, выдвигать гипотезы, проверять их, строить цепочки рассуждений, делать выводы. Логические задачи от обычных отличаются тем, что не требуют вычислений, а решаются с помощью рассуждений. Можно сказать, что логическая задача – это особая информация, которую не только нужно обработать в соответствии с заданным условием, но и хочется это сделать. Логика помогает усваивать знания осознанно, с пониманием, т.е. не формально; создаёт возможность лучшего взаимопонимания. Логика – это искусство рассуждать, умение делать правильные выводы. Это не всегда легко, потому, что очень часто необходимая информация «замаскирована», представлена неявно, и надо уметь её извлечь. Как известно, видение рождает мышление. Возникает проблема: как установить логические связи между разрозненными фактами и как оформить в виде единой целой. Видеть ход доказательства и решения задач позволяет метод граф - схем, который делает доказательство более наглядным и позволяет кратко и точно изложить доказательства теорем и решения задач.
Пример 1.1 . Красный, синий, желтый и зеленый карандаши лежат в четырех коробках по одному. Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке, а красный не лежит в желтой. В какой коробке лежит каждый карандаш?
Решение.
Обозначим точками карандаши и коробки. Сплошная линия будет обозначать, что карандаш лежит в соответствующей коробке, а пунктирная, что не лежит. Тогда с учетом задачи имеем G1 (рис. 1).
Рис.1
Далее достраиваем граф по следующему правилу: поскольку в коробке может лежать ровно один карандаш, то из каждой точки должны выходить одна сплошная линия и три пунктирные. Получается граф G2 , дающий решение задачи.
Пример 1.2. Беседуют трое друзей: Белокуров, Чернов и Рыжов. Брюнет сказал Белокурову: «Любопытно, что один из нас белокурый, другой брюнет, третий рыжий, но ни у кого цвет волос не соответствует фамилии». Какой цвет волос имеет каждый из друзей?
Решение. Построим граф отношения, заданного в условии задачи. Для этого, прежде всего, выделим множество фамилий М и множество цветов волос К, элементы которых будем обозначать точками. Точки множества М назовем буквами Б, Ч, Р (Белокуров, Чернов и Рыжов); точки второго множества – б, бр, р (белокурый, брюнет, рыжий). Если точке из одного множества соответствует точка из другого, мы их соединим сплошной линией, а если не соответствует – штриховой. Условие задачи указывает лишь на несоответствия, поэтому, вначале должен возникнуть граф, изображенный на рисунке 2.
Рис.2
Принцип решения задачи прост. Если какая-то точка оказывается соединенной с двумя точками другого множества штриховыми линиями, то с его третьей точкой ее необходимо соединить сплошной линией. Поэтому граф на рисунке 2 дополняется сплошными линиями, соединяющими точки Б и р , Р и бр (рис. 3).
Рис.3
Далее остается соединить сплошной линией точку Ч
и точку б
, так как точка Ч
соединена с точкой бр
штриховой линией, а точка р
уже «занята» (рис. 4).
Рис. 4
В следующей задаче применение графов помогает обнаружить наличие двух решений.
Пример 1.3. Маша, Лида, Женя и Катя умеют играть на разных инструментах (виолончели, рояле, гитаре и скрипке), но каждая только на одном. Они же владеют разными иностранными языками (английским, французским, немецким и испанским), но каждая только одним. Известно, что:
1. девушка, которая играет на гитаре, говорит по-испански;
2. Лида не играет ни на скрипке, ни на виолончели и не знает английского языка;
3. Маша не играет ни на скрипке, ни на виолончели и не знает английского языка;
4. девушка, которая говорит по-немецки, не играет на виолончели;
5. Женя знает французский язык, но не играет на скрипке.
Кто на каком инструменте играет и какой иностранный язык знает?
Решение. Условию задачи соответствует граф, изображенный на рисунке 5.
Рис. 5
Рис. 6
Тем самым образуются два «сплошных» треугольника ЖВФ и КСА. Проводим еще сплошной отрезок РН. Теперь убеждаемся, что условия задачи не обеспечивают однозначности выбора третьей точки для каждой из пар РН и ГИ. Возможны следующие варианты «сплошных» треугольников: МГИ и ЛРН или ЛГИ и МРН. Таким образом, задача имеет два решения.
В некоторых случаях решение комбинаторных задач может быть затруднено. Облегчить процесс нахождения можно, научившись пользоваться такими средствами организации перебора как таблицы и графы. Они позволяют расчленить ход рассуждений, четко провести перебор, не упустив каких-либо возможностей.
Сначала как наиболее простым средством организации перебора нужно познакомится с таблицами.
Для примера рассмотрим такую задачу:
Имеются два сосуда вместимостью 3л и 5л. Как с помощью этих сосудов налить из водопроводного крана 4л воды?
Начнем с конца. Как в результате может получиться 4л? – Из 5-литрового сосуда отлить 1л. Как это сделать? – Надо в 3-литровом сосуде иметь ровно 2л. Как их получить? – Из 5-литрового сосуда отлить 3 литра. Теперь запишем решение задачи сначала в виде таблицы.
Поиск решения можно начать с действия 3+1, что привело бы к решению, записанному в следующей таблице.
Из чисел 3 и 5 можно составить выражения, имеющие значение 4:
5-3+5-3=4 и 3+3-5+3=4
Несложно убедиться, что полученные выражения соответствуют найденным выше решениям.
Второе средство организации при решении комбинаторных задач, которое можно использовать – графы.
Приведу пример решения с применением граф - дерева для решения комбинаторной задачи.
Например, требуется решить задачу: «Однажды встретились пятеро друзей. Каждый здороваясь, пожал каждому руку. Сколько рукопожатий было сделано».
Сначала выясняется, как нужно обозначить каждого человека. Рассматривая разные предложения, приходят к тому, что быстрее и удобнее изображать людей точками. Точки нужно расположить примерно по кругу, нарисовать их цветным карандашом, чтобы записи были понятными и наглядными. От двух точек навстречу друг к другу проводят черточки – «руки», которые встречаясь образуют одну линию. Так приходят к символическому изображению рукопожатия. Сначала составляются все рукопожатия одного человека (точка соединяется линиями со всеми остальными). Потом переходят к другому человеку. Проведенные лини помогают увидеть, с кем он уже поздоровался, а с кем – нет. Составляются недостающие рукопожатия (эти линии лучше проводить другим цветом, так как потом лучше будет подсчитать общее число рукопожатий). И так действуют до тех пор, пока все не поздороваются друг с другом. По получившему графу подсчитать число рукопожатий (их всего 10).
Следующая задача :
«Сколько двухзначных чисел можно составить, используя цифры 1,2,3,4?».
Решение.
Число 12: надо показать, что начинает с цифры 1, а оканчивается цифрой 2. петля появляется при обозначении, например, числа 11: стрелка должна начинаться и заканчиваться на одной и той же цифре. Открыв для себя первых задачах эти условные обозначения (точки, лини, стрелки, петли), я стала применять их при решении различных задач, составляя графы того или иного вида (рис 2).
ответ:16 чисел.
Приведу некоторые примеры:
1
.В финал турнира по шашкам вышли два российских игрока, два немецких и два американских. Сколько партий будет в финале, если каждый играет с каждым по одному разу и представители одной страны между собой не играют? (рис.3.).
н
Н
В финале будет сыграно 4×6 = 24партии.
2.В вазе лежали конфеты четырех сортов. Каждый ребенок взял две конфеты. И у всех оказались отличающие наборы конфет. Сколько могло быть детей? (граф на рис.4).
Из данного графа становится понятно, что возможно 6 отличающихся наборов конфет, а следовательно, детей могло быть 6.
С их помощью можно обеспечивать учеников новыми знаниями, которые облегчат ему в дальнейшем изучение информатики; повышать логическое и умственное развитие школьников; приучать их к самостоятельной работе; развивать их воображение и повышать культуру общения.
При решении комбинаторных задач сохраняется тесная связь мышления с практическими действиями, обеспечивается постепенный переход действиям в уме, способствует развитию качества мышления, как вариативность.
ЗАКЛЮЧЕНИЕ
Выполняя эту работу, я изучила один из интереснейших вопросов теории графов, я рассмотрела математические графы, области их применения, решила несколько задач с помощью графов. Научилась использовать «графы» для выяснения родственных отношений. Изучила метод «графов», как один из методов решения логических задач.
Теория графов не изучается в школьном курсе, но с задачами по дискретной математике приходится сталкиваться довольно часто на различных математических олимпиадах и конкурсах. Графы достаточно широко применяются в математике, технике, экономике, управлении. Знание основ теории графов необходимо в различных областях, связанных с управлением производством, бизнесом (например, сетевой график строительства, графики доставки почты), и познакомившись с элементами теории графов, я надеюсь, что смогу успешно решать не только олимпиадные задачи.
В дальнейшем я собираюсь продолжить изучение теории графов, потому что этот раздел математики показался мне интересным и полезным. Кроме того, работая над исследовательской работой, я освоила работу на компьютере в текстовом редакторе Word и Рower Point. Я считаю, что задачи исследовательской работы выполнила.
Литература.
Приложения.
Приложение 1.
Лобурец Виктория Владимировна 1994 гр.
Лобурец В. Н
1962
.
Орловская Л. В.
Третья городская научная
конференция учащихся
Информатика и математика
Круги Эйлера и теория графов в решении задач
школьной математики и информатики
Валиев Айрат
Муниципальное общеобразовательное учреждение
«Средняя общеобразовательная школа №10 с углубленным изучением
отдельных предметов», 10 Б класс, г. Нижнекамск
Научные руководители:
Халилова Нафисе Зиннятулловна, учитель математики
Учитель информатики
г. Набережные Челны
Введение. 3
Глава 1. Круги Эйлера. 4
1.1. Теоретические основы о кругах Эйлера. 4
1.2. Решение задач, применяя круги Эйлера. 9
Глава 2.О графах 13
2.1.Теория графов. 13
2.2. Решение задач, используя графы. 19
Заключение. 22
Список литературы. 22
Введение
«Всё наше достоинство заключено в мысли.
Не пространство, не время, которых мы не можем заполнить,
возвышает нас, а именно она, наша мысль.
Будем же учиться хорошо мыслить.»
Б. Паскаль,
Актуальность. Основной задачей школы является не подача детям большого объёма знаний, а обучение учащихся самим добывать знания, умению перерабатывать эти знания и применять их в каждодневной жизни. Поставленные задачи может решить ученик, обладающий не только умением хорошо и много работать, но и ученик с развитым логическим мышлением. В связи с этим во многие школьные предметы вложены различного типа задачи, которые и развивают у детей логическое мышление. Решая эти задачи, мы применяем различные приёмы решения. Одни из приёмов решения – это использование кругов Эйлера и граф.
Цель исследования : изучение материала, применяемого на уроках математики и информатики, где используются круги Эйлера и теория графов, как один из приемов решения задач.
Задачи исследования :
1. Изучить теоретические основы понятий: «Круги Эйлера», «Графы».
2. Решить задачи школьного курса вышеназванными методами.
3. Составить подборку материала для использования учениками и учителями на уроках математики и информатики.
Гипотеза исследования: применение кругов Эйлера и графов повышают наглядность при решении задач.
Предмет исследования: понятия: «Круги Эйлера», «Графы», задачи школьного курса математики и информатики.
Глава 1. Круги Эйлера.
Эйлеровы круги (круги Эйлера) - принятый в логике способ моделирования, наглядного изображения отношений между объемами понятий с помощью кругов, предложенный знаменитым математиком Л. Эйлером (1707–1783).
Обозначение отношений между объемами понятий посредством кругов было применено еще представителем афинской неоплатоновской школы - Филопоном (VI в.), написавшим комментарии на «Первую Аналитику» Аристотеля.
Условно принято, что круг наглядно изображает объем одного какого-нибудь понятия. Объем же понятия отображает совокупность предметов того или иного класса предметов. Поэтому каждый предмет класса предметов можно изобразить посредством точки, помещенной внутри круга, как это показано на рисунке:
Группа предметов, составляющая вид данного класса предметов, изображается в виде меньшего круга, нарисованного внутри большего круга, как это сделано на рисунке.
https://pandia.ru/text/78/128/images/image003_74.gif" alt="пересекающиеся классы" width="200" height="100 id=">
Такое именно отношение существует между объемом понятий «учащийся» и «комсомолец». Некоторые (но не все) учащиеся являются комсомольцами; некоторые (но не все) комсомольцы являются учащимися. Незаштрихованная часть круга А отображает ту часть объема понятия «учащийся», которая не совпадает с объемом понятия «комсомолец»; незаштрихованная часть круга B отображает ту часть объема понятия «комсомолец», которая не совпадает с объемом понятия «учащийся». 3аштрихованиая часть, являющаяся общей для обоих кругов, обозначает учащихся, являющихся комсомольцами, и комсомольцев, являющихся учащимися.
Когда же ни один предмет, отображенный в объеме понятия A, не может одновременно отображаться в объеме понятия B, то в таком случае отношение между объемами понятий изображается посредством двух кругов, нарисованных один вне другого. Ни одна точка, лежащая на поверхности одного круга, не может оказаться на поверхности другого круга.
https://pandia.ru/text/78/128/images/image005_53.gif" alt="понятия с одинаковыми объемами - совпадающие круги" width="200" height="100 id=">
Такое отношение существует, например, между понятиями «родоначальник английского материализма» и «автор „Нового Органона“». Объемы этих понятий одинаковы, в них отобразилось одно и то же историческое лицо - английский философ Ф. Бэкон.
Нередко бывает и так: одному понятию (родовому) подчиняется сразу несколько видовых понятий, которые в таком случае называются соподчиненными. Отношение между такими понятиями изображается наглядно посредством одного большого круга и нескольких кругов меньшего размера, которые нарисованы на поверхности большего круга:
https://pandia.ru/text/78/128/images/image007_46.gif" alt="противоположные понятия" width="200" height="100 id=">
При этом видно, что между противоположными понятиями возможно третье, среднее, так как они не исчерпывают полностью объема родового понятия. Такое именно отношение существует между понятиями «легкий» и «тяжелый». Они исключают друг друга. Нельзя об одном и том же предмете, взятом в одно и то же время и в одном и том же отношении, сказать, что он и легкий, и тяжелый. Но между данными понятиями есть среднее, третье: предметы бывают не только легкого и тяжелого веса, но также и среднего веса.
Когда же между понятиями существует противоречащее отношение, тогда отношение между объемами понятий изображается иначе: круг делится на две части так: А - родовое понятие, B и не-B (обозначается как B) - противоречащие понятия. Противоречащие понятия, исключают друг друга и входят в один и тот же род, что можно выразить такой схемой:
https://pandia.ru/text/78/128/images/image009_38.gif" alt="субъект и предикат определения" width="200" height="100 id=">
Иначе выглядит схема отношения между объемами субъекта и предиката в общеутвердительном суждении, не являющемся определением понятия. В таком суждении объем предиката больше объема субъекта, объем субъекта целиком входит в объем предиката. Поэтому отношение между ними изображается посредством большого и малого кругов, как показано на рисунке:
Школьные библиотеки" href="/text/category/shkolmznie_biblioteki/" rel="bookmark">школьной библиотеке , 20 - в районной. Сколько из пятиклассников:
а) не являются читателями школьной библиотеки;
б) не являются читателями районной библиотеки;
в) являются читателями только школьной библиотеки;
г) являются читателями только районной библиотеки;
д) являются читателями обеих библиотек?
3. Каждый ученик в классе изучает либо английский, либо французский язык , либо оба этих языка. Английский язык изучают 25 человек, французский - 27 человек, а тот и другой -18 человек. Сколько всего учеников в классе?
4. На листе бумаги начертили круг площадью 78 см2 и квадрат площадью 55 см2. Площадь пересечения круга и квадрата равна 30 см2. Не занятая кругом и квадратом часть листа имеет площадь 150 см2. Найдите площадь листа.
5. В детском саду 52 ребенка. Каждый из них любит либо пирожное, либо мороженое, либо и то, и другое. Половина детей любит пирожное, а 20 человек - пирожное и мороженое. Сколько детей любит мороженое?
6. В ученической производственной бригаде 86 старшеклассников. 8 из них не умеют работать ни на тракторе, ни на комбайне. 54 ученика хорошо овладели трактором, 62 - комбайном. Сколько человек из этой бригады могут работать и на тракторе, и на комбайне?
7. В классе 36 учеников. Многие из них посещают кружки: физический (14 человек), математический (18 человек), химический (10 человек). Кроме того, известно, что 2 человека посещают все три кружка; из тех, кто посещает два кружка, 8 человек занимаются в математическом и физическом кружках, 5 - в математическом и химическом, 3 - в физическом и химическом. Сколько человек не посещают никаких кружков?
8. 100 шестиклассников нашей школы участвовали в опросе, в ходе которого выяснялось, какие компьютерные игры им нравятся больше: симуляторы, квесты или стратегии. В результате 20 опрошенных назвали симуляторы, 28 - квесты, 12 - стратегии. Выяснилось, что 13 школьников отдают одинаковое предпочтение симуляторам и квестам, 6 учеников - симуляторам и стратегиям, 4 ученика - квестам и стратегиям, а 9 ребят совершенно равнодушны к названным компьютерным играм. Некоторые из школьников ответили, что одинаково увлекаются и симуляторами, и квестами, и стратегиями. Сколько таких ребят?
Ответы
https://pandia.ru/text/78/128/images/image012_31.gif" alt="Овал: А " width="105" height="105">1.
А – шахматы 25-5=20 – чел. умеют играть
В – шашки 20+18-20=18 – чел играют и в шашки, и в шахматы
2. Ш – множество посетителей школьной библиотеки
Р – множество посетителей районной библиотеки
 |
https://pandia.ru/text/78/128/images/image015_29.gif" width="36" height="90">.jpg" width="122 height=110" height="110">
 |
5. 46. П – пирожное, М – мороженое
6 – детей любят пирожное
6. 38. Т – трактор, К – комбайн
54+62-(86-8)=38 – умеют работать и на тракторе и на комбайне
графами" и систематически изучать их свойства.
Основные понятия.
Первое из основных понятий теории графов - это понятие вершины. В теории графов оно принимается в качестве первичного и не определяется. Его нетрудно представить себе на собственном интуитивном уровне. Обычно вершины графа наглядно изображаются в виде окружностей, прямоугольников другими фигурами (рис.1). Хотя бы одна вершина должна обязательно присутствовать в каждом графе.
Другое основное понятие теории графов - дуги. Обычно дуги представляют собой отрезки прямых или кривых, соединяющих вершины. Каждый из двух концов дуги должен совпадать с какой-нибудь вершиной. Случай, когда оба конца дуги совпадают с одной и той же вершиной, не исключается. Например, на рис.2 - допустимые изображения дуг, а на рис.3 - недопустимые:
В теории графов используются дуги двух типов - ненаправленными или направленными (ориентированными). Граф, содержащий только ориентированные дуги, называется ориентированным графом или орграфом.
Дуги могут быть однонаправленными, при этом каждая дуга имеет только одно направление, или двунаправленными.
В большинстве применений можно без потери смысла заменить ненаправленную дугу на двунаправленную, а двунаправленную - на две однонаправленных дуги. Например, так, как показано на рис. 4.
Как правило, граф либо сразу строится таким образом, чтобы все дуги имели одинаковую характеристику направленности (например, все - однонаправленные), либо приводится к такому виду путем преобразований. Если дуга AB - направленная, то это значит, что из двух ее концов один (A) считается началом, а второй (B) - концом. В этом случае говорят, что начало дуги AB есть вершина A, а конец - вершина B, если дуга направлена от A к B, или что - дуга AB исходит из вершины A и входит B (рис. 5).
Две вершины графа, соединенные какой-либо дугой (иногда, независимо от ориентации дуги) называют смежными вершинами.
Важным понятием при исследовании графов является понятие пути. Путь A1,A2,...An определяется как конечная последовательность (кортеж) вершин A1,A2,...An и дуг A1, 2,A2 ,3,...,An-1, n последовательно соединяющих эти вершины.
Важным понятием в теории графов является понятие связности. Если для любых двух вершин графа существует хотя бы один соединяющий их путь - граф называется связным.
Например, если изобразить в виде графа систему кровообращения человека, где вершины соответствуют внутренним органам, а дуги - кровеносным капиллярам, то такой граф, очевидно, является связным. Можно ли утверждать, что система кровообращения двух произвольных людей является несвязным графом? Очевидно, нет, поскольку в природе наблюдаются т. н. “сиамские близнецы”.
Связность может быть не только качественной характеристикой графа (связный/несвязный), но и количественной.
Граф называется K-связным, если каждая его вершина связана с K других вершин. Иногда говорят о слабо - и сильносвязанных графах. Эти понятия субъективны. Исследователь называет граф сильносвязанным, если для каждой его вершины количество смежных вершин, по мнению исследователя, велико.
Иногда связность определяют как характеристику не каждой, а одной (произвольной) вершины. Тогда появляются определения типа: граф называется K-связным, если хотя бы одна его вершина связана с K других вершин.
Некоторые авторы определяют связность как экстремальное значение количественной характеристики. Например, граф является K-связным, если в графе существует хотя бы одна вершина, связанная с K смежными вершинами и не существует ни одной вершины, связанной с более чем K смежными вершинами.
Например, детский рисунок человека (рис. 6) представляет собой граф с максимальной связностью равной 4.
Еще одна характеристика графа, исследуемая в ряде задач, часто называется мощностью графа. Эта характеристика определяется как количество дуг, связывающих две вершины. При этом дуги, имеющие встречное направление, часто рассматриваются раздельно.
Например, если вершины графа представляю собой узлы обработки информации , а дуги - однонаправленные каналы передачи информации между ними, то надежность системы определяется не суммарным количеством каналов, а наименьшим количеством каналов в любом направлении.
Мощность, как и связность, может определяться как для каждой пары вершин графа, так и для некоторой (произвольной) пары.
Существенная характеристика графа - его размерность. Под этим понятием обычно понимают количество вершин и дуг, существующих в графе. Иногда эта величина определяется как сумма количеств элементов обоих видов, иногда - как произведение, иногда - как количество элементов только одного (того или иного) вида.
Разновидности графов.
Объекты, моделируемые графами, имеют весьма разнообразную природу. Стремление отразить эту специфику привело к описанию большого количества разновидностей графов. Процесс этот продолжается и в настоящее время. Многие исследователи для своих конкретных целей вводят новые разновидности и выполняют их математическое исследование с большим или меньшим успехом.
В основе всего этого многообразия лежат несколько довольно простых идей, о которых мы здесь и будем говорить.
Окраска
Окраска графов - весьма популярный способ модификации графов.
Этот прием позволяет, и повысить наглядность модели и увеличить математическую загруженность. Способы введения окраски могут быть различными. По тем или иным правилам окрашиваются как дуги, так и вершины. Окраска может быть однократно определена или меняться с течением времени (т. е. при приобретении графом каких-либо свойств); цвета можно преобразовывать по тем или иным правилам, и т. д.
Например, пусть граф представляет собой модель кровообращения человека, где вершины соответствуют внутренним органам, а дуги - кровеносным капиллярам. Окрасим артерии в красный цвет, а вены - в синий. Тогда очевидно справедливость следующего утверждения - в рассматриваемом графе (рис. 8) существуют, и при этом только две, вершины, имеющие исходящие красные дуги (на рисунке красный цвет изображен жирно).
Дольность
Иногда элементы объекта, моделируемые вершинами, имеют существенно различный характер. Или к реально существующим в объекте элементам в процессе формализации оказывается полезным добавить некоторые фиктивные элементы. В этом, и некоторых других случаях, вершины графа естественно разделить на классы (доли). Граф, содержащий вершины двух типов, называют двудольным и т. д. При этом в число ограничений графа вносятся правила, касающиеся взаимоотношений вершин разных типов. Например: “не существует дуги, которая бы соединяла вершины одного типа”. Одна из разновидностей графов такого рода называется “сеть Петри” (рис. 9) и имеет достаточно широкое распространение. Более подробно сети Петри будут рассмотрены в следующей статье этого цикла.
Понятие дольности может быть применено не только к вершинам, но и к дугам.
2.2. Решение задач, используя графы.
1. Задача о Кенигсбергских мостах. На рис. 1 представлен схематический план центральной части города Кенигсберг (ныне Калининград), включающий два берега реки Перголя, два острова в ней и семь соединяющих мостов. Задача состоит в том, чтобы обойти все четыре части суши, пройдя по каждому мосту один раз, и вернуться в исходную точку. Эта задача была решена (показано, что решение не существует) Эйлером в 1736 году. (рис. 10).
2. Задача о трех домах и трех колодцах. Имеется три дома и три колодца, каким-то образом расположенные на плоскости. Провести от каждого дома к каждому колодцу тропинку так, чтобы тропинки не пересекались (рис. 2). Эта задача была решена (показано, что решение не существует) Куратовским в 1930 году. (рис. 11).
3. Задача о четырех красках. Разбиение на плоскости на непересекающиеся области называется картой. Области на карте называются соседними, если они имеют общую границу. Задача состоит в раскрашивании карты таким образом, чтобы никакие две соседние области не были закрашены одним цветом (рис. 12). С конца позапрошлого века известна гипотеза, что для этого достаточно четырех красок. В 1976 году Аппель и Хейкен опубликовали решение задачи о четырех красках, которое базировалось на переборе вариантов с помощью компьютера. Решение этой задачи «программным путем» явилось прецедентом, породившим бурную дискуссию, которая отнюдь не закончена. Суть опубликованного решения состоит в том, чтобы перебрать большое, но конечное число (около 2000) типов потенциальных контрпримеров к теореме о четырех красках и показать, что ни один случай контрпримером не является. Этот перебор был выполнен программой примерно за тысячу часов работы суперкомпьютера. Проверить «вручную» полученное решение невозможно – объем перебора выходит далеко за рамки человеческих возможностей. Многие математики ставят вопрос: можно ли считать такое «программное доказательство» действительным доказательством? Ведь в программе могут быть ошибки… Методы формального доказательства правильности программ не применимы к программам такой сложности, как обсуждаемая. Тестирование не может гарантировать отсутствие ошибок и в данном случае вообще невозможно. Таким образом, остается уповать на программистскую квалификацию авторов и верить, что они сделали все правильно.
4.
Задачи Дьюдени.
1. Смит, Джонс и Робинсон работают в одной поездной бригаде машинистом, кондуктором и кочегаром. Профессии их названы не обязательно в том же порядке, что и фамилии. В поезде, который обслуживает бригада, едут трое пассажиров с теми же фамилиями. В дальнейшем каждого пассажира мы будем почтительно называть «мистер» (м-р)
2. М-р Робинсон живет в Лос-Анджелесе.
3. Кондуктор живет в Омахе.
4. М-р Джонс давно позабыл всю алгебру, которой его учили в колледже .
5. Пассажир – однофамилец кондуктора живет в Чикаго.
6. Кондуктор и один из пассажиров, известный специалист по математической физике, хотя в одну церковь.
7. Смит всегда выигрывает у кочегара, когда им случается встречаться за партией в бильярд.
Как фамилия машиниста? (рис.13)
Здесь 1-5 – номера ходов, в скобках – номера пунктов задачи, на основании которых сделаны ходы (выводы). Далее следует из п.7, что кочегар не Смит, следовательно, Смит-машинист.
Заключение
Анализ теоретического и практического материала по исследуемой теме позволяет сделать выводы об успешности применения кругов Эйлера и графов для развития логического мышления детей, привития интереса к изучаемому материалу, применению наглядности на уроках, а так же трудные задачи свести к легким для понимания и решения.
Список литературы
1. «Занимательные задачи по информатике» , Москва, 2005
2. «Сценарии школьных праздников» Е. Владимирова, Ростов-на-Дону, 2001
3. Задачи для любознательных. , М., Просвещение, 1992г,
4. Внеклассная работа по математике, Саратов, Лицей, 2002г.
5. Удивительный мир чисел. , ., М., Просвещение, 1986г.,
6. Алгебра: учебник для 9 класса . , и др. под ред. ,- М.: Просвешение, 2008
Титов Максим
1. Рассмотреть все маршруты Нижнегорского района.
2. По данным маршрутов составить новые маршруты.
3. Показать являются ли новые маршруты Эйлеровыми графами.
4. Построить матрицу смежности для новых маршрутов.
5. Найти кратчайшие расстояния от пгт.Нижнегорского до населенных пунктов.
ВВЕДЕНИЕ ……………………………………………………………………………….3
РАЗДЕЛ 1. ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ГРАФОВ …………………………………5
РАЗДЕЛ 2. МАРШРУТЫ НИЖНЕГОРСКОГО РАЙОНА ……………………..……10
ЗАКЛЮЧЕНИЕ ………………………………………………………………………….17
СПИСОК ИСПОЛЬЗОВАННОЙ ЛИТЕРАТУРЫ …………………………………….19
ВВЕДЕНИЕ
Графы - это замечательные математические объекты, с помощью, которых можно решать математические, экономические и логические задачи. Также можно решать различные головоломки и упрощать условия задач по физике, химии, электронике, автоматике. Графы используют при составлении карт и генеалогических древ. Графами являются блок-схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, - работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего. Одними из самых распространённых графов являются схемы линий метрополитена.
В математике даже есть специальный раздел, который так и называется: «Теория графов». Теория графов является частью как топологии, так и комбинаторики. То, что это топологическая теория, следует из независимости свойств графа от расположения вершин и вида соединяющих их линии. А удобство формулировок комбинаторных задач в терминах графов привела к тому, что теория графов стала одним из мощнейших аппаратов комбинаторики. При решении логических задач обычно бывает достаточно трудно держать в памяти многочисленные факты, данные в условии, устанавливать связь между ними, высказывать гипотезы, делать частные выводы и пользоваться ими.
Актуальность темы заключается в том, что теория графов в настоящее время является интенсивно развивающимся разделом дискретной математики. Это объясняется тем, что в виде графовых моделей описываются многие объекты и ситуации: коммуникационные сети, схемы электрических и электронных приборов, химические молекулы, отношения между людьми, всевозможные транспортные схемы и многое-многое другое. Очень важное для нормального функционирования общественной жизни. Именно этот фактор определяет актуальность их более подробного изучения.
Цель работы – исследование транспортных путей Нижнегорского района.
Задачи работы:
1 . Рассмотреть все маршруты Нижнегорского района.
2 . По данным маршрутов составить новые маршруты.
3. Показать являются ли новые маршруты Эйлеровыми графами.
4. Построить матрицу смежности для новых маршрутов.
5. Найти кратчайшие расстояния от пгт.Нижнегорского до населенных пунктов.
Объектом исследования является карта транспортных путей Нижнегорского района.
Практическая значимость данной работы в том, что она может быть использована на уроках при решении разных задач, а также в различных областях науки и в современной жизни.
Применяемые методы: поиск источников информации, наблюдение, сравнение, анализ, математическое моделирование.
С общим замыслом работы связана структура разделов. Основная часть состоит из трех глав. В первой рассмотрены основные понятия графов. Во второй главе исследуются маршруты Нижнегорского района.
При работе использовал ряд литературных источников: специальная литература по теории графов, познавательную литературу, различные научно-популярные, образовательные, специализированные журналы.
РАЗДЕЛ 1
ОСНОВНЫЕ ОПРЕДЕЛЕНИЯ ГРАФОВ
1.1. Основные понятия теории графов
Граф представляет собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек. (Рис.1.1.)
Рис.1.1.
Вершина графа - точка, где могут сходиться/выходить рёбра и/или дуги.
Ребро графа - ребро соединяет две вершины графа.
Степень вершины - количество рёбер, выходящих из вершины графа.
Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.
Если направление связи имеет значение, то линии снабжают стрелками, и в этом случае граф называется ориентированным графом, орграфом. (Рис.1.2.)
Рис.1.2.
Взвешенный граф - граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра). (Рис.1.3.)
Рис. 1.3.
Графы, в которых построены все возможные ребра, называются полными графами. (Рис.1.4.)
Рис. 1.4.
Граф называется связным, если любые две его вершины могут быть соединены путем, т. е. последовательностью ребер, каждое следующее из которых начинается в конце предыдущего.
Матрица смежности – это матрица, элемент M[i] [j] которой равен 1, если существует ребро из вершины i в вершину j, и равен 0, если такого ребра нет (Рис.1.5. для графа на рис.1.1).
1.2. Характеристика Эйлеровых графов
Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. (рис.1.6.)
Такими графы названы в честь учёного Леонарда Эйлера.
Закономерность 1.
Невозможно начертить граф с нечетным числом нечетных вершин.
Закономерность 2.
Если все вершины графа четные, то можно не отрывая карандаш от бумаги («одним росчерком»), проводя по каждому ребру только один раз, начертить этот граф. Движение можно начать с любой вершины и закончить его в той же вершине.
Закономерность 3.
Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них.
Закономерность 4.
Граф, имеющий более двух нечетных вершин, невозможно начертить «одним росчерком».
Фигура (граф), которую можно начертить, не отрывая карандаш от бумаги, называется уникурсальной.
Рис.1.6.
1.3. Поиск кратчайшего расстояния в графе (Алгоритм Дейкстри)
Задача: задана сеть дорог между городами, часть которых могут иметь одностороннее движение. Найти кратчайшие расстояния от заданного города до всех остальных городов (рис.1.7).
Та же задача: дан связный граф с N вершинами, веса ребер заданы матрицей W. Найти кратчайшие расстояния от заданной вершины до всех остальных.
Алгоритм Дейкстры (E.W. Dijkstra, 1959):
1. Присвоить всем вершинам метку ∞.
2. Среди нерассмотренных вершин найти вершину j с наименьшей меткой.
3. Для каждой необработанной вершины i: если путь к вершине i через вершину j меньше существующей метки, заменить метку на новое расстояние.
4. Если остались необработанны вершины, перейти к шагу 2.
5. Метка = минимальное расстояние.
Рис.1.7.
Рис.1.8. Решение задачи
РАЗДЕЛ 2
МАРШРУТЫ НИЖНЕГОРСКОГО РАЙОНА
2.1. Маршруты Нижнегорского района
Нижнегорский район находится в степной части на севере АР Крым. В состав Нижнегорского района входят пгт.Нижнегорский и 59 населенных пунктов.
Через Нижнегорский район проходят две трассы: 2Р58 и 2Р64. Существуют 8 маршрутов, следующие от А/С Нижнегорская до других населенных пунктов. В своей работе я буду рассматривать эти маршруты:
1 маршрут «Нижнегорск – Красногвардейск». Следует через: Нижнегорск – Плодовое – Митофановка – Буревестник – Владиславовка.
2 маршрут «Нижнегорск - Изобильное»: Нижнегорск – Семенное – Кирсановка – Лиственное – Охотское – Цветущее – Емельяновка – Изобильное.
3 маршрут «Нижнегорск - Великоселье»: Нижнегорк – Семенное – Двуречье – Акимовка – Лужки – Заливное – Степановка – Луговое – Чкалово – Великоселье.
4 маршрут «Нижнегорск – Белогорск (трасса 2Р64)»: Нижнегорск – Желябовка – Ивановка – Заречье – Серово – Садовое – Пены.
5 маршрут «Нижнегорск - Уваровка»: Нижнегорск – Семенное – Новоивановка – Уварвка.
6 маршрут «Нижнегорск - Любимовка»: Нижнегорск – Семенное – Двуречье – Акимовка – Лужки – Заливное – Степановка – Луговое – Коворово – Дворовое – Любимовка.
7 маршрут «Нижнегорск - Пшеничное»: Нижнегорск – Семенное – Двуречье – Акимовка – Лужки – Заливное – Степановка – Луговое – Коворово – Дворовое – Сливянка – Пшеничное.
8 маршрут «Нижнегорск – Зоркино (траса 2Р58)»: Нижнегорск – Разливы – Михайловка – Кунцево – Зоркино.
Существует очень много сел, в которые автобусы по маршрутам не заезжают и людям приходится добираться до своих населенных пунктов самостоятельно, в основном пешком. Поэтому передо мною стала задача: А можно составить новые маршруты и включить в них населенные пункты, в которые автобусы не заходят.
Маршруты «Нижнегорск - Уваровка» «Нижнегорск - Любимовка» «Нижнегорск - Пшеничное» изменить нельзя, так как по пути их следования, автобусы заезжают во все населенные пункты, поэтому эти маршруты я рассматривать не буду.
Рассмотрим остальные пять маршрутов. Населенные пункты обозначим цифрами – это вершины графа, а расстояния между ними – ребрами графа и получим пять графов. Рассмотрим каждый граф по отдельности.
2.2. Исследование маршрутов Нижнегорского района
1 маршрут: Нижнегорск – Красногвардейск.
Нижнегорск – 1
Плодовое – 2
Митрофановка – 3
Червоное – 6
Буревестник – 4
Новогригорьевка – 7
Владиславовка – 5
Не заезжает в пункт 6, 7. Добавим в маршрут эти населенные пункты.
Рис.2.1.
Граф не является Эйлеровым. Новый маршрут выглядит так: Нижнегорск – Плодовое – Митрофановка – Буревестник – Новогригорьевка – Владиславовка. Добавилось село Новогригорьевка.
2 маршрут: Нижнегорск – Изобильное.
Нижнегорск – 1
Семенное – 2
Кирсановка – 3
Лиственное – 4
Охотское – 5
Цветущее – 6
Емельяновка – 7
Изобильное – 8
Кулички – 9
Родники - 10
Не заезжает в пункт 9,10. Добавим в маршрут эти населенные пункты.
Рис.2.2.
Граф не является Эйлеровым и связным, поэтому нельзя построить новый маршрут. Маршрут остается тот же.
3 маршрут: Нижнегорск - Великоселье
Нижнегорск – 1
Семенное – 2
Двуречье – 3
Акимовка – 4
Лужки – 5
Заливное – 6
Степановка – 7
Луговое – 8
Чкалово – 9
Великоселье – 10
Широкое - 11
Не заезжает в пункт 11. Добавим в маршрут этот населенный пункт.
Рис.2.3.
Граф не является Эйлеровым. Маршрут остается тот же.
4 маршрут: Нижнегорск - Белогорск (Трасса 2Р64)
Нижнегорск – 1 Косточковка - 12
Желябовка – 2 Фрунзе - 13
Ивановка – 3 Приречное - 14
Заречье – 4 Жемчужина - 15
Серово – 5
Садовое – 6
Пены – 7
Ломоносово – 8
Кукурузное – 9
Тамбовка – 10
Тарасовка - 11
Не заезжает в пункты 8-18. Добавим в маршрут эти населенные пункты.
Рис.2.4.
Граф не является Эйлеровым. Новый маршрут выглядит так: Нижнегорск – Желябовка – Ивановка – Заречье – Тамбовка – Тарсовка – Приречное – Жемчужина – Пены.
5 маршрут: Нижнегорск - Зоркино (Трасса 2Р58)
Нижнегорск – 1
Разливы – 2
Михайловка – 3
Кунцево – 4
Зоркино – 5
Уютное – 6
Нижинское – 7
Не заезжает в пункт 6,7. Добавим в маршрут эти населенные пункты.
Рис.2.5.
Граф не является Эйлеровым и связным, поэтому маршрут остается тот же.
ЗАКЛЮЧЕНИЕ
Фрактальная наука очень молода, и ей предстоит большое будущее. Красота фракталов далеко не исчерпана и ещё подарит нам немало шедевров – тех, которые услаждают глаз, и тех которые доставляют истинное наслаждение разума. В этом заключается новизна работы.
В заключение хочется сказать, что после того как были открыты фракталы, для многих учёных стало очевидно, что старые, добрые формы евклидовой геометрии сильно проигрывают большинству природных объектов из-за отсутствия в них некоторой нерегулярности, беспорядка и непредсказуемости. Возможно, что новые идеи фрактальной геометрии помогут изучить многие загадочные явления окружающей природы. В настоящие время фракталы стремительно вторгаются во многие области физики, биологии, медицины, социологии, экономики. Методы обработки изображений и распознавания образов, использующие новые понятия, дают возможность исследователям применить этот математический аппарат для количественного описания огромного количества природных объектов и структур.
В процессе исследования была проделана следующая работа:
1. Проанализирована и проработана литература по теме исследования.
2. Рассмотрены и изучены различные виды фракталов.
3. Представлена классификация фракталов.
4. Собрана коллекция фрактальных образов для первичного ознакомления с миром фракталов.
5. Составлены программы для построения графического образа фракталов.
Лично для меня изучение темы «Неисчерпаемое богатство фрактальной геометрии» оказалось очень интересной и необычной. В процессе исследования я сам для себя сделал массу новых открытий, связанных не только с темой проекта, но и с окружающим миров в целом. Я испытываю огромный интерес к этой теме, и поэтому данная работа оказала исключительно положительное влияние на мое представление о современной науке.
Закончив свой проект, я могу сказать, что всё из того, что было задумано, удалось. В следующем году я продолжу работу над темой «фракталы», так как это тема очень интересна и многогранна. Думаю, что я решил проблему своего проекта, так как мной были достигнуты все поставленные цели. Работа над проектом показала мне то, что математика – это не только точная, но и красивая наука.
СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ
1. В.М. Бондарев, В.И. Рублинецкий, Е.Г. Качко. Основы программирования, 1998 г.
2. Н. Кристофидес. Теория графов: алгоритмический подход, Мир, 1978 г.
3. Ф.А. Новиков. Дискретная математика для программистов, Питер, 2001 г.
4. В.А. Носов. Комбинаторика и теория графов, МГТУ, 1999 г.
5. О. Оре. Теория графов, Наука, 1982 г.
Цель исследования :
Рассмотреть возможности применения графового аппарата для решения логических и комбинаторных задач.
Задачи исследования:
рассмотреть решение задач при помощи графов;
научиться переводить задачи на язык графов;
сравнить традиционные методы решения задач с методами теории графов.
Актуальность исследования:
Графы используют во всех отраслях нашей жизни. Знание основ теории графов необходимо в различных областях, связанных с управлением производством, бизнесом (например, сетевой график строительства, графики доставки почты), построении путей транспортировки и доставки, решении задач. Графы используют в связи с развитием теории вероятностей, математической логики и информационных технологий.
Гипотеза:
Использование теории графов делает решение многих логических и комбинаторных задач будет менее трудоемким.
Содержание:
Введение. Понятие графа.
Основные свойства графа.
Основные понятия теории графов и их доказательства.
Избранные задачи.
Хроматическое число графа.
Литература.
Введение. Понятие графа.
Любой из нас, конечно, прав,
Найдя без проволочек,
Что он…обыкновенный граф
Из палочек и точек.
Теория графов в настоящее время является интенсивно развивающимся разделом дискретной математики. Графы и связанные с ним методы исследований органически пронизывают на разных уровнях едва ли не всю современную математику. Язык графов прост, понятен и нагляден. Графовые задачи обладают рядом достоинств, позволяющих использовать их для развития соображения, улучшения логического мышления, применения смекалки. Графы – замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач.
В математике существует целый раздел – теория графов, который изучает графы, их свойства и применение. Математические графы с дворянским титулом «граф» связывает общее происхождение от латинского слова «графио» - пишу. Типичными графами являются схемы авиалиний, которые часто вывешивается в аэропортах, схемы метро, а на географических картах – изображение железных дорог. Выбранные точки графа называются его вершинами, а соединяющие их линии – ребрами. Один из графов хорошо знаком москвичам и гостям столицы – это схема московского метрополитена: вершины – конечные станции и станции пересадок, рёбра – пути, соединяющие эти станции. Генеалогическое древо графа Л. Н. Толстого – ещё один граф. Здесь вершины – предки писателя, а рёбра показывают родственные связи между ними.
рис.1 рис. 2
Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями.При изображении графа не имеет значения расположение вершин на плоскости, кривизна и длина рёбер (рис.3).Вершины графов обозначаются буквами или натуральными числами. Ребра графа – пары чисел.
рис. 3
Графами являются блок – схемы программ для ЭВМ, сетевые графики строительства, где вершины – события, означающие окончания работ на некотором участке, а ребра, связывающие эти вершины, - работы, которые возможно начать по совершении одного события и необходимо выполнить для совершения следующего. Свойства графов, как и их изображения, не будут зависеть и не изменятся от того, соединены вершины отрезками или кривыми линиями. Это дает возможность изучения их свойств с помощью одной из молодых наук – топологии, хотя сами задачи теории графов являются типичными задачами комбинаторики.
Что же связывает топологию и комбинаторику? Теория графов является частью как топологии, так и комбинаторики. То, что это топологическая теория, следует из независимости свойств графа от расположения вершин и вида соединяющих их линий. А удобство формулировок комбинаторных задач в терминах графов привело к тому, что теория графов стала одним из мощнейших аппаратов комбинаторики.
Но кто придумал эти графы? Где они применяются? Все ли они одинаковые или есть разновидности?
История возникновения теории графов. Классическая задача о кёнигсбергских мостах.
Основы теории графов как математической науки заложил в 1736 году Леонард Эйлер, рассматривая задачу о кёнигсбергских мостах. «Мне была предложена задача об острове, расположенном в городе Кёнигсберге и окружённом рекой, через которую перекинуто 7 мостов. Спрашивается, может ли кто – нибудь непрерывно обойти их, проходя только однажды через каждый мост…» (Из письма Л. Эйлера итальянскому математику и инженеру Маринони от 13 марта 1736 года)
Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены (рис.4). Кенигсбергцы предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз. Прогуляться по городским мостам предложили и Эйлеру. После безуспешной попытки совершить нужный обход, он начертил упрощённую схему мостов. Получился граф, вершины которого – части города, разделённые рекой, а рёбра – мосты (рис.5).
рис. 4 рис. 5
Прежде, чем обосновать возможность требуемого маршрута, Эйлер рассмотрел и другие, более сложные карты. В итоге он доказал общее утверждение для того чтобы можно было обойти все рёбра графа по одному разу и вернуться в исходную вершину, необходимо и достаточно выполнение следующих двух условий:
из любой вершины графа должен существовать путь по его рёбрам в любую другую вершину (графы, удовлетворяющие этому требованию, называются связными);
из каждой вершины должно выходить чётное количество рёбер.
«Следовательно, надо держаться следующего правила: если на каком-либо рисунке число мостов, ведущих в некоторую область, будет нечетным, тогда желаемый переход через все мосты одновременно не может быть осуществлен иначе, как если переход или начинается, или заканчивается в этой области. А если число мостов четное, отсюда не может возникнуть никакого затруднения, так как ни начало, ни конец перехода при этом не фиксируются. Отсюда следует такое общее правило: если будет больше чем две области, к которым ведет нечетное количество мостов, тогда желательный переход вообще не может быть совершен. Ибо представляется совершенно невозможным, чтобы переход и начинался, и заканчивался в какой-нибудь одной из этих областей. А если будут только две области такого рода (так как не могут быть даны одна область этого рода или нечетное число областей), тогда может быть совершен переход через все мосты, но с таким условием, чтобы начало перехода было в одной, а конец в другой из этих областей. Когда в предложенной фигуре А и В есть области, к которым ведет нечетное число мостов, а число мостов, ведущих к С, является четным, то я считаю, что переход или построение мостов может иметь место, если переход начинается или из А, или из В, а если же кто-нибудь пожелает начать переход из С, то он никогда не сможет достигнуть цели. В расположении кенигсбергских мостов я имею четыре области А, В, С, D, взаимно отделенные друг от друга водой, к каждой из которых ведет нечетное число мостов (рис.6).
рис. 6
Следовательно, ты можешь убедиться, славнейший муж, что это решение по своему характеру, по-видимому, имеет мало отношения к математике, и мне непонятно, почему следует скорее от математика ожидать этого решения, нежели от какого-нибудь другого человека, ибо это решение подкрепляется одним только рассуждением и нет необходимости привлекать для нахождения этого решения какие-либо законы, свойственные математике. Итак, я не знаю, каким образом получается, что вопросы, имеющие совсем мало отношения к математике, скорее разрешаются математиками, чем другими [учеными]. Между тем ты, славнейший муж, определяешь место этого вопроса в геометрии положения, и что касается этой новой науки, то, признаюсь, мне неизвестно, какого рода относящиеся сюда задачи желательны были Лейбницу и Вольфу. Итак, я прошу тебя, если ты считаешь, что я способен нечто создать в этой новой науке, чтобы ты соблаговолил мне прислать несколько определенных, относящихся к ней задач...»
Основные свойства графа.
Решая задачу про Кенигсбергские мосты, Эйлер установил следующие свойства графа:
Если все вершины графа чётные, то можно одним росчерком (т.е. не отрывая карандаша от бумаги и не проводя дважды по одной и той же линии) начертить граф.
Граф с двумя нечётными вершинами тоже можно начертить одним росчерком. Движение нужно начинать от любой нечётной вершины, а заканчивать на другой нечётной вершине.
Граф с более чем двумя нечётными вершинами, невозможно начертить одним росчерком.
Понятие эйлерова и гамильтонова циклов.
Замкнутый путь, проходящий по одному разу по всем рёбрам, до сих пор называют эйлеровым циклом.
Если отбросить условие возвращения в исходную вершину, то можно допустить наличие двух вершин, из которых выходит нечётное количество рёбер. В этом случае начинать движение следует из одной из этих вершин, а заканчивать в другой.
В задаче о Кенигсбергских мостах все четыре вершины соответствующего графа – нечётные, значит, нельзя пройти по всем мостам ровно один раз и закончить путь там же.
Граф получить на листе бумаги очень просто. Надо взять карандаш и нарисовать на этом листке, не отрывая карандаша от бумаги и не проводя дважды по одной линии, что угодно. Отметить точками «перекрёстки» и начальную и конечную точки, если они не совпадают с «перекрёстками». Получившуюся фигуру можно назвать графом. Если начальная и конечная точки рисунка совпадают, то все вершины окажутся чётными, если же начальная и конечная точки не совпадают, то они окажутся нечётными вершинами, а все остальные будут чётными. Решение многих логических задач с помощью графов вполне доступно уже младшим школьникам. Для этого им достаточно иметь лишь интуитивные представления о графах и самых очевидных их свойствах. Во многих детских головоломках можно встретить такие задания: начертить фигуру, не отрывая карандаша от бумаги и не проводя дважды по одной линии.
рис. 7 а) б)
Рисунок 7 (а) имеет две вершины (нижние), из которых выходит нечётное количество рёбер. Поэтому рисунок нужно начинать с одной из них, а в другой заканчивать. В рисунке 7(б) существует эйлеров цикл, так как из шести вершин графа выходит чётное число рёбер.
В 1859 г. сэр Вильям Гамильтон, знаменитый ирландский математик, давший миру теорию комплексного числа и кватерниона, предложил необычную детскую головоломку, в которой предлагалось совершить «кругосветное путешествие» по 20 городам, расположенным в различных частях земного шара (рис. 8). В каждую вершину деревянного додекаэдра, помеченную названием одного из известных городов (Брюссель, Дели, Франкфурт и т. д.), был вбит гвоздик и к одному из них была привязана нить.Требовалось соединить вершины додекаэдра этой нитью так, чтобы она проходила вдоль его ребер, обвивая каждый гвоздик ровно один раз, и чтобы полученный в результате ниточный маршрут был замкнутым (циклом).Каждый город соединялся дорогами с тремя соседними так, что дорожная сеть образовывала 30 ребер додекаэдра, в вершинах которого находились города a, b ... t. Обязательным условием было требование посетить каждый город, за исключением первого, лишь один раз.
рис. 8 рис. 9
Если путешествие начать из города a, то последними должны быть города b, e или h, иначе мы не сможем вернуться в первоначальный пункт a. Непосредственное исчисление показывает, что число таких замкнутых маршрутов равно 60.Можно потребовать посещения всех городов строго по одному разу, включая и первый, т.е. допускается окончание путешествия в любом городе (например, предполагается, что в начальный пункт можно будет вернуться самолетом). Тогда общее число цепных маршрутов увеличится до 162 (рис.9).
В этом же, 1859 году Гамильтон предложил владельцу фабрики игрушек в Дублине запустить её в производство. Владелец фабрики принял предложение Гамильтона и выплатил ему 25 гиней. Игрушка напоминала «кубик Рубик», ещё не так давно пользующегося огромной популярностью, и оставила заметный след в математике. Замкнутый путь по рёбрам графа, проходящий по одному разу через все вершины, называется гамильтоновым циклом. В отличие от эйлерова цикла условия существования на произвольном графе гамильтонова цикла до сих пор не установлены.
Понятие полного графа. Свойства плоских графов.
А всегда ли граф можно изобразить на плоскости так, чтобы его рёбра не пересекались? Оказывается, нет. Графы, для которых это возможно, называются плоскими. Графы, в которых не построены все возможные ребра, называются неполными графами, а тот граф, в котором соединены все вершины всеми возможными способами, называется полным графом.
рис. 10 рис. 11
На рисунке 10 изображён граф с пятью вершинами, который не укладывается на плоскость без пересечения рёбер. Каждые две вершины этого графа соединены ребром. Это полный граф. На рисунке 11 – граф с шестью вершинами и девятью рёбрами. Он носит название «домики – колодцы». Оно произошло от старинной задачи – головоломки. В трёх избушках жили трое друзей. Около их домиков находились три колодца: один с солёной водой, второй – со сладкой, третий – с пресной. Но однажды друзья поссорились, да так, что и видеть друг друга не хотели. И решили они по- новому проложить тропинки от домов к колодцам, чтобы их пути не пересекались. Как это сделать? На рисунке 12 проведено восемь из девяти тропинок, но провести девятую уже не удаётся.
рис.12
Польский математик Казимеж Куратовский установил, что никаких принципиально иных не плоских графов не существует. Точнее, если граф «не укладывается» на плоскость, то в нём «сидит» по крайней мере один из этих двух графов (полный граф с пятью вершинами или «домики – колодцы»), быть может с дополнительными вершинами на рёбрах.
Льюис Кэрролл, автор книги «Алиса в стране чудес», любил давать своим знакомым следующую головоломку. Он просил обвести фигуру, изображённую на рисунке, не отрывая карандаша от бумаги и не проводя дважды по одной линии. Подсчитав чётность вершин, убеждаемся, что эта задача легко решается, причём начинать обход можно с любой вершины, так как они все чётные. Однако, он усложнял задачу тем, что требовал, чтобы при обводке линии не пересекались. Справиться с этой проблемой можно следующим способом. Раскрасим фигуру так, чтобы её граничащие части оказались разного цвета. Затем разъединим пересекающиеся линии таким образом, чтобы закрашенная часть представляла из себя единый кусок. Теперь остаётся обвести по краю одним росчерком закрашенную область – это и будет искомая линия (рис. 13).
рис. 13
Основные понятия теории графов и их доказательства .
Плоские графы обладают многими интересными свойствами. Так, Эйлер обнаружил простую связь между количеством вершин (B), количеством рёбер (Р),количеством частей (Г) на которые граф разделяет плоскость
В – P + Г = 2.
1. Определение . Число рёбер, выходящих из одной вершины, называют степенью этой вершины.
Лемма1. Число рёбер в графе ровно в 2 раза меньше, чем сумма степеней вершин.
Доказательство. Любое ребро графа связывают 2 вершины. Значит, если будем складывать число степеней всех вершин графа, то получим удвоенное число рёбер, т.к. каждое ребро было подсчитано дважды.
Лемма2 . Сумма степеней вершин графа чётна .
Доказательство. По лемме1 число рёбер в графе в 2 раза меньше суммы степеней вершин, значит сумма степеней вершин чётна (делится на 2).
2. Определение . Если степень вершины чётная, то вершина называется чётной, если степень не чётная, то вершина нечётная.
Лемма3 . Число нечётных вершин графа чётно.
Доказательство. Если в графе есть n чётных и k нечётных вершин, то сумма степеней чётных вершин чётна. Сумма степеней нечётных вершин нечётна, если количество этих вершин нечётна. Но тогда общее число степеней вершин тоже нечётна, чего не может быть. Значит, k чётно.
Лемма 4. Если полный граф имеет n вершин, то количество ребер будет равно
Доказательство. В полном графе с n вершинами из каждой вершины выходит по n -1 рёбер. Значит, сумма степеней вершин равна n ( n -1). Число рёбер в 2 раза меньше, то есть .
Избранные задачи.
Зная свойства графа, полученные Эйлером, теперь легко можно решить такие задачи:
Задача 1. Из трех человек, стоящих рядом, один всегда говорит правду (правдолюб), другой всегда лжет (лжец), а третий, смотря по обстоятельствам, говорит либо правду, либо ложь (дипломат). У стоящего слева спросили: "Кто стоит рядом с тобой?". Он ответил: "Правдолюб". Стоящему в центре задали вопрос: "Кто ты?", и он ответил: "Я дипломат". Когда у стоящего справа спросили: "Кто стоит рядом с тобой?", он сказал: "Лжец". Кто где стоял?
Решение: Если в данной задаче ребро графа будет соответствовать месту,занимаемому тем или иным человеком, то нам могут представиться следующие возможности.
Рассмотрим первую возможность. Если "правдолюб" стоит слева, то рядом с ним, судя по его ответу, также стоит "правдолюб". У нас же стоит "лжец". Следовательно, эта расстановка не удовлетворяет условию задачи. Рассмотрев таким образом все остальные возможности, мы придем к выводу, что позиция "дипломат", "лжец", "правдолюб" удовлетворяет задаче. Действительно, если "правдолюб" стоит справа, то, по его ответу, рядом с ним стоит "лжец", что выполняется. Стоящий в центре заявляет, что он "дипломат", и, следовательно, лжет (что возможно из условия), а стоящий справа также лжет. Таким образом, все условия задачи выполнены.
Задача 2. В 10-значном числе каждые две подряд идущие цифры образуют двузначное число, которое делится на 13. Докажите, что среди этих цифр нет цифры 8.
Решение. Существует 7 двузначных чисел, которые делятся на 13. Обозначим эти числа точками и применим определение графа. По условию каждые 2 подряд идущие цифры образуют двузначное число, которые делятся на 13, значит цифры, из которых состоит 10-значное число, повторяются. Соединим вершины графа рёбрами так, чтобы цифры, входящие в этот граф повторялись.
13 65
91 39 52
Из построенных графов видно, что среди цифр 10-значного числа цифры 8 быть не может.
Задача 3. В деревне 10 домов, и из каждого выходит по 7 тропинок, идущих к другим домам. Сколько всего тропинок приходит между домами?
Решение. Пусть дома - вершины графа, тропинки - рёбра. По условию из каждого дома (вершины) выходит 7 тропинок (рёбер), тогда степень каждой вершины 7, сумма степеней вершин 7×10=70, а число рёбер 70: 2= 35. Таким образом между домами проходит 35 тропинок.
Задача 4: Между 9 планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля-Меркурий, Плутон-Венера, Земля-Плутон, Плутон-Меркурий, Меркурий-Венера, Уран-Нептун, Нептун-Сатурн, Сатурн-Юпитер, Юпитер-Марс и Марс-Уран. Можно ли добраться с Земли до Марса?
Решение. Нарисуем схему: планетам будут соответствовать точки, а соединяющим их маршрутам - непересекающиеся между собой линии.
Сделав набросок рисунка маршрутов, мы нарисовали граф, соответствующий условию задачи. Видно, что все планеты Солнечной системы разделились на две не связанных между собой группы. Земля принадлежит одной группе, а Марс - второй. Долететь с Земли до Марса нельзя.
Классическая «задача коммивояжёра». «Жадные» алгоритмы.
Одна из классических задач теории графов называется «задачей коммивояжёра» или «задачей о бродячем торговце». Представим себе торгового агента, который должен побывать в нескольких городах и вернуться обратно. Известно, какие дороги соединяют эти города и каковы расстояния между этими городами по данным дорогам. Нужно выбрать самый короткий маршрут. Это же не «игрушечная» задача. Например, водитель почтового автомобиля, вынимающий письма из почтовых ящиков, очень хотел бы знать кратчайший маршрут, как и водитель грузовика, развозящий товары по киоскам. А решить эту задачу довольно – таки сложно, потому что число вершин графа очень велико. А вот другая задача, в некотором смысле противоположная задаче коммивояжёра. Предполагается проложить железную дорогу, которая соединит несколько крупных городов. Для любой пары городов известна стоимость прокладки пути между ними. Требуется найти наиболее дешёвый вариант строительства. На самом деле алгоритм нахождения оптимального варианта строительства довольно прост. Продемонстрируем его на примере дороги, соединяющей пять городов А, В, С, D и Е. Стоимость прокладки пути между каждой парой городов указана в таблице (рис.14), а расположение городов на карте (рис.15)
1,5
2,5
1,5
1,2
0,8
1,2
1,1
0,9
1,1
2,7
2,5 5
ис.е, а расположеие городов аждой паройдов А, В С тагрузовика, разво
0,8
0,9
2,7
В
А А
D D
Е
С
рис.14 рис. 15
Сначала строим ту дорогу, которая имеет наименьшую стоимость. Это маршрут В →Е. Теперь найдём самую дешёвую линию, соединяющую В или Е с каким-нибудь из городов. Это путь между Е и С. Включаем его в схему. Далее поступаем аналогично – ищем самый дешёвый из путей, соединяющих один из городов В, С, Е с одним из оставшихся – А или D . Это дорога между С и А. Осталось подключить к железнодорожной сети город D .
Дешевле всего соединить его с С. Получим сеть железнодорожных путей (рис. 16).рис. 16
Этот алгоритм нахождения оптимального варианта строительства железной дороги относится к категории «жадных»: на каждом шаге решения этой задачи мы выбираем самое дешёвое продолжение пути. Для данной задачи он подходит как нельзя лучше. Но в задаче о коммивояжёре «жадный» алгоритм не даст оптимального решения. Если с самого начала выбирать самые «дешёвые» элементы, т.е. кратчайшие расстояния, то не исключено, что в конце концов придётся воспользоваться очень «дорогими» - длинными, и общая длина маршрута окажется существенно выше оптимальной.
Итак, для решения некоторых задач можно использовать метод или алгоритм, который называется «жадным». «Жадный» алгоритм – алгоритм нахождения наикратчайшего расстояния путём выбора самого короткого, ещё не выбранного ребра, при условии, что оно не образует цикла с уже выбранными рёбрами. «Жадным» этот алгоритм назван потому, что на последних шагах приходится жестоко расплачиваться за жадность. Посмотрим, как поведет себя при решении задачи о коммивояжёре «жадный» алгоритм. Здесь он превратится в стратегию «иди в ближайший (в который еще не входил) город». Жадный алгоритм, очевидно, бессилен в этой задаче. Рассмотрим для примера сеть на рисунке 17, представляющую узкий ромб. Пусть коммивояжер стартует из города 1. Алгоритм «иди в ближайший город» выведет его в город 2, затем 3, затем 4; на последнем шаге придется платить за жадность, возвращаясь по длинной диагонали ромба. В результате получится не кратчайший, а длиннейший тур. Однако в некоторых ситуациях «жадный» алгоритм определяет-таки кратчайший путь.
2
4
1
4 3
3
рис. 17
Есть ещё один метод для решения подобных задач - метод полного перебора (иногда говорят Метод перебора, подразумевая при этом полный перебор - это не совсем правильно, так как перебор может быть и не полным), который заключается в том, что выполняется перебор всех возможных комбинаций точек (пунктов назначения). Как известно из математики, число таких перестановок равно n!, где n – количество точек. Так как в задаче коммивояжера исходный пункт обычно принимается одним и тем же (первая точка), то нам достаточно перебрать оставшиеся, т.е. количество перестановок будет равно (n–1)!. Этот алгоритм почти всегда дает точное решение задачи коммивояжера, однако продолжительность таких вычислений может занять непозволительно много времени. Известно, что при значениях n > 12, современный компьютер не смог бы решить задачу коммивояжера даже за все время существования вселенной. Существуют и другие алгоритмы для решения задачи коммивояжера, которые значительно точнее «жадного» алгоритма и значительно быстрее метода полного перебора. Однако мы рассматриваем графы, а эти методы не связаны с теорией графов.
Хроматическое число графа.
Задача о раскраске географической карты
Дана географическая карта, на которой изображены страны, разделяемые границами. Требуется раскрасить карту так, чтобы страны, имеющие общие участки границы, были окрашены в разные цвета, и чтобы при этом было использовано минимальное количество цветов.
По данной карте построим граф следующим образом. Поставим в соответствие странам карты вершины графа. Если какие-то две страны имеют общий участок границы, то соответствующие им вершины соединим ребром, в противном случае – нет.Легко видеть, что раскраске карты соответствует правильная раскраска вершин полученного графа, а минимальное количество необходимых красок равно хроматическому числу этого графа.
Хроматическим числом графа называется наименьшее количество красок, с помощью которых можно так раскрасить вершины графа, что любые две вершины, соединенные ребром, окрашиваются при этом в разные цвета. Долгое время математики не могли решить такую проблему: достаточно ли четырех красок, для того чтобы раскрасить произвольную географическую карту так, чтобы любые две страны, имеющие общую границу, были окрашены разными красками? Если изобразить страны точками – вершинами графа, соединив ребрами те вершины, для которых соответствующие им страны граничат (рис.18), то задача сведется к следующей: верно ли, что хроматическое число любого графа, расположенного на плоскости не больше четырех? Положительный ответ на этот вопрос был лишь недавно получен с помощью ЭВМ.
рис. 18
Игра «четыре краски»
Стивен Барр предложил логическую игру на бумаге для двух игроков, названную «Четыре краски». По словам Мартина Гарднера - «Я не знаю лучшего способа понять трудности, которые встречаются на пути решения проблемы четырёх красок, чем просто поиграть в эту любопытную игру»
Для этой игры нужны четыре цветных карандаша. Первый игрок начинает игру, рисуя произвольную пустую область. Второй игрок закрашивает её любым из четырёх цветов и в свою очередь рисует свою пустую область. Первый игрок закрашивает область второго игрока и добавляет новую область, и так далее - каждый игрок раскрашивает область соперника и добавляет свою. При этом области, имеющие общую границу, должны быть раскрашены в разные цвета. Проигрывает тот, кто на своём ходу вынужден будет взять пятую краску.
Комбинаторные и логические задачи.
В 1936 году немецкий математик Д. Кёниг впервые провёл исследование подобных схем и предложил называть такие схемы «графами» и систематически изучать их свойства. Итак, как отдельная математическая дисциплина теория графов была представлена лишь в 30 – е годы ХХ столетия в связи с тем, что в обиход вошли так называемые «большие системы», т.е. системы с большим числом объектов, связанных между собой разнообразными соотношениями: сети железных дорог и авиалиний, телефонные узлы на много тысяч абонентов, системы заводов – потребителей и предприятий – поставщиков, радиосхемы, большие молекулы и т.д. и т. п. Стало ясно, что разобраться в функционировании таких систем невозможно без изучения их конструкции, их структуры. Здесь и пригодилась теория графов. В середине XX века задачи теории графов стали возникать также и в чистой математике (в алгебре, топологии, теории множеств). Чтобы можно было применять теорию графов в столь разнообразных областях, она должна быть в высшей степени абстрактной и формализованной. Ныне она переживает эпоху бурного возрождения.Графы используются: 1) в теории планирования и управления, 2) в теории расписаний, 3) в социологии, 4) в математической лингвистике, 5) экономике, 6) биологии, 7) химии, 8) медицине, 9) в областях прикладной математики таких, как теория автоматов, электроника, 10) в решении вероятностных и комбинаторных задач и т.д. Наиболее близки к графам – топология и комбинаторика.
Комбинато́рика (Комбинаторный анализ) - раздел математики, изучающий дискретные объекты, множества (сочетания, перестановки, размещения и перечисления элементов) и отношения на них (например, частичного порядка). Комбинаторика связана со многими другими областями математики - алгеброй, геометрией, теорией вероятностей и имеет широкий спектр применения в различных областях знаний (например в генетике, информатике, статистической физике). Термин «комбинаторика» был введён в математический обиход Лейбницем, который в 1666 году опубликовал свой труд «Рассуждения о комбинаторном искусстве».Иногда под комбинаторикой понимают более обширный раздел дискретной математики, включающий, в частности, теорию графов.
Широкое развитие теория графов получила с 50-х гг. 20 в. в связи со становлением кибернетики и развитием вычислительной техники. И з современных математиков над графами работали - К. Берж, О. Оре, А. Зыков.
Графы часто используют для решения логических проблем, связанных с перебором вариантов. Для примера рассмотрим такую задачу. В ведре 8 л воды, и имеется две кастрюли емкостью 5 и 3 л. требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4 л, т. е. разлить воду поровну в ведро и большую кастрюлю. Ситуацию в каждый момент можно описать тремя числами, где А-количество литров воды в ведре, Б- в большой кастрюле, В - в меньшей. В начальный момент ситуация описывалась тройкой чисел (8, 0, 0), от нее мы можем перейти в одну из двух ситуаций: (3, 5, 0),если наполним водой большую кастрюлю, или (5,0, 3), если наполним меньшую кастрюлю. В результате получаем два решения: одно в 7 ходов, другое в 8 ходов.
Рассмотрим задачи, которые можно легко решить, начертив граф.
Задача №1. Андрей, Борис, Виктор и Григорий играли в шахматы. Каждый сыграл с каждым по одной партии. Сколько партий было сыграно?
Задача решается с помощью полного графа с четырьмя вершинами А, Б, В, Г, обозначенными по первым буквам имён каждого из мальчиков. В полном графе проводятся всевозможные рёбра. В данном случае отрезки-рёбра обозначают сыгранные шахматные партии. Из рисунка видно, что граф имеет 6 рёбер, значит, и партий сыграно 6 партий.
Ответ: 6 партий.
Задача №2. Андрей, Борис, Виктор и Григорий подарили на память друг другу свои фотографии. Причём каждый мальчик подарил каждому из своих друзей по одной фотографии. Сколько всего фотографий было подарено?
Решение найдётся легко, если начертить граф:
1 способ. С помощью стрелок на рёбрах полного графа показан процесс обмена фотографиями. Очевидно, что стрелок в 2 раза больше, чем рёбер, т.е. 12.
2 способ. Каждый из 4 мальчиков подарил друзьям 3 фотографии, следовательно, всего было подарено 3 4=12 фотографий.
Ответ: 12 фотографий.
Задача № 3. Известно, что у каждой из трех девочек фамилия начинается с той же буквы, что и имя. У Ани фамилия Анисимова. У Кати фамилия не Карева, а у Киры – не Краснова. Какая фамилия у каждой из девочек?
Решение:По условию задачи составим граф, у которого вершины – имена и фамилии девочек. Сплошная линия будет обозначать, что девочке соответствует данная фамилия, а пунктирная – что не соответствует. Из условия задачи видно, что у Ани фамилия Анисимова (соединяем сплошной линией две соответствующие точки). Из этого следует, что у Кати и у Киры фамилия не Анисимова. Так как Катя – не Анисимова и не Карева, значит она Краснова. Остается, что у Киры фамилия Карева. Ответ: Аня Анисимова, Катя Краснова, Кира Карева.
Граф - это совокупность объектов со связями между ними. Объекты представляются как вершины, или узлы графа (они обозначаются точками), а связи - как дуги, или рёбра. Если связь однонаправленная обозначается на схеме линиями со стрелками, если связь между объектами двусторонняя обозначается на схеме линиями без стрелок. Основное направление работы с комбинаторными задачами – это переход от осуществления случайного перебора вариантов к проведению системного перебора. Задачи данного вида нагляднее решать при помощи графа.
Многие логические задачи легче решать при помощи графов. Графы позволяют наглядно представить условие задачи, а значит, значительно упростить её решение.
Задача № 4.Поступающий на физмат должен сдать три вступительных экзамена по десятибалльной системе. Сколькими способами он может сдать экзамены, чтобы быть принятым в университет, если проходной балл в тот год составил 28 баллов?
Решение. Для решения этой задачи, как и во многих других комбинаторных и вероятностных задачах, эффективным оказывается организация элементов анализируемого множества в виде дерева. От одной выделенной вершины проводятся ребра, соответствующие оценке на первом экзамене, а затем к их концам добавляются новые ребра, соответствующие возможным результатам второго экзамена, а затем и третьего.
Таким образом, для поступления на физмат можно сдать вступительные экзамены 10 различными способами.
Граф-дерево назван так за внешнее сходство с деревом. С помощью графа-дерева подсчет вариантов гораздо легче производить. Также вычерчивать дерево вариантов полезно, когда требуется записать все существующие комбинации элементов.
Задача № 5. На одном далеком острове живут два племени: рыцарей (которые всегда говорят правду) и плутов (которые всегда лгут). Один мудрец-путешественник рассказал такую историю. «Приплыв на остров, я встретил двух местных жителей и захотел узнать, из какого они племени. Я спросил первого: «Вы оба рыцари?». Не помню, ответил он «да» или «нет», но по его ответу я не смог однозначно определить кто из них кто. Тогда я спросил у того же жителя: «Вы из одного племени?». Опять-таки, не помню, ответил он «да» или «нет», но после этого ответа я сразу догадался, кто из них кто». Кого же встретил мудрец?
П
Решение:Р
Р
нет
да
да
да
да
да
нет
нет
да
да
да
2
Ответ: первый ответ - "да", второй ответ - "нет" - мудрец встретил двух плутов.
Заключение. Приложение теории графов в различных областях науки и техники.
Инженер чертит схемы электрических цепей.
Химик рисует структурные формулы, чтобы показать, как в сложной молекуле с помощью валентных связей соединяются друг с другом атомы. Историк прослеживает родословные связи по генеалогическому дереву. Военачальник наносит на карту сеть коммуникаций, по которым из тыла к передовым частям доставляется подкрепление.
Социолог по сложнейшей диаграмме показывает, как подчиняются друг другу различные отделы одной огромной корпораций.
Что общего во всех этих примерах? В каждом из них фигурирует граф.
На языке теории графов формируются и решаются многие технические задачи, задачи из области экономики, социологии, менеджмента и т.д. Графы используются для наглядного представления объектов и связи между ними
К теории графов также относится целый ряд математических проблем, не решенных на сегодняшний день.
Литература.
«Энциклопедия для детей. Т.11. Математика» /Глав.ред. М.Д.Аксёнова/ Издательский центр «Аванта+», 1998.
«За страницами учебника математики» Сост. С. А. Литвинова. -2-е изд., дополненное. – М.:Глобус, Волгоград: Панорама, 2008.
Графы // Квант. -1994.- № 6.
Математические головоломки и развлечения. М. Гарднер. – М.: «Мир», 1971.
Зыков А.А. Основы теории графов М.: Вузовская книга, 2004.
Мельников О.И. Занимательные задачи по теории графов Издательство: ТетраСистемс, 2001.
Берж К. Теория графов и ее приложения. М.: ИЛ, 1962.
Материалы из Википедии - свободной энциклопедии.
Выполнила: Мухина Анна, ученица 9А класса
Руководитель: Колчанова Г.Р.
учитель математики
Метод графов очень важен и широко
Метод графов очень важен и широко
применяется в различных областях науки и
жизнедеятельности человека.
жизнедеятельности человека.
Решение многих математических задач
упрощается, если удается использовать
графы. Представление данных в виде графа
придает им наглядность и простоту.
также упрощаются, приобретают
убедительность, если пользоваться графами.
Многие математические доказательства
Цель: рассмотреть решение задач с
использованием «Граф», рассмотреть
«Графы» на примерах алгоритмов и
родословных деревьев
Задачи:
Изучить научно- популярную литературу по
Проанализировать результаты проведенных
данному вопросу.
экспериментов
Граф - система, которая интуитивно может быть рассмотрена
как множество кружков и множество соединяющих их. Кружки
называются вершинами графа, линии со стрелками - дугами,
без стрелок -ребрами.
Начало теории графов датируют 1736 г., когда Л. Эйлер решил
популярную в то время «задачу о кенигсбергских мостах».
Термин «граф» впервые был введен спустя 200 лет (в 1936 г.) Д. Кенигом.
Математические графы с дворянским титулом «граф» связывает общее
Графами являются алгоритмы программ для ЭВМ, сетевые графики
строительства, где вершины – события, означающие окончания работ на
некотором участке, а ребра, связывающие эти вершины, - работы, которые
возможно начать по совершении одного события и необходимо выполнить для
совершения следующего.
происхождение от латинского слова «графио» - пишу. Типичными графами
являются схемы авиалиний, которые часто вывешивается в аэропортах, схемы
метро, а на географических картах – изображение железных дорог.
Выбранные точки графа называются его вершинами, а соединяющие их линии
– ребрами.
Слово «дерево» в теории графов означает граф, в котором нет циклов, то есть
в котором нельзя из некоторой вершины пройти по нескольким различным
ребрам и вернуться в ту же вершину.
Город Кенигсберг расположен на
берегах реки Прегель и двух
островах. Различные части города
были соединены семью мостами. По
воскресеньям горожане совершали
прогулки по городу. Вопрос: можно
ли совершить прогулку таким
образом, чтобы, выйдя из дома,
вернуться обратно, пройдя в
точности один раз по каждому мосту.
Мосты через реку Прегель
расположены как на рисунке.
Рассмотрим граф, соответствующий
схеме мостов
Чтобы ответить на вопрос задачи,
достаточно выяснить, хотя бы из
одной вершины выходит четное
число мостов.
Нельзя, прогуливаясь по городу,
пройти по одному разу все мосты и
вернуться обратно.
Рассмотрим задачу о поиске выхода
из лабиринта, коридоры которого не
возникает, например, при блуждании
обязательно находятся на одном
уровне. Подобная ситуация
в пещерах или катакомбах.
Корт
На рисунке изображен интересный
пример лабиринта в саду Хемптон
Построим соответствующий ему
граф. Коридоры лабиринта – это
ребра графа, а перекрестки, тупики,
входы и выходы – это вершины.
Теперь хорошо видно, что в центр
лабиринта можно попасть, следуя по
И, соответственно, выйти из центра
следующим вершинам:
1 - 4 - 7 - 10 - 9 - 11 - 12 - 13.
лабиринта по маршруту:
13 - 12 - 11 - 9 - 10 - 7 - 4 - 1.
Подробнее графы мы рассмотрим на двух
примерах:
Алгоритмы
Родословные деревья
