Тайны граф в

Обучающее занятие по теории графов Выполнили: ученики 8 «А» класса МОУ гимназии «Дмитров» Руководитель: Москевич Л.В.

А) Б) Перерисовать рисунки в тетрадь и другим цветом их обрисовать, не отрывая карандаша от бумаги и не проводя дважды ни по одной линии.

А)Б) Q(3) н R(3) н T(4) ч K(3) н S(3) н F(2) ч О(4) ч D(3) нА(3) н С(4) ч B(4) ч Обозначьте точки пересечений, а в скобках напишите, сколько линий выходит из той или иной точки пересечений, если четное, то поставить «ч», если – нечетное – «н».

А) В)Б) Г) Е) Д) Перерисуйте фигуры, обозначьте, как и в предыдущем случае и попытайтесь обрисовать их не отрывая карандаш от бумаги и не проводя дважды ни одной линии.

В каком случае можно обрисовать фигуры не отрывая карандаш от бумаги и не проводя дважды ни одной линии, а в каком случае нет? Гипотеза: Фигуру можно нарисовать, не отрывая карандаш от листа и не проводя дважды ни по одной линии, если она содержит не более двух точек, из которых выходит нечетное число линий.

Кенигсберг и его мосты Город стоит на берегах реки Прегили и состоит из четырех частей, соединенных между собой семью мостами. План города схематически изображен на рисунке. Некоторые из любопытных жителей Кенигсберга заинтересовались, можно ли обойти все семь мостов, не переходя ни по одному из них дважды.

Слайд 4 Схема мостов Кёнигсберга Подсказка: Данный рисунок преобразуйте в схему, состоящую из точек и линий и сделайте вывод о возможности решения задачи. Задача: найти маршрут, проходящий по всем четырем участкам суши по одному разу. При этом через каждый из мостов можно проходить только один раз, а конец и начало пути должны совпасть.

Леонард Эйлер ( гг.)

Леонард Эйлер

Идеальный математик 18 века

Читайте Эйлера: он наш общий учитель П. С. Лаплас

В 1736 году Эйлер нашел решение головоломки, носящей название «проблема кёнигсбергских мостов».

Эйлер взял план города и заменил его упрощенной схемой, на которой части города изображены точками (узлами), а мосты - линиями (ребрами).

Чтобы существовал маршрут, позволяющий обойти ровно по одному разу все мосты, каждая точка на схеме должна принадлежать четному числу линий. Это связано с тем, что в середине обхода путешественник, проходя какую-то из частей города, должен войти в нее по одному мосту, а выйти по другому. Из этого правила существуют лишь два исключения: когда путешественник начинает или завершает обход. В самом начале обхода путешественник покидает некую часть города, и для выхода из нее необходим только один- единственный мост. Если обход начинается и заканчивается в различных частях города, то число мостов, ведущих к каждой из них нечетно. Но если обход начинается и заканчивается в одной и той же части города, то соответствующая ей точка на схеме, как и все другие точки, должна принадлежать четному числу линий (т.е. эта часть города должна быть соединена с другими частями четным числом мостов).

Эйлер заключил, какой бы ни была сеть мостов, обойти все мосты, побывав на каждом по одному и только одному разу, можно только в том случае, если все части города соединены с другими четным числом мостов или если ровно две части города соединены с другими частями нечетным числом мостов. В Кенигсберге город подразделяется всего на четыре части, - и все они соединены с другими частями нечетным числом мостов. На схеме Кенигсберга три точки принадлежат трем линиям, а одна - пяти линиям. Тем самым Эйлер не только сумел объяснить, почему все семь кёнигсбергских мостов невозможно обойти, побывав на каждом один и только один раз, но и придумал правило, применимое к любой сети мостов в любом городе мира.

Понятие «Граф» Граф- это схема, состоящая из точек (вершины графа) и соединяющих эти точки отрезков прямых или кривых (ребра графа) Степенью вершины графа называется число ребер графа, которым принадлежит эта вершина.

Слайд 9 Если вершина графа не соединена с другими вершинами отрезками, ее называют изолированной

Граф может быть: нулевым (без ребер); неполным(с отражением не всех возможных ребер); полным ( с отражением всех ребер). Количество ребер полного графа, имеющего n вершин равно: n(n-1)/2

