Задачи на построение графов: Математическое Бюро. Страница 404

Содержание

Графы. Применение графов к решению задач

1. Методические рекомендации к теме “Графы”.

Понятие графа целесообразно вводить после того, как разобрано несколько задач, подобных задаче 1, решающее соображение в которых – графическое представление. Важно, чтобы ученики сразу осознали, что один и тот же граф может быть нарисован разными способами. Строгое определение графа, на мой взгляд, давать не нужно, т.к. оно слишком громоздко и это только затруднит обсуждение. На первых порах хватит и интуитивного понятия. При обсуждении понятия изоморфизма можно решить несколько упражнений на определение изоморфных и неизоморфных графов. Одно из центральных мест темы – теорема о четности числа нечетных вершин. Важно, чтобы ученики до конца разобрались в ее доказательстве и научились применять к решению задач. При разборе нескольких задач рекомендую не ссылаться на теорему, а фактически повторять ее доказательство. Чрезвычайно важно также понятие связности графа. Содержательным соображением здесь является рассмотрение компоненты связности, на это необходимо обратить особое внимание.

Эйлеровы графы – тема почти игровая.

Первая и главная цель, которую нужно преследовать при изучении графов, –научить школьников видеть граф в условии задачи и грамотно переводить условие на язык теории графов. Не стоят рассказывать обе всем на нескольких занятиях подряд. Лучше разнести занятия по времени на 2–3 учебных года. (Прилагается разработка занятия “Понятие графа. Применение графов к решению задач” в 6 классе).

2. Теоретический материал к теме “Графы”.

Введение

Графы – замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач. В математике существует целый раздел – теория графов, который изучает графы, их свойства и применение. Мы же обсудим только самые основные понятия, свойства графов и некоторые способы решения задач.

Понятие графа

Рассмотрим две задачи.

Задача 1. Между девятью планетами солнечной системы установлено космическое сообщение. Рейсовые ракеты летают по следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ?

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

Теперь сразу видно, что долететь с Земли до Марса нельзя.

Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4×4 убрать угловые клетки.

Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу ?

Решение: Занумеруем последовательно клетки доски:

А теперь с помощью рисунка покажем, что такой обход таблицы, как указано в условии, возможен:

Мы рассмотрели две непохожие задачи. Однако решения этих двух задач объединяет общая идея – графическое представление решения. При этом и картинки, нарисованные для каждой задачи, оказались похожими: каждая картинка – это несколько точек, некоторые из которых соединены линиями.

Такие картинки и называются графами. Точки при этом называются вершинами, а линии – ребрами графа. Заметим, что не каждая картинка такого вида будет называться графом. Например. если вас попросят нарисовать в тетради пятиугольник, то такой рисунок графом не будет. Будем называть что рисунок такого вида, как в предыдущих задачах, графом, если есть какая-то конкретная задача для которой такой рисунок построен.

Другое замечание касается вида графа. Попробуйте проверить, что граф для одной и той же задачи можно нарисовать разными способами; и наоборот для разных задач можно нарисовать одинаковые по виду графы. Здесь важно лишь то, какие вершины соединены друг с другом, а какие – нет. Например, граф для задачи 1 можно нарисовать по-другому:

Такие одинаковые, но по-разному нарисованные графы, называются изоморфными.

Степени вершин и подсчет числа ребер графа

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

С понятием степени вершины связана одна из основных теорем теории графов –теорема о честности числа нечетных вершин. Докажем ее мы немного позднее, а сначала для иллюстрации рассмотрим задачу.

Задача 3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими ?

Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным . Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.

Ответ. Соединить телефоны таким образом невозможно.

Теорема: Любой граф содержит четное число нечетных вершин.

Доказательство: Количество ребер графа равно половине суммы степеней его вершин. Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной. А это возможно только в том случае, если граф содержит четное число нечетных вершин.

Связность графа

Есть еще одно важное понятие, относящееся к графам – понятие связности.

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

Задача 4. В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города модно добраться в любой другой.

Доказательство: Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам:

Теперь явно видно, что мы получили не менее различных 16 городов, что противоречит условию задачи. Значит утверждение доказано от противного.

Если принять во внимание предыдущее определение, то утверждение задачи можно переформулировать и по-другому: “Доказать, что граф дорог страны Семерка связен.

”

Теперь вы знаете, как выглядит связный граф. Несвязный граф имеет вид нескольких “кусков”, каждый из которых – либо отдельная вершина без ребер, либо связный граф. Пример несвязного графа вы видите на рисунке:

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

Задача 5. В Тридевятом царстве только один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов, – по 20. Докажите, что из столицы можно долететь в город Дальний.

Доказательство: Понятно, что если нарисовать граф ковролиний Царства, то он может быть несвязным. Рассмотрим компоненту связности, которая включает в себя столицу Царства. Из столицы выходит 21 ковролиния, а из любых других городов, кроме города Дальний – по 20, поэтому, чтобы выполнялся закон о четном числе нечетных вершин необходимо, чтобы и город Дальний входил в эту же самую компоненту связности.

А так как компонента связности – связный граф, то из столицы существует путь по ковролиниям до города Дальний, что и требовалось доказать.

Графы Эйлера

Вы наверняка сталкивались с задачами, в которых требуется нарисовать какую-либо фигуру не отрывая карандаш от бумаги и проводя каждую линию только один раз. Оказывается, что такая задача не всегда разрешима, т.е. существуют фигуры, которые указанным способом нарисовать нельзя. Вопрос разрешимости таких задач также входит в теорию графов. Впервые его исследовал в 1736 году великий немецкий математик Леонард Эйлер, решая задачу о Кенигсбергских мостах. Поэтому графы, которые можно нарисовать указанным способом, называются Эйлеровыми графами.

Задача 6. Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз ?

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

