Обсуждение участника:Пенкина Любовь Ивановна

Материал из ТолВИКИ
(Различия между версиями)
Перейти к: навигация, поиск
(Полностью удалено содержимое страницы)
 
Строка 1: Строка 1:
Знакомство с графами (5 класс)
 
  
Участник: Пенкина Любовь Ивановна 005
 
 
Тема: '''Графы'''
 
 
Цель: 
 
 знакомство с новым способом решения задач повышенной трудности;
 
 развитие  логического мышления у учащихся;
 
 воспитание интереса к предмету.
 
 
Оборудование:
 
 карточки с задачами;
 
 многогранники: куб, пирамида, додекаэдр;
 
 школьная доска с готовыми рисунками графов.
 
 
Ход занятия.
 
 
I. '''Вводная беседа'''
 
 
Сегодня мы с вами познакомимся еще с одним способом решения логических задач. Рассмотрим сначала три задачи:
 
             
 
'''1. Кто играет Ляпкина-Тяпкина?'''
 
            В школьном драмкружке решили ставить гоголевского «Ревизора». И тут разгорелся жаркий спор. Все началось с Ляпкина-Тяпкина.
 
  - Ляпкиным-Тяпкиным буду я! – решительно заявил Гена.
 
  - Нет, я буду Ляпкиным-Тяпкиным, - возразил Дима. – С раннего детства мечтал воплотить этот образ на сцене.
 
  - Ну, хорошо, согласен уступить эту роль, если мне дадут сыграть Хлестакова, - проявил великодушие Гена.
 
  - …А мне – Осипа – не уступил ему в великодушии Дима.
 
  - Хочу быть Земляникой или Городничим, - сказал Вова.
 
  - Нет, Городничим буду я, - хором закричали Алик и Боря. – Или Хлестаковым, - добавили они одновременно.
 
Удастся ли распределить роли так, чтобы исполнители были довольны? (Мы не спрашиваем, будут ли довольны зрители.)
 
 
'''2. Сварливые соседи.'''
 
        Житель пяти домов поссорились друг с другом и, чтобы не встречаться у колодцев, решили поделить их (колодцы) так, чтобы хозяин каждого дома  ходил к «своему» колодцу по «своей» тропинке. Удастся ли им это сделать?
 
 
[[Изображение:ris1.gif]],
 
'''3. Корзины, полные хлебцов.'''
 
            В пяти корзинах лежат хлебцы пяти сортов. Хлебцы первого сорта лежат в корзинах Г и Д; хлебцы второго сорта – в корзинах А, Б и Г; в корзинах А, Б и В имеются хлебцы пятого сорта, в корзине В имеются к тому же хлебцы четвертого сорта, а в корзине Д – третьего. Требуется дать каждой корзине но-мер, но так, чтобы в корзине № 1 были хлебцы первого сорта (хотя бы один), в корзине № 2 – второго и т.д.
 
 
[[Изображение:ris2.gif]],
 
'''II. Обсуждение.'''
 
Эти задачи довольно простые. Достойно удивления другое – хотя на первый взгляд эти задачи раз-личны – в одной говорится о распределении ролей, в другой – о тропинках от домов к колодцам, в третьей – о нумерации корзин с хлебцами, существует единый подход к решению этих задач, связанный с так называемой теорией графов.
 
Переведя эти задачи на язык теории графов, вы увидите, что все три задачи превратятся в простенькую задачу «на графы».
 
Познакомимся с основными понятиями теории графов. Прежде всего, стоит сказать о том, что гра-фы, о которых идет речь, к аристократам былых времен никакого отношения не имеют. Наши «графы» имеют корнем греческое слово «графо», что значит «пишу». Тот же корень в словах «график», «биография», «голография»
 
Понятие графа проще всего выяснить на примере.
 
 
'''III. Разбор задач.'''
 
'''''4. Первенство классов.'''''
 
            В первенстве класса по настольному теннису принимали участие 6 учеников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Первенство проводится по круговой системе – каждый из участников играет с каждым из остальных один раз. К настоящему моменту некоторые игры уже проведены: Анд-рей сыграл с Борисом, Галиной и Еленой; Борис, как уже говорилось, с Андреем и еще с Галиной; Виктор – с Галиной, Дмитрием и Еленой; Галина – с Андреем и Виктором. Сколько игр проведено к настоящему моменту и сколько еще осталось?
 
          '''О б с у ж д е н и е.'''  Изобразим данные задачи в виде схемы. Участников будем изображать точками: Андрея – точкой А, Бориса – точкой Б и т.д. Если двое участников уже сыграли между собой, то будем соединять изображающие их точки  отрезками. Получается схема, показанная на рисунке.
 
 