Совокупность ребер (вместе с вершинами, которые они соединяют), которые дополняют неполный граф до полного называют дополнением графа.

Ребра графа могут изображаться как прямыми, так и кривыми линиями, а точки могут располагаться произвольно. На слайде изображен один и тот же граф.

Задание: 1)Нарисовать граф с пятью вершинами и пятью ребрами (3 различных варианта). 2)Нарисовать граф с четырьмя вершинами и пятью ребрами так, что бы одна вершина была изолированной.

а) б) в) д) г) е) Найти три пары одинаковых графов

В1 А4 А2 А3 А1 В2 В6 В5 В4 В3 Эйлеров путь так называется путь в графе, проходящий по каждому ребру графа ровно один раз Если начало и конец эйлерова пути совпадают, то он называется эйлеровым циклом, а такой граф называется эйлеровым графом.

Граф будет иметь эйлеров цикл, если все его вершины имеют четную степень или граф содержит две нечетные вершины. Если же в графе количество нечетных вершин больше двух, то такой граф не обладает ни эйлеровым циклом, ни эйлеровым путем, его нельзя изобразить одним росчерком, не проходя дважды по одному и тому же ребру Фигура (граф), которую можно начертить не отрывая карандаш от бумаги, называется уникурсальной

Найти на рисунке графы, которые обладают эйлеровым циклом, эйлеровым путем, не обладают ни эйлеровым циклом, ни эйлеровым путем. А) Б) Г) В)

А) Б) В)Г) Можно ли обойти графы и если можно, то с какой вершины начинать обход и какая окажется в конце пути?

Если все вершины графа имеют четную степень, то обход возможен, и начать этот обход можно с любого участка. Если же из этих вершин две нечетные, то можно совершить обход, но только начало обхода должно быть взято в одной из этих двух нечетных вершин, а конец обхода будет во второй нечетной вершине.

Применение графов Примеры графов: схема автомобильных дорог, т.е. множество городов (вершины графа), и соединяющие их дороги (ребра графа); элементы электрической схемы и провода, соединяющие их. В виде графа можно представить городской метрополитен, вершинами которого являются станции, а ребрами пути, соединяющие соседние станции (одна из задач: указать какой-либо маршрут от станции А к станции В).

Задача: Винни-Пух решил навестить своих друзей: Пятачка, Кролика и Иа-Иа. Ему обязательно нужно побывать у каждого из своих друзей и вернуться домой. Если он к кому-то не зайдет, то его друг обидится. Но вы же знаете Винни-Пуха: он не любит длительных путешествий. Помогите ему выбрать кратчайший путь, если известно, как расположены домики друзей и на каком расстоянии они находятся друг от друга:

Дано: Иа-Иа (О) Винни-Пух (В) Пятачок (П) Кролик (К) Найти кратчайший путь Алгоритм решения: 1. Построить граф, используя условие задачи, и расставить на нем расстояния.

Выписать оставшиеся варианты и подсчитать расстояния: В-К-П-И-В= =195; В-К-И-П-В= =200; В-И-К-П-В= =165. Определить пары симметричных вариантов (симметричные варианты – это, например, пути В-К-П-И-В и В-И-П-К-В) и вычеркнуть на графе один вариант из каждой пары. Ответ: самый короткий путь Винни-Пуха: В-И-К-П-В=165

Задача. Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано? Нулевой граф с пятью вершинами Полный граф, соответствующий всем совершенным рукопожатиям.

Количество ребер в полном графе с n вершинами определяется как число неупорядоченных пар, составленных из всех n точек-ребер графа, т. е. как число сочетаний из n элементов по 2: n(n-1)/2 Если подсчитать число ребер графа, изображенного на рисунке, то это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми. n(n-1)/2, n=5, 5*(5-1)/2 = 10 Ответ: 10.

Закономерности Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа. Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа. Эта закономерность справедлива не только для полного, но и для любого графа. Число нечетных вершин любого графа четно

Задача Может ли в государстве, в котором из каждого города выходит 3 дороги, быть ровно 100 дорог?

Решение: Если в государстве k городов(вершин), то сумма степеней всех вершин равна 3k, и равна удвоенному произведению числа ребер – 2r. Отсюда число ребер (дорог) - 3k/2. Это число не может быть равно 100.