Сейчас мы доказали теорему об Эйлеровых графах:

Теорема: Эйлеров граф должен иметь не более двух нечетных вершин.

И в заключение – задача о Кенигсбергских мостах.

Задача 7. На рисунке изображена схема мостов города Кенигсберга.

Можно ли совершить прогулку так, чтобы пройти по каждому мосту ровно 1 раз?

3. Задачи к теме “Графы”

Понятие графа.

1. На квадратной доске 3×3 расставлены 4 коня так, как показано на рис.1. Можно ли сделав несколько ходов конями, переставить их в положение, показанное на рис.2?

Рис. 1

Рис. 2

Решение. Занумеруем клетки доски, как показано на рисунке:

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

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

2. В стране Цифра есть 9 городов с названиями 1, 2, 3, 4, 5, 6, 7, 8, 9. Путешественник обнаружил, что два города соединены авиалинией в том и только в том случае, если двузначное число, образованное названиями городов, делится на 3. Можно ли долететь по воздуху из города 1 в город 9 ?

Решение. Поставив в соответствие каждому городу точку и соединив точки линией, если сумма цифр делится на 3, получим граф, в котором цифры 3, 5, 9 связаны между собой, но не связаны с остальными. Значит долететь из города 1 в город 9 нельзя.

Степени вершин и подсчет числа ребер.

3. В государстве 100 городов к из каждого города выходит 4 дороги. Сколько всего дорог в государстве.

Решение. Подсчитаем общее количество выходящих городов дорог – 100 ^. 4 = 400. Однако при таком подсчете каждая дорога посчитана 2 раза – она выходит из одного города и входит в другой. Значит всего дорог в два раза меньше, т.е. 200.

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

Ответ. Нет (теорема о четности числа нечетных вершин).

5. У короля 19 вассалов. Может ли оказаться так, что у каждого вассала 1, 5 или 9 соседей ?

Ответ. Нет, не может.

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

Решение. Подсчитаем число городов. Число дорог равно числу городов х, умноженному на 3 (число выходящих из каждого города дорог) и разделенному на 2 (см. задачу 3). Тогда 100 = Зх/2 => Зх=200, чего не может быть при натуральном х. Значит 100 дорог в таком государстве быть не может.

7. Докажите, что число людей, живших когда-либо на Земле и сделавших нечетное число рукопожатий, четно.

Доказательство непосредственно следует из теоремы о четности числа нечетных вершин графа.

Связность.

8. В стране из каждого города выходит 100 дорог и из каждого города можно добраться до любого другого. Одну дорогу закрыли на ремонт. Докажите, что и теперь из любого города можно добраться до любого другого.

Доказательство. Рассмотрим компоненту связности, в которую входит один из городов, дорогу между которыми закрыли. По теореме о четности числа нечетных вершин в нее входит и второй город. А значит по-прежнему можно найти маршрут и добраться из одного из этих городов в другой.

Графы Эйлера.

9. Имеется группа островов, соединенных мостами так, что от каждого острова можно добраться до любого другого. Турист обошел все острова, пройдя по каждому мосту розно 1 раз. На острове Троекратном он побывал трижды. Сколько мостов ведет с Троекратного, если турист

а) не с него начал и не на нем закончил?
б) с него начал, но не на нем закончил?
в) с него начал и на нем закончил?

10. На рисунке изображен парк, разделенный на несколько частей заборами. Можно ли прогуляться по парку и его окрестностям так, чтобы перелезть через каждый забор розно 1 раз?

Применение графов при решении задач

Задачи на вычерчивание фигур одним росчерком

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

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

Мосты через реку Прегель расположены как на рисунке.
(приложение 2 рис.1).

Рассмотрим граф, соответствующий схеме мостов

Проблема семи мостов Кёнигсберга.
Суть: можно ли пройти по 7 мостам города Кёнигсберга, не ступив на каждый более одного раза.

Решение: было найдено русско-немецким математиком Леонардом Эйлером(1736 год).

Его рассуждения заключались в следующем:

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

Задача 2. Между 9 планетами Солнечной системы введено космическое сообщение. Ракеты летают по следующим маршрутам: Земля–Меркурий, Плутон–Венера, Земля–Плутон, Плутон–Меркурий, Меркурий–Венера, Уран–Нептун, Нептун–Сатурн, Сатурн–Юпитер, Юпитер–Марс и Марс–Уран. Можно ли добраться с Земли до Марса?

Решение: Нарисуем схему: планетам будут соответствовать точки, а соединяющим их маршруты – не пересекающиеся между собой линии.

Ответ: с Земли до Марса добраться нельзя.

Логические задачи.

Задача 3. В соревнованиях по борьбе, проходящих по олимпийской системе, участвуют 20 борцов. За какое минимальное время можно провести соревнование, если в спортивном зале есть только три борцовских ковра, и на каждую схватку, включая разминку и отдых, отводится час? Изобразите схему соревнований с помощью корневого дерева.

Решение: одна из возможных схем приведена на рисунке.

(приложение 2 рис.2)

Ответ: На соревнование уйдет 7 часов.

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

Решение: Разобьем монеты на три группы по три монеты. Положим монеты двух групп на разные чашки весов.

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

Если чашки придут в равновесие, то фальшивая — третья монета. Если чашки не придут в равновесии, то фальшивая — более легкая монета.

Решение этой задачи легко изобразить в виде графа-дерева, похожего на алгоритм. (приложение 2, рис.3)

Задачи на группу знакомств
Задача 5. Однажды Андрей, Борис, Володя, Даша и Галя договорились вечером пойти в кино. Выбор кинотеатра и сеанса они решили согласовать по телефону. Было также решено, что если с кем-то созвониться не удастся, то поход в кино отменяется. Вечером у кинотеатра собрались не все, и поэтому посещение кино сорвалось. На следующий день стали выяснять, кто кому звонил. Оказалось, что Андрей звонил Борису и Володе, Володя звонил Борису и Даше, Борис звонил Андрею и Даше, Даша звонила Андрею и Володе, а Галя звонила Андрею, Володе и Борису. Кто не сумел созвониться и поэтому не пришёл на встречу?