[[Изображение:ris3.gif]],
 
 
Такие схемы называются '''графами'''. Точки А, Б, В, Г, Д называются '''вершинами графа''', соединяющие их отрезки – '''ребрами графа'''. Заметьте, что точки пересечения ребер графа не являются его вершинами. Во избежание путаницы вершины графа часто изображают не точками, а кружочками. Ребра зачастую оказывается удобнее изображать не прямолинейными отрезками, а криволинейными – «дугами».
 
Решим нашу задачу. Число игр, проведенных к настоящему моменту, равно числу ребер, т.е. 7. Чтобы найти число игр, которые осталось провести, построим еще один граф с теми же вершинами, но ребрами будем соединять тех участников, которые еще не играли друг с другом. Ребер у этого графа оказалось 8, значит, осталось провести 8 игр.
 
 
[[Изображение:ris4.gif]],
 
 
Графами мы пользуемся довольно часто. Возьмите схему железных дорог: здесь станции – это вершины графа, перегоны (участки пути между станциями) – ребра графа. Вершины и ребра многогранни-ка (куба, пирамиды и т.д.) тоже образуют граф.
 
 
'''IV. Решение первых трех задач'''
 
[[Изображение:ris5.gif]],
 
 
А теперь решим первые три задачи с помощью графов.
 
Попробуем построить граф для ситуации, описанной в задаче 8.1: «Кто играет Ляпкина-Тяпкина?» Изобразим юных актеров кружками верхнего ряда: А — Алик, Б — Боря, В — Вова, Г — Гена, Д — Дима, а роли, которые они собираются играть – кружками второго ряда (1— Ляпкин-Тяпкин, 2 — Хлестаков, 3 — Осип, 4 — Земляника, 5 — Городничий). Затем от каждого участника проведем отрезки, т. е. ребра, к ролям, которые он хотел бы сыграть. У нас получится граф с десятью вершинами и десятью ребрами.
 
Чтобы решить задачу, нужно из десяти выбрать пять ребер, не имеющих общих вершин. Сделать это легко. Достаточно заметить, что в вершины 3 и 4 ведет по одному ребру, из вершин Д и В соответственно. Это означает, что Осипа (вершина 3) должен играть Дима (кто же еще?), а Землянику — Вова. Вершина 1 — Ляпкин-Тяпкин — соединена ребрами с Г и Д. Ребро 1 — Д отпадает, так как Дима уже занят, остается ребро 1 — Г, Ляпкина-Тяпкина должен играть Гена. Остается соединить вершины А и Б с вершинами 2 и 5, соответствующими ролям Хлестакова и Городничего. Это можно сделать двумя способами: либо выбрать ребра А — 5 и Б — 2, либо ребра А—2 и Б — 5. В первом случае Алик будет играть Городничего, а Боря — Хлестакова, во втором случае наоборот. Как показывает наш граф, других решений задача не имеет.
 
Постройте теперь графы для второй и третьей задач. У вас получились те же графы! Теперь вы видите, что вторая и третья задачи по сути ничем не отличаются от первой. Отметив на этих графах по пять ребер, не имеющих общих вершин, вы тем самым решите данные задачи.
 
Возникает вопрос: так ли уж нужны были графы в разобранных задачах? Разве нельзя прийти к решению чисто логическим путем? Да, можно. Но графы придали условиям наглядность, упростили решение и выявили сходство задач, превратив три задачи в одну, а это не так уж мало. А теперь представьте себе задачи, графы которых имеют 100 или более вершин. А ведь именно такие задачи приходится решать современным инженерам и экономистам. Тут уж без графов не обойтись.
 
Сейчас почти в любой отрасли науки и техники встречаешься с графами: в элект¬ротехнике — при построении электрических схем, в химии и биологии — при изучении молекул и их цепочек, в экономике — при решении задач о выборе оптимального пути для потоков грузо¬вого транспорта и во многих других задачах. О математике и говорить не приходится. С теорией графов связаны не только математические развлечения и головоломки, но и такие серьезные науки, как теория отношений и теория групп.
 
И все же теория графов — наука сравнительно молодая: во времена Ньютона такой науки еще не было, хотя и были в ходу «генеалогические деревья», представляющие собой разновидности графов. Первая работа по теории графов принадлежит Леонарду Эйлеру, и появилась она в 1736 году в публикациях Петербургской Академии наук. Начиналась эха работа с рассмотрения следующей задачи:
 
 
[[Изображение:ris6.gif]],
 
 
'''Задача о кенигсбергских мостах'''. Город Кенигсберг (ныне Калининград) расположен на берегах и двух островах реки Прегель (Преголи). Различные части города были соединены семью моста¬ми, как пока-зано на рисунке В воскресные дни горожане совер¬шают прогулки по городу. Можно ли выбрать такой маршрут, чтобы пройти один и только один раз по каждому мосту и потом вернуться в начальную точку пути?
 