Задача В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 - по 4 друга, а 10 - по 5 друзей?

Решение Если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 - степень 4, 10 - степень 5. Однако у такого графа 19 нечетных вершин, что противоречит теореме «Число нечетных вершин любого графа четно»

Задача Муха забралась в банку из- под сахара. Банка имеет форму куба. Сможет ли муха последовательно обойти все 12 ребер куба, не проходя дважды по одному ребру. Подпрыгивать и перелетать с места на место не разрешается.

Решение Ребра и вершины образуют граф, все 8 вершин которого имеют степень 3. Следовательно, требуемый условием обход невозможен.

Связные графы. Две вершины графа называются связными, если в графе существует путь с концами в этих вершинах. Если такого пути не существует, вершины называются не связными. Граф называется связным, если любая пара его вершин связная. Граф называется несвязным, если в нем есть хотя бы одна несвязная пара вершин.

Ребро в теории графов, после удаления которого, граф из связного превращается в несвязный, называется мостом.

Деревья Деревом называется любой связный граф, не имеющий циклов. Договорились считать «деревом» и всякий граф, состоящий из одной (изолированной) вершины. Вершина дерева, имеющая степень единицу, называется висячей вершиной

Свойство Для каждой пары вершин дерева существует единственный путь, их соединяющий. Всякое ребро в дереве является мостом. Действительно, после удаления любого ребра дерева, оно «распадается» на два дерева.

"Множество элементов" Лист бумаги Плюшкин разрезал на 3 части. Некоторые из полученных листов он также разрезал на три части. Несколько новых листиков он вновь разрезает на три более мелкие части и т.д. Сколько Плюшкин получает листков, если разрезает k листков?

Решение: Листки бумаги обозначим на рисунке кружками. Кружки, соответствующие листам, которые разрезаются, закрасим синим; остальные кружки - красным. На рисунке видно, что при разрезании одного листа на 3 части число листков увеличивается на два. Если же разрезано k листков, то образовалось 1+ 2k листов Ответ: образовалось 1+ 2k листов

"Наибольшее и наименьшее число элементов". Город имеет в плане вид прямоугольника, разбитого на клетки: n улиц параллельны друг другу, m других пересекаются под прямым углом. На улицах города – но не на перекрестках – стоят милиционеры. Каждый милиционер сообщает номер проходящего мимо него автомобиля, направление его движения и время, когда он проехал. Какое наименьшее число милиционеров нужно расставить на улицах, чтобы по их показаниям можно было однозначно восстановить путь любого автомобиля, едущего по замкнутому маршруту (маршрут не проходит по одному и тому же участку улицы дважды)?

Решение: Если милиционеры расставлены требуемым образом, то вся сетка улиц распадается на какое-то число k кусков, не содержащих замкнутых маршрутов (циклов), - иначе найдется цикл, по которому можно проехать не будучи замеченным ни одним милиционером. Если оставшийся кусок сетки содержит р перекрестков то в нем содержится ровно р – 1 отрезков улиц. Так как перекрестков всего m n, то число отрезков, на которых нет милиционеров, равно mn – k. Общее число отрезков улиц равно 2mn – m – n. Таким образом, число занятых отрезков равно Наименьшее число милиционеров равно (m-1)(n-1). mn – m – n + k (n – 1)(m – 1).

Проверь себя:

Домашнее задание 1)Составить алгоритм решения задач в которых необходимо обойти фигуру «одним росчерком». 2)Ответить на вопрос: можно ли фигуру, изображенную на рисунке нарисовать одним росчерком? Решить с помощью графа. (рис.1) 3)Добавьте два моста так, чтобы получившуюся схему можно было обойти, побывав на каждом мосту ровно один раз и вернувшись в исходную точку. (рис.2) рис.1 рис.2

Литература Генкин С.А., И.В. Итенберг, Д.В. Фомин. Ленинградские математические кружки: пособие для внеклассной работы. Киров, издательство «АСА», стр. Гуцанович С.А. Занимательная математика в базовой школе: Пособие для учителей.-Мн.: Тетра Системс, стр. Заесенок В.П. Графы в математике и в жизни/Программа интеллектуального развития учащихся/ Выпуск 6/Инновационно- образовательный центр-М стр.