Решение:
Нарисуем пять точек и обозначим их буквами А, Б, В, Г, Д.

Это первые буквы имён.

Соединим те точки, которые соответствуют именам созвонившихся ребят.

(приложение 2, рис.4)

Задача 6. В первенстве класса по настольному теннису 6 участников: Андрей, Борис Виктор, Галина, Дмитрий и Елена. Первенство проводят по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Андрей сыграл с Борисом, Галиной, Еленой; Борис – с Андреем, Галиной; Виктор – с Галиной, Дмитрием, Еленой; Галина – с Андреем, Виктором и Борисом. Сколько игр проведено к настоящему моменту и сколько еще осталось?

Решение: Получим, что сыграно 7 игр, а осталось – 8. Можно проверить: в графе 6 вершин тогда всего ребер 6*5/2=15 (7+8).

Логическая задача на переливание. В ведре 8 л воды, и имеется две кастрюли емкостью 5 и 3 л. Требуется отлить в пятилитровую кастрюлю 4 л воды и оставить в ведре 4 л, т. е. разлить воду поровну в ведро и большую кастрюлю.

Решение:

Ситуацию в каждый момент можно описать тремя числами (приложение рис.16).

В результате получаем два решения:

одно в 7 ходов, другое в 8 ходов.

(приложение 2, рис.5)

Задача 7. Имеется шахматная доска 3×3, в верхних двух углах стоят два чёрных коня, в нижних – два белых (рисунок ниже). За 16 ходов поставьте белых коней на место чёрных, а чёрных на место белых и докажите, что за меньшее число ходов это сделать невозможно.

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

Тогда, передвигая коней в графе, каждый раз перемещая всех коней, как показано на рисунках 1-4, мы получим за 16 ходов белых коней на месте чёрных, а чёрных на месте белых (рис.5). (приложение 2, рис.6)

Примеры задач, решаемых методом графов в приложении 3.

Перейти к разделу 2.3. Генеалогическое древо – один из способов применения теории графов

4. Решение задач с помощью графов. Мерзляк (угл.)

Онлайн. Глава 1. Линейное уравнение с одной переменной. § 4. Решение задач с помощью графов. Упражнения №№ 4.1 — 4.14. Итоги главы 1. Мерзляк, Поляков: Алгебра. Углубленный уровень: 7 класс. Учебник — М.: Вентана-Граф (Российский учебник). Электронная ознакомительная версия для покупки пособия. Цитаты из книги использованы в учебных целях.

Алгебра 7 класс Мерзляк, Поляков (угл.изуч.)

Предыдущая тема ОГЛАВЛЕНИЕ Следующая тема

§ 4. Решение задач с помощью графов.

Вы хорошо знаете, что составление уравнений — это не единственный способ решения текстовых задач. Также эффективным приёмом является «решение задач по действиям», т. е. арифметическим способом, когда в определённой последовательности находят значения числовых выражений и в конечном итоге получают ответ. Здесь переводом задачи из реальной жизни на математический язык является запись одного или нескольких числовых выражений.

Заметим, что в начальной школе именно с этого способа вы начали знакомство с методами решения текстовых задач.

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

ПРИМЕР 1. В регионе есть пять городов. Можно ли эти города связать дорогами так, чтобы из каждого города выходили: 1) четыре дороги; 2) три дороги?

Решение. Построим схему, на которой города будут изображены точками А, В, С, D и Е. Дорогу, соединяющую два города, будем изображать в виде отрезка. Например, на рисунке 4.1 показана кольцевая схема дорог.

1) Задача сводится к тому, чтобы выяснить, можно ли пять точек плоскости соединить отрезками так, чтобы из каждой точки выходили четыре отрезка. На рисунке 4.2 показано, как это сделать.

2) Предположим, что такая схема возможна. Подсчитаем, сколько отрезков будет на этой схеме. Имеем: 5*3 = 15 (отрезков). Однако при таком подсчёте каждый отрезок был учтён дважды. Получается, что количество отрезков равно 15/2. Это число не является целым. Получили противоречие.

Ответ: 1) да; 2) нет. ■

В повседневной жизни нам нередко приходится пользоваться рисунками, состоящими из точек, некоторые из которых соединены линиями. Например, на рисунке 4.3 изображена схема метрополитена Санкт–Петербурга.

Такие рисунки называют графами. Точки на рисунке называют вершинами графа, а соединяющие их линии — рёбрами графа.

На рисунке 4.4 приведены ещё несколько примеров графов.

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

Любопытно, что рисунки такого вида и дворянский титул имеют одинаковое название — граф. Это слово произошло от латинского grafito — пишу.

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

ПРИМЕР 2. Существует ли компания из 16 человек, в которой каждый дружит ровно с 6 другими людьми из этой компании?

Решение. Нарисуем 16 точек так, как показано на рисунке 4.5. Эти точки изображают 16 человек данной компании. Возьмём произвольную точку и соединим её со всеми точками, находящимися с ней на одной горизонтали или вертикали. Получили 6 рёбер графа, которые соответствуют дружеским связям. Так можно поступить с каждой из 16 точек.

Ответ: существует. ■

Количество рёбер, выходящих из вершины графа, называют степенью этой вершины. Например, степень каждой вершины, изображённой на рисунке 4.1, равна 2.

Заметим, что решение задачи 2 из примера 1 свелось к выяснению вопроса: существует ли пятивершинный граф, степень каждой вершины которого равна 3? Ответ на этот вопрос оказался отрицательным. На самом деле имеет место более общий факт: в любом графе количество вершин, степень которых нечётная, является чётным числом. Он следует из того, что сумма степеней всех вершин графа равна удвоенному количеству его рёбер, а следовательно, является чётным числом.

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

На рисунке 4.6 изображён связный граф, а граф, изображённый на рисунке 4.7, связным не является.

ПРИМЕР 3. В некотором регионе 9 городов. Из каждого города выходят 4 дороги, связывающие его с четырьмя городами этого региона. Докажите, что из любого города можно проехать в любой другой город.

Решение. Предположим, что не существует пути, соединяющего города А и В. Каждый их этих двух городов соединён с четырьмя другими (отличными от А и В).

Если город А и город В соединены с одним и тем же городом, это означает, что существует путь, соединяющий города А и В. Следовательно, чтобы такого пути не существовало, все 8 городов, с которыми соединены города А и В, должны быть различными. Добавив к ним города А и В, получаем, что количество городов в данном регионе не меньше 10, что противоречит условию задачи. Следовательно, наше предположение неверно. ■

Рассмотренный пример иллюстрирует следующий общий факт: если граф имеет n вершин и степень каждой вершины не меньше, чем (n — 1)/2, то такой граф является связным.

Воспользовавшись идеей решения задачи из примера 3, докажите этот факт самостоятельно.

ИТОГИ ГЛАВЫ 1.

Предыдущая тема ОГЛАВЛЕНИЕ Следующая тема

Ознакомительная версия для принятия решения о покупке книги: Мерзляк, Поляков: Алгебра. Углубленный уровень: 7 класс. Учебник — М.: Вентана-Граф, 2019 (Российский учебник). 4. Решение задач с помощью графов.

Граф. Решение задач с помощью графа, 6 класс

Назарбаев Интеллектуальная школа физико- математического направления

г. Кокшетау Акмолинская область

Конспект урока по информатике

в 6 классе

«Граф.

Решение задач с помощью графа».

Подготовила учитель информатики

Нурмуханова Асель Сериковна

Кокшетау

2011

Тема урока: Граф. Решение задач с помощью графа.

Цель урока: Составить представление об организации информации в виде дерева (графа). Освоить понятие граф. Научиться решать задачи с помощью графов.

Знание

Оборудование: компьютер, таблицы, карточки. Длительность урока:40 мин

План урока

I этап – Орг.момент (3 мин)

II этап – Новая тема. Понятие графа.(8 мин)

Графы являются существенным элементом математических моделей в самых разнообразных областях науки и практики. Они помогают наглядно представить взаимоотношения между объектами или событиями в сложных системах. Многие алгоритмические задачи дискретной математики могут быть сформулированы как задачи, так или иначе связанные с графами, например задачи, в которых требуется выяснить какие-либо особенности устройства графа, или найти в графе часть, удовлетворяющую некоторым требованиям, или построить граф с заданными свойствами.

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

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

Графы – это рисунки, которые состоят из точек и линий, соединяющих эти точки.

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

Точки называются вершинами графа, а линиями рёбрами.

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

У графа обязательно есть вершины.

Граф без рёбер называется пустым.

Примеры различных графов приведены на рисунке.

Дерево (граф) – это способ организации информации об отношениях между объектами.

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

Первая работа по теории графов принадлежит Леонардо Эйлеру (1736г).

Термин граф впервые ввёл 1936г Венгерский математик Денеш Кениг. Графами были названы схемы состоящие из точек и соединяющие эти точки отрезков прямых или кривых.

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

С помощью графов изображаются схемы дорог, газопроводов, тепло и электро сетей.

Графы в которых не построены все возможные рёбра называется не полными графами.

III этап. Представление информации в виде дерева. (2 мин)

Особым видом графа является дерево. Данная форма модели применяется тогда, когда элементы моделируемого объекта находятся в состоянии какого-либо подчинения и соподчинения, когда есть отношение иерархичности. Модель управления предприятием (школой, театральным коллективом и т. д.) очень удобно представлять в виде дерева.

Описать граф- это значит, ответить на вопросы:

Сколько вершин?

Есть рёбра?

Есть направление?

Все ли вершины соединены рёбрами?

На каких школьных предметах вы встречались с графами, приведите примеры?

Учитель приводит несколько примеров. Вам хорошо известно понятие «родословное дерево» и вы можете изобразить в такой форме ваши родственные отношения. Каталог файлов на диске, также как и библиотечный каталог — примеры информационных моделей в форме дерева.

IV этап.Заполнение схемы. Применение графа. (3мин)

V этап. Применение знаний и закрепление изученного. (15 мин)

Рассмотрим одну из простейших задач: «Красный, синий, желтый и зеленый карандаши лежат в четырех коробках по одному. Цвет карандаша отличается от цвета коробки. Известно, что зеленый карандаш лежит в синей коробке, а красный не лежит в желтой. В какой коробке лежит каждый карандаш?»

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

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

Задача1: Алия решила маме на день рождения подарить букет цветов (розы, тюльпаны или гвоздики) и поставить из или в вазу или в кувшин.

Сколькими способами это можно сделать.

Решение. Отметим точками цветы (РТГВК) (вершины графа)

А связи между ними -линиями между точками (рёбра графа)

По рисунку видно, что таких сопопбов — 6

* розы * тюльпан *гвоздики

* ваза *кувшин

Задача2. Ранним утром Миша Маша, Асем обменялись приветствиями каждый с каждым. Сколько всего было приветствий. Решите задачу с помощью графа. Нарисуй граф в рабочей тетради.

Задача3. Шесть футбольных команд должны сыграть матчи, каждая с каждой. Уже сыграли матчи.

А с В, Г,Е Г с А,Д,Е

Б с В,Д,Е Д с Б,Г,Е

В с А,Б Е с А,Б,Г,Д

