Граф, связный граф, представление задачи с помощью графа.
Урок предмета Вероятность и статистика в 10 классе
Тема урока:
Граф, связный граф, представление задачи с помощью графа.
Обучающая цель:
Ознакомить с теорией графов, показать ее прикладной характер, расширить теоретические знания в области математики, научить использовать логические приемы анализа, обобщения,.
Развивающая цель:
Развивать интерес к предмету, логическое мышление, внимательность, самостоятельность при выполнении логических заданий.
Воспитательная цель:
Показать значимость знаний, возможность их применения на практике, формирование у обучающихся социальной активности.
Задачи:
1. Основные понятия теории графов и способы представления.
2. История возникновения теории графов.
3. Изучить понятия: маршрут, цепь (простая цепь), цикл (простой цикл) графа.
4. Познакомиться с определением эйлерового цикла, эйлеровой цепи.
5. Применение теории графов.
Ход урока
Организационный момент: готовность к уроку, постановка целей и задач урока.
Основные понятия теории графов и способы представления.
Многое из нашей повседневной жизни можно смоделировать при помощи графов. Например, нарисовать для маршрута автобуса схему: отметить точками остановки, а линиями — куда едет автобус. В переводе с греческого граф — «пишу», «описываю». В современном мире граф описывает отношения. И наоборот: любое отношение можно описать в виде графа. Теория графов широко применяется в решении экономических и управленческих задач, в программировании, химии, конструировании и изучении электрических цепей, коммуникации, психологии, социологии, лингвистике и в других областях.
Для чего строят графы: чтобы отобразить отношения на множествах. По сути, графы помогают визуально представить всяческие сложные взаимодействия: аэропорты и рейсы между ними, разные отделы в компании, молекулы в веществе.
Пример.
Пусть множество A = {a1, a2, ... an} — это множество людей, и каждый элемент отображен в виде точки. Множество B = {b1, b2, ... bm} — множество связок (прямых, дуг или отрезков).
На множестве A зададим отношение знакомства между людьми из этого множества. Строим граф из точек и связок. Связки будут связывать пары людей, знакомых между собой.
Число знакомых у одних людей может отличаться от числа знакомых у других людей, некоторые могут вовсе не быть знакомы (такие элементы будут точками, не соединёнными ни с какой другой). Так получился граф:
Граф — это геометрическая фигура, которая состоит из точек и линий, которые их соединяют. Точки называют вершинами графа, а линии — ребрами.
-Два ребра называются смежными, если у них есть общая вершина.
-Два ребра называются кратными, если они соединяют одну и ту же пару вершин.
-Ребро называется петлей, если его концы совпадают.
-Степенью вершины называют количество ребер, для которых она является концевой (при этом петли считают дважды).
-Вершина называется изолированной, если она не является концом ни для одного ребра.
-Вершина называется висячей, если из неё выходит ровно одно ребро.
-Граф без кратных ребер и петель называется обыкновенным.
-Лемма о рукопожатиях:
В любом графе сумма степеней всех вершин равна удвоенному числу ребер.
Из леммы о рукопожатиях следует: в любом графе число вершин нечетной степени — четно.
Пример 1. В классе 30 человек. Может ли быть так, что у 9 из них есть 3 друга в этом классе, у 11 — 4 друга, а у 10 — 5 друзей? Учесть, что дружбы взаимные.
Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 — со степенью 4, 10 — со степенью 5. Однако у такого графа 19 нечетных вершин, что противоречит следствию из леммы о рукопожатиях.
Пример 2. Каждый из 102 учеников одной школы знаком не менее чем с 68 другими. Доказать, что среди них найдутся четверо ребят с одинаковым числом знакомых.
Решение: Сначала предположим противоположное. Тогда для каждого числа от 68 до 101 есть не более трех человек с таким числом знакомых. С другой стороны, у нас есть ровно 34 натуральных числа, начиная с 68 и заканчивая 101, а 102 = 34 * 3. Это значит, что для каждого числа от 68 до 101 есть ровно три человека, имеющих такое число знакомых. Но тогда количество людей, имеющих нечетное число знакомых, нечетно. Противоречие.
История возникновения теории графов.
Учение о графах, т.е. о геометрических схемах, представляющих собой системы линий, соединяющих какие-то заданные точки, было зарождено в XVII веке и было связано с математическими развлечениями и головоломками.
Основы теории графов как математической науки заложил в 1736 г. Леонард Эйлер, рассматривая задачу о кенигсбергских мостах. Сегодня эта задача стала классической.
Задача о Кенигсбергских мостах:
Бывший Кенигсберг (ныне Калининград) расположен на реке Прегель. В пределах города река омывает два острова. С берегов на острова были перекинуты мосты. Старые мосты не сохранились, но осталась карта города, где они изображены. Кенигсбергцы предлагали приезжим следующую задачу: пройти по всем мостам и вернуться в начальный пункт, причём на каждом мосту следовало побывать только один раз.
Решение: Пройти по Кенигсбергским мостам, соблюдая заданные условия, нельзя. Прохождение по всем мостам при условии, что нужно на каждом побывать один раз и вернуться в точку начала путешествия, на языке теории графов выглядит как задача изображения «одним росчерком» графа.
Но, поскольку граф на этом рисунке имеет четыре нечетные вершины, то такой граф начертить «одним росчерком» невозможно.
Изучить понятия: маршрут, цепь (простая цепь), цикл (простой цикл) графа.
Путем или цепью в графе называют конечную последовательность вершин, в которой каждая вершина (кроме последней) соединена со следующей в последовательности вершин ребром.
Циклом называют путь, в котором первая и последняя вершины совпадают.
Путь или цикл называют простым, если ребра в нем не повторяются.
Если в графе любые две вершины соединены путем, то такой граф называется связным.
Можно рассмотреть такое подмножество вершин графа, что каждые две вершины этого подмножества соединены путем, а никакая другая вершина не соединена ни с какой вершиной этого подмножества.
Каждое такое подмножество, вместе со всеми ребрами исходного графа, соединяющими вершины этого подмножества, называется компонентой связности.
Один и тот же граф можно нарисовать разными способами. Вот, например, два изображения одного и того же графа, которые различаются кривизной:
Познакомиться с определением эйлерового цикла, эйлеровой цепи.
Маршрутом длины n в неориентированном графе называется последовательность ребер . Одни и те же ребро и вершина могут встречаться в маршруте несколько раз.
Маршрут называют цепью, если все его ребра различны.
Цепь в графе, содержащая все его ребра, называется эйлеровой цепью.Эйлерова цепь, являющаяся циклом, называется эйлеровым циклом. Граф, обладающий эйлеровым циклом, называется эйлеровым.
Эйлеров граф отличен тем, что в нем можно обойти все вершины и при этом пройти одно ребро только один раз. В нём каждая вершина должна иметь только чётное число рёбер.
В каком случае можно обрисовать фигуры не отрывая карандаша от бумаги и не проводя дважды ни одной линии, а в каком случае нет?
- Если все вершины графа четные, то нарисовать фигуру возможно, и начать можно с любой вершины.
-Если же из этих вершин две нечетные, то нарисовать фигуру можно, но только начинать необходимо в одной из этих двух нечетных вершин, а заканчивать во второй нечетной вершине.
Вывод:
Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них.
Пример 1:
Пример 2:
Каждая вершина этого графа имеет чётную степень, поэтому этот граф — эйлеров. Обход рёбер в алфавитном порядке даёт эйлеров цикл.
Взвешенный граф
Взвешенным графом называется граф, вершинам и/или ребрам которого присвоены «весы» — обычно некоторые числа. Пример взвешенного графа — транспортная сеть, в которой ребрам присвоены весы: они показывают стоимость перевозки груза по ребру и пропускные способности дуг.
Графы-деревья
Деревом называется связный граф без циклов. Любые две вершины дерева соединены лишь одним маршрутом.
Граф, состоящий из компонент дерева, называется лесом.
Теория графов и современные прикладные задачи
На основе теории графов создали разные методы решения прикладных задач, в которых в виде графов можно моделировать сложные системы. В этих моделях узлы содержат отдельные компоненты, а ребра отражают связи между компонентами.
Применение теории графов.
В построении графов расположение точек не обязательно должно совпадать с расположением объектов, которые эти точки обозначают. Важно, чтобы они правильно отражали связи между этими объектами.
С помощью графа можно очень удобно изобразить схему дорог между городами, автобусных маршрутов, линий метро, телефонная и мобильная связь и т.д.
Решение задач:
Задача 1.
Между девятью планетами Солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам:
Земля-Меркурий
Плутон- Венера
Земля – Плутон
Плутон – Меркурий
Меркурий – Венера
Уран – Нептун
Нептун – Сатурн
Сатурн – Юпитер
Юпитер – Марс
Марс – Уран
Можно ли долететь на рейсовых ракетах с Земли до Марса?
Решение:
Задача 2.
Аркадий, Борис, Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?
Решение: Пусть каждому из молодых людей соответствует точка на плоскости, названная по первой букве имени, а произведенные рукопожатия – отрезок или кривая линия, которая будет соединять точки, соответствующие именам.
Вывод урока:
Графы – это замечательные математические объекты, с помощью, которых можно решать математические, экономические и логические задачи. Также можно решать различные головоломки и упрощать условия задач.
Теория графов применяется в таких областях, как экономика, психология, лингвистика, биология, химия, схемотехника и пр. Графы используются при составлении карт и иерархических древ.
В математике даже есть специальный раздел, который так и называется: «Теория графов».
Домашнее задание:
Задача 1. Можно ли нарисовать, не отрывая карандаш от бумаги и не проходя ни по какому отрезку дважды, фигуры вида а), б), в), г), д), е), ж), з), и). (см. рис.).
Задача 2.