''Обсуждение.'' Обозначим различные части города буквами А, В, C ,D, а мосты — буквами a,b,c, d, e ,f, g. В этой задаче существенны лишь переходы через мосты: переходя через любой мост, мы всегда из одной части города попадаем в другую, - и, наоборот, переходя из одной части города в другую, мы непременно пройдем по мосту. Поэтому изобразим план города в виде графа, вершины которого А, В, С и D изображают отдельные части города, а ребра а, b9 с, d, e, f, g — мосты, соединяющие соответствующие части города. Если бы существовал маршрут, удовлетворяющий условию задачи, то существовал бы замкнутый и непрерывный обход этого графа, проходящий один раз по каждому ребру. Иными словами, этот граф можно было бы вычертить, не отрывая карандаша от бумаги и не проходя дважды по одному и тому же ребру. Но это невозможно — какую бы вершину мы ни выбрали за исходную, нам придется проходить через остальные вершины, и при этом каждому «входящему» ребру (мосту, по которому мы вошли в эту часть города) будет соответствовать «выходящее» ребро (мост, которым мы воспользуемся затем, чтобы покинуть эту часть горо¬да): число ребер, входящих в каждую вершину, будет равно числу ребер, выходящих из нее, т. е. общее число ребер, сходящихся в каждой вершине, долж-но быть четным. Наш граф этому условию не удовлетворяет, и поэтому требуемого маршрута не существует. Если в каждой вершине связного графа сходится четное число ребер, то такой граф называется «эйлеров». Можно доказать, что всякий эйлеров граф допускает непрерывный замкнутый обход (такой путь в теории графов называется ц и к л ом), проходящий по каждому ребру ровно один раз. Из предыдущих рассуждений следует, что граф, не являющийся эйлеровым, такого обхода не до¬пускает.
 
 
'''V. Закрепление''' полученных навыков решения задач с помощью графов.
 
1. Сколькими способами можно пройти из А в В, двигаясь по линиям слева направо и сверху вниз? 
 
 
[[Изображение:ris7.gif]],
 
2.  В выходной день Миша решил навестить своих друзей: Алешу, Борю, Витю, Гену, Диму, Женю, Колю, Славу. Он начертил схему взаимного расположения домов, где живут мальчики, и дорог, соеди-няющих их. Посетил он их в следующем порядке: Алеша, Боря, Витя, Гена, Дима, Женя, Коля, Слава. Ус-тановите, какой дом кому принадлежит, если ни к одному из домов Миша не подходил более одного раза, Известно, что Миша живет в доме М, последним он посетил дом R. 
 
 
[[Изображение:ris8.gif]],
 
 
3. '''Задача Леонарда Эйлера'''. Можно ли совершить прогулку по городу, план которого показан на  рисунке, пройдя в точности один раз по каждому из пятнадцати мостов. Возвращаться в начальную точку пути не обязательно. Если такой обход существует, найти его, указав мосты в той последовательности, в которой вы их проходите. Если же такого обхода не может существовать, объясните, почему не может. Постройте граф — план города.
 
 
[[Изображение:ris9.gif]],
 
 
VI. Задание на дом.
 
 
1. Решение задач на разрезание
 
 
№ 1. Разрезать фигуру на четыре равные части (рис. 1):
 
 
[[Изображение:ris10.gif]],
 
 
№ 2. Пусть фигура состоит из трех равных квадратов, расположенных так, как показано на рис. 2. Вырезать из этой фигуры такую часть, чтобы приложив ее к оставшейся части, получить квадрат, внутри которого имеется квадратное отверстие.
 
 
№ 3. Квадрат с вырезанной «четвертушкой» легко разрезать на четыре равные части  (см. рис. 1). А сможете ли вы разрезать сам квадрат на пять равных частей?
 
 
№ 4. На коврике изображено семь роз. Требуется  тремя прямыми линиями разрезать коврик на семь частей, каждая из которых содержала бы по одной розе (рис. 3).
 
 
[[Изображение:ris11.gif]],
 
 
№ 5. Произвольный треугольник АВС разрезать на три части – такие, чтобы из них можно было со-ставить прямоугольник.
 
 
№ 6. Изображенную на рис. 4 фигуру требуется разделить на шесть частей, проведя всего лишь две прямые. Попытайтесь это сделать.
 
 
'''VII. Итог занятия.'''
 
 
 
Итак, сегодня мы познакомились еще с одним из способов решения задач. Таким образом, чтобы ответить на вопрос задачи, нужно найти наиболее оптимальный способ решения.
 

Текущая версия на 14:42, 31 октября 2007

Личные инструменты
наши друзья
http://аудиохрестоматия.рф/