Сколько матчей сыграно и сколько осталось сыграть.

Задача4. Мадии утром собрался в школу, но по пути он должен зайти в аптеку за лекарствами. Сколькими способами он может это сделать.

Задача5. В квартирах №1,2,3 жили три друга: Айдар, Тима и Саша. Известно, что в квартирах №1 и 2 жил не Айдар. Тима жил не в квартире №1. В какой квартире жил каждый из друзей.

Ответ:

Задача6. Арман, Мадии, Тимур, Сергей заняли на математической олимпиаде четыре первых места. Когда их спросили о распределений мест, они дали три ответа: Сергей – первый, Мади– второй, Сергей -второй, Арман – третий, Тимур – второй, Арман – четвертый. Известно, что в каждом ответе только одно утверждение верно. Как распределились места?

Ответ: С-1 Т-2 А -3 М-4.

Задача7. Григорий играли в шахматы. Каждый сыграл с каждым по одной партии. Сколько партий было сыграно?

Решение: Решим задачу с помощью полного графа с четырьмя вершинами А, Б, В, Г, обозначенными по первым буквам имен каждого из мальчиков. В полном графе проводятся всевозможные ребра.

В данном случае отрезки-ребра обозначают сыгранные шахматные партии. Из рисунка видно, что граф имеет 6 ребер, значит, и партий было сыграно 6.

Задача8.Из города А в город Б ведут две дороги, из города Б в городок В -тоже две дороги и из города А в город В – тоже две дороги. Нарисуй схему и сосчитай все возможные пути из города А в город В. Ответ: 6 партий .

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

Решение. I способ. С помощью стрелок на ребрах полного графа с вершинами А, Б, В и Г показан процесс обмена фотографиями. Очевидно, стрелок в 2 раза больше, чем ребер, т.е. 6*2 = 12. Столько же было подарено и фотографий.

II способ. Каждый из четверых мальчиков подарил друзьям 3 фотографии, следовательно, всего было роздано 3 • 4 = 12 фотографий.

О т в е т: 12 фотографий.

VI этап. Рефлексия. (5 мин)

«Почему понятие графа изучается в школьном курсе информатики?»

Дополнительные вопросы:

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

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

VII этап. Домашнее задание: Дополнить схему примерами применения графов. (1 мин)

VIII этап. Итог урока. Выставление оценок. (1 мин)

Список литературы:

1. Нагибин Ф.Ф. Применение графов для решения логических задач.

// Математика в школе. — 1964. — № 3.

2. Шедивы Я. Решение логических задач при помощи графов.

// Математика в школе. — 1967. — № 6.

3. Березина Л.Ю. Графы помогают решать логические задачи.

// Математика в школе. — 1972. — № 2.

4. Федосеев В.Н. Элементы теории вероятностей для VII—VIII классов средней школы.

// Математика в школе. — 2002. — № 4.

Ученик знает назначение графов
Понимание	Умеет приводить примеры использования графов в различных учебных предметах (химия, информатика, биология, геометрия и др. ) и повседневной жизни.
Применение	Умеет записывать арифметические выражения в виде графов, отражать информацию в виде семантической сети, изображать классификации различных объектов в виде дерева
Анализ	Умеет из множества предметов вычленить объекты, обозначить связи между ними.
Айдар	Тима	Саша
№1	—	—	+
№2	—	+	—
№3	+	—	—

Тема: «Графы и решение логических задач».

Посельский Борис учеником 8 «в» класса МБОУ «Нижнесаянтуйская СОШ»

Научный руководитель:

Кожемякина Ирина Семеновна

учитель математики

МБОУ «Нижнесаянтуйская СОШ»

2018г

Оглавление.

1. Введение

2. Глава 1.Теория графов

2.1. История возникновения графов

2.2. Задача о кёнигсбергских мостах

2.3.Граф и его элементы

2.4. Степени вершин и подсчет числа ребер

2.4. Эйлеровы графы

3. Глава 2. Решение задач с помощью графов

4. Заключение

5. Список литературы

Введение.

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

Предмет моего исследования: графы

Объект исследования: логические задачи, решаемые с помощью построения графов

Актуальность исследования: актуальность моей работы обусловлена большим интересом к теме данного исследования по математике. Кроме этого, выбранная мною тема актуальна, так как в последнее время теория графов стала простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем.

Цели моего исследования:

Выяснить особенности применения теории графов при решении логических задач и в практической деятельности.

Задачи исследования:

познакомиться с историей возникновения графов;
познакомиться с основными понятиями графа, видами, элементами;
рассмотреть решение логических задач с помощью графов;

Гипотеза:

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

Глава 1. ТЕОРИЯ ГРАФОВ

1.История возникновения теории графов.

Начало теории графов все единодушно относят к 1736 г., когда Леонард Эйлер — один из крупнейших математиков XVIII, члена Петербургской академии наук, не только решил популярную в то время задачу о кёнигсбергских мостах, но и

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

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

теорию графов, называемых деревьями, для исследования

Рис. 4 Портрет Леонарда Эйлера. электрических цепей, а математик А. Кэли в связи с

описанием строения углеводородов решил перечислительные задачи для трех видов

деревьев.

Термин «Графы» ввёл в язык немецкий математик Д. Кёниг. Он первым предложил называть такие схемы «графами». Термин «граф» (от латинского слова «графио» — пишу) приобрел права гражданства и вошел в математический язык в 1936 году, после выхода в свет монографии Кёнига, в которой впервые графы рассматриваются как самостоятельные математические объекты независимо от их конкретного содержания.

2. Задача о кёнигсбергских мостах.

Проблема семи мостов Кёнигсберга или Задача о кёнигсбергских мостах — старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Издавна жители Кёнигсберга пытались пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок.

Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.

Задача о семи мостах заинтересовала Леонарда Эйлера, о чём он написал в письме итальянскому математику и инженеру Мариони от 13 марта 1736 года. В этом письме Эйлер пишет о том, что он смог найти правило, пользуясь которым, легко определить, можно ли пройти по всем кёнигсбергским мостам, не проходя дважды ни по одному из них. Его ответ был — «нельзя».

Читая письмо Эйлера выясним, какое же правило он нашел:

«Вопрос состоит, писал Эйлер, в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, — таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре — A, B, C, D.»

Эйлеровский ход решения задачи я представлю в виде графа, где вершины — острова и берега, а ребра — мосты. Рис. 1

Построим граф без посторонних линий. Рис. 2

Читаем письмо Эйлера дальше: «Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным — по три моста. То есть нам нужно определить степень каждой вершины, и узнать какие вершины четные, а какие нечетные. Подпишем степени вершин в кружочках. И посчитаем количество нечетных вершин. Нечетные вершины: А, B, C, D.

Покажу это на графе — Рис. 3.

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

Итак, используя правило Леонардо Эйлера мы можем сделать вывод: так как количество нечетных вершин в графе равно 4, а это > 2, то обойти все кенигсбергские мосты, проходя только один раз через каждый из этих мостов нельзя.

В своей работе Эйлер доказал общее утверждение, для решения каждой подобной задачи о мостах — для того, чтобы можно было обойти все рёбра графа по одному разу и вернуться в исходную вершину, необходимо и достаточно выполнение двух условий:

Из любой вершины графа должен существовать путь по его рёбрам в любую другую вершину.
Из каждой вершины должно выходить чётное количество рёбер.

3. Граф и его элементы.

Слово «граф» в математике означает картинку, где нарисовано несколько точек, некоторые из которых соединены линиями. С дворянским титулом «граф» их связывает общее происхождение от латинского слова «графио» — пишу.

В математике определение графа дается так:

Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами.

Абсолютно неважно, какой вид имеют эти линии, и как точки расположены в пространстве. Идея графа — это набор каких-то объектов, с описанными связями между ними. В самом простом случае связь может быть, а может не быть. Приведу пример. Допустим, мы имеем группу людей. Это будут точки в графе. Мы можем описать связи между этими людьми. Например, связь — «знакомства». Если два человека знают друг друга, то между ними есть связь. На рисунке такого графа связь между ними будет обозначена линией от одного человека к другому. Вот как выглядит такой рисунок (граф):

По рисунку (графу) видно, что с Мариной никто не знаком, а Саша знаком с Олегом, Катей и Леной.

В графе точки называются вершинами графа, а соединяющие их линии (дуги) – рёбрами. Смотрим Рис. 1.

Схема графа, состоящая из «изолированных» вершин, называется нулевым графом. (рис.2)

Графы, в которых не построены все возможные ребра, называются неполными графами. (рис.3)

Графы, в которых построены все возможные ребра, называются полными графами. (рис.4)

Если на ребрах графа нанесены стрелочки, указывающие направление ребер, то такой граф называют направленным.

4. Степени вершин и подсчет числа ребер.

Количество рёбер, выходящих из вершины графа, называется степенью вершины. Вершина графа, имеющая нечётную степень, называется нечетной, а чётную степень – чётной.

Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.

рис.5

На рисунке 5 изображен граф с пятью вершинами. Степень вершины А обозначим Ст.А.
На рисунке: Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст. Г= 2, Ст. Д= 0.

Сформулируем некоторые закономерности, присущие определенным графам.

Закономерность 1.

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

Закономерность 2.

Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.

Эта закономерность справедлива не только для полного, но и для любого графа.

Теорема .

Число нечетных вершин любого графа четно.

Если полный граф имеет n вершин, то количество ребер будет равно .

Действительно, количество ребер в полном графе с n-вершинами определяется как число неупорядоченных пар, составленных из всех n-точек-ребер графа, т. е. как число

сочетаний из n по 2. Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа.

5. Эйлеровы графы.

Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. (рис.6) Такими графы названы в честь учёного Леонарда Эйлера.

Закономерность 3 (вытекает из рассмотренной нами теоремы).
Невозможно начертить граф с нечетным числом нечетных вершин.
Закономерность 4.

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

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

Закономерность 6.

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

рис.6 (Эйлеровы графы)

Глава 2. РЕШЕНИЕ ЗАДАЧ С ПОМОЩЬЮ ГРАФОВ.

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

Задача 1. В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что вода и молоко не в бутылке, сосуд с лимонадом стоит между кувшином и сосудом с квасом, в банке – не лимонад и не вода. Стакан стоит около банки и сосуда с молоком. Куда налита каждая жидкость?

	Молоко	Лимонад	Квас	Вода
Бутылка	—	+	—	—
Стакан	—	—	—	+
Кувшин	+	—	—	—
Банка	—	—	+	—

Ответ: в кувшине-молоко, в банке-квас, в стакане-вода, в бутылке-лимонад

Эту же задачу можно решить с помощью графов.

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

Тогда получаем:

В бутылке – квас или лимонад, так как в банке только квас, значит в бутылке – лимонад;

В кувшине – молоко или вода, так как в стакане не молоко, значит – вода, а кувшине тогда молоко.

Ответ: в кувшине-молоко, в банке-квас, в стакане-вода, в бутылке-лимонад

Решение задачи в графах.

Задача 2. На международном конгрессе встретились четверо ученых: физик, историк, биолог и математик. Национальности их различны и, хотя каждый из ученых владеет двумя языками их четырех (русский, английский, французский и итальянский), нет такого языка, на котором они могут разговаривать вчетвером. Есть язык, на котором они могут разговаривать сразу трое, – итальянский. Никто из ученых не владеет французским и русским языками одновременно. Хотя физик не говорит по-английски, но может быть переводчиком, если биолог и историк захотят поговорить друг с другом. Историк может говорить с математиком по-французски. Физик, биолог и математик не могут беседовать втроем на одном языке. Какими двумя языками владеет биолог (укажите названия языков в именительном падеже через пробел).

Решение: Соединим пунктирными ребрами те вершины, которые не могут быть связаны друг с другом.

Ответ: русский английский

Задача 3. Однажды мама, в магазине купила разную приправу: красный перец, коричневый имбирь, зелёную петрушку и белую горчицу. Придя домой, она разложила всё это в баночки для специй. Я знаю, что у нас дома каждая специя лежит в своей баночке и цвет банки не соответствует свету специй. Так же известно, что зеленая петрушка лежит в коричневой банке, а красный перец не лежит в белой баночке. Мне для приготовления плова нужно узнать: «В какой банке лежит каждая специя?»

Решение: Обозначим точками специи и баночки. Сплошная линия будет обозначать, что специя лежит в соответствующей баночке, а пунктирная, что не лежит. Тогда с учетом задачи имеем граф G1,

Далее достраиваем граф по следующему правилу: поскольку в баночке может лежать только одна специя, то из каждой точки должны выходить одна сплошная линия и три пунктирные. Получается граф G2 — решение задачи.

Ответ: Красный перец лежит в зелёной банке, имбирь лежит в белой банке, зелёная петрушка – в коричневой, а белая горчица лежит в красной баночке.

Задача 4. Запишите все трехзначные числа, для записи которых употребляются только цифры 1 и 2.

Ответ: 111, 112, 121, 122, 211, 212, 221, 222.

Задача 4. Сколько трехзначных чисел можно составить из цифр 2,4,6,8, если цифры в записи числа не повторяются?

Решение: первой цифрой может быть одна из четырех данных цифр, вторая любая из трех, а третья – любая из двух оставшихся, получается:

Всего можно составить 4*3*2= 24 трехзначных числа.

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

Задача 5.

Рис.1 Рис. 2

На рисунке 1 пять вершин, причем три из них – четные ( 1,2 и 3), а два нечетных (4 и 5). Эту фигуру можно начертить одним росчерком. Основываемся при решении на

Закономерность 5.

А вот домик с дверью рис.2 – это уже другая фигура, содержит 9 вершин, 5 из которых четные, а 4 – нечетные. Если в фигуре на графе больше двух нечетных вершин, то ее нельзя начертить одним росчерком!

Задача 6. Можно ли нарисовать графы изображенные на рисунках, не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз?

Решение:

Можно, т. к. только 2 нечетные вершины.
Нельзя, т. к. 4 нечетные вершины.

Задача 7. Мальчики 10 б класса Андрей, Витя, Сережа, Валера, Дима при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано?

Решение: Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени, а производимому рукопожатию — отрезок или часть кривой, соединяющая конкретные точки — имена.

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

Их 10. Ответ: 10.

Задача 8. В трех различных домах живут три поссорившиеся между собой соседа. Недалеко от их домов имеются три колодца. Можно ли от каждого дома проложить к каждому из колодцев тропинку так, чтобы никакие две из них не пересекались?

Решение:

Построим граф, вершины которого,
А, Б, В, 1, 2, 3
соответствуют домам и колодцам условия задачи, и попробуем доказать, что девятую тропинку — ребро графа, не пересекающее остальные ребра, провести нельзя.

Проведенные в графе на рисунке ребра А1, А2, A3 и В1,В2, ВЗ (соответствующие тропинкам от домов А и В ко всем колодцам). Построенный граф разбил плоскость на три области: X, У, Z. Вершина Б, в зависимости от ее расположения на плоскости, попадает в одну из этих трех областей. Если вы рассмотрите каждый из трех случаев «попадания» вершины Б в одну из областей X, Y или Z, то убедитесь, что всякий раз одна из вершин графа 1, 2 или 3 (один из колодцев) будет «недоступной» для вершины Б (т. е. нельзя будет провести одно из ребер Б1, Б2 или Б3. которое не пересекло бы уже имеющихся в графе ребер).

Задача 9. Дан кусок проволоки, длиной 120 см. Можно ли, не ломая проволоки, изготовить каркас куба с ребром 10 см?

Решение:

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

Задача 10. Можно ли обвести карандашом, не отрывая его от бумаги и не проходя по одной линии дважды, правильный пятиугольник с диагоналями?

Решение:

Если пятиугольник – граф и все вершины его четные – то это выполнить

ЗАКЛЮЧЕНИЕ:

Выделяя из словесных рассуждений главное — объекты и отношения между ними, графы представляют изучаемые факты в наглядной форме. Приёмы решения логических задач с использованием графов подкупают своей естественностью и простотой, избавляют от лишних рассуждений, во многих случаях сокращающих нагрузку на память.

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

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

Графы используются при составлении карт и генеалогических древ. С помощью графов удобно и наглядно изображается информация о разных объектах и отношениях между ними. В дальнейшем хочу составить генеалогическое древо своей семьи.

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

СПИСОК ЛИТЕРАТУРЫ:

1. Весёлые задачи, Я. И. Перельман, Москва, 2003г

2. Графы и их применение, О. Оре, Москва, 1979г

3. Ленинградские математические кружки: пособие для внеклассной работы, С. А. Генкин, И. В. Итенберг, Киров, 1994г

4. Математика (Дополнительные главы). Е. В. Смыкалова Санкт-Петербург СМИО Пресс 2006

5 Математическая смекалка, Е. И. Игнатьев, Москва 1994г.

6. Сборник олимпиадных задач по математике, В. Г. Горбачев, 2004г.

7. Физико-математический журнал «Квант», А. Савин, №6 1994г.

8. Наглядная геометрия И.Ф.Шарыгин, Л.Н. Ерганжиева М, дрофа, 2000г.

Построение графов. Решение задач c использованием графов — FINDOUT.SU

Поможем в ✍️ написании учебной работы

Имя

Поможем с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой

Выберите тип работыЧасть дипломаДипломная работаКурсовая работаКонтрольная работаРешение задачРефератНаучно — исследовательская работаОтчет по практикеОтветы на билетыТест/экзамен onlineМонографияЭссеДокладКомпьютерный набор текстаКомпьютерный чертежРецензияПереводРепетиторБизнес-планКонспектыПроверка качестваЭкзамен на сайтеАспирантский рефератМагистерская работаНаучная статьяНаучный трудТехническая редакция текстаЧертеж от рукиДиаграммы, таблицыПрезентация к защитеТезисный планРечь к дипломуДоработка заказа клиентаОтзыв на дипломПубликация статьи в ВАКПубликация статьи в ScopusДипломная работа MBAПовышение оригинальностиКопирайтингДругое

Нажимая кнопку «Продолжить», я принимаю политику конфиденциальности

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

Пояснения к работе

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

При этом элементы множества V называются вершинами графа, а элементы множества Х – ребрами.

В множестве V могут встречаться одинаковые элементы, ребра, соединяющие одинаковые элементы называются петлями. Одинаковые пары в множестве Х называются кратными (или параллельными) ребрами. Количество одинаковых пар

(v, w) в Х называется кратностью ребра (v, w).

Множество V и набор Х определяют граф с кратными ребрами – псевдограф.

G = ( V, X)

Псевдограф без петель называется мультиграфом.

Если в наборе Х ни одна пара не встречается более одного раза, то мультиграф называется графом.

Если пары в наборе Х являются упорядочными, то граф называется ориентированным или орграфом.

Графу соответствует геометрическая конфигурация. Вершины обозначаются точками (кружочками), а ребра – линиями, соединяющими соответствующие вершины.

Определение. Если х = {v, w} – ребро графа, то вершины v, w называются концами ребра х.

Если х = ( v, w) – дуга орграфа, то вершина v – начало, а вершина w – конец дуги х.

Определение. Вершины v, w графа G = (V, X) называются смежными, если {v, w}ÎX. Два ребра называются смежными, если они имеют общюю вершину.

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

Определение. Графы G₁(V₁, X₁) и G₂(V₂, X₂) называются изоморфмными, если существует взаимно однозначное отображение j: V₁ ® V₂, сохраняющее смежность.

Определение. Маршрутом (путем) для графа G(V, X) называется последовательность v₁x₁v₂x₂v₃…x_kv_k₊₁. Маршрут называется замкнутым, если его начальная и конечная точки совпадают. Число ребер (дуг) маршрута (пути) графа называется длиной маршрута (пути).

Определение. Незамкнутый маршрут (путь) называется цепью. Цепь, в которой все вершины попарно различны, называется простой цепью.

Определение. Замкнутый маршрут (путь) называется циклом (контуром). Цикл, в котором все вершины попарно различны, называется простым циклом.

Матрицы графов.

Пусть D = (V, X) – орграф, где V = {v₁, …, v_n}, X = {x₁, … , x_m}.

Определение. Матрицей смежности орграфа D называется квадратичная матрица A(D) = [a_ij] порядка п, у которой

Определение. Если вершина v является концом ребра х, то говорят, что v и х – инциндентны.

Определение. Матрицей инциндентности оргафа D называется матрица размерности п´т B(D) = [b_ij], у которой

Пример. Записать матрицы смежности и инцидентности для графа, изображенного на рисунке.

x₁

v₁ x₄ v₂

x₂

x₃

v₃

Составим матрицу смежности:

	v₁	v₂	v₃
v₁	0	1	0
v₂	1	0	1
v₃	1	0	0

Т. е. — матрица смежности.

Матрица инциндентности:

	x₁	x₂	x₃	x₄
v₁	-1	0	1	1
v₂	1	-1	0	-1
v₃	0	1	-1	0

Т.е.

Если граф имеет кратные дуги (ребра), то в матрице смежности принимается a_ij= k, где k – кратность дуги (ребра).

С помощью матриц смежности и инциндентности всегда можно полностью определить граф и все его компоненты. Такой метод задания графов очень удобен для обработки данных на ЭВМ.

Пример. Задана симметрическая матрица Q неотрицательных чисел. Нарисовать на плоскости граф G(V, X), имеющий заданную матицу Q своей матрицей смежности. Найти матрицу инциндентности R графа G. Нарисовать также орграф , имеющий матрицу смежности Q, определить его матрицу инциндентности С.

x₄

x₃

v₂

x₂ x₅

x₆

x₁ v₁ v₃ x₇ x₈

x₁₀

x₁₁ x₉

v₄

Составим матрицу инциндентности:

	x₁	x₂	x₃	x₄	x₅	x₆	x₇	x₈	x₉	x₁₀	x₁₁
v₁	1	1	0	0	0	0	0	0	0	0	1
v₂	0	1	1	1	1	1	0	0	0	1	0
v₃	0	0	0	0	1	1	1	1	1	0	0
v₄	0	0	0	0	0	0	0	0	1	1	1

Итого:

Построим теперь ориентированный граф с заданной матрицей смежности.

x₄

x₅

v₂

x₂ x₇

х₃ x₆

x₁ v₁ х₈ v₃ x₁₀ x₁₁

х₉

х₁₇ х₁₅ x₁₄

x₁₆ х₁₃ x₁₂

v₄

Составим матрицу инциндентности для ориетированного графа.

Элемент матрицы равен 1, если точка является концом дуги, -1 – если началом дуги, если дуга является петлей, элемент матрицы запишем как ±1.

Таким образом, операции с графами можно свести к операциям с их матрицами.

Задание

Вариант 1.