Летняя математическая школа . 5 класс

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

История возникновения графов Термин граф впервые появился в книге венгерского математика Д. Кенига в 1936 г., хотя начальные важнейшие теоремы о графах восходят к Л. Эйлеру. Математические графы с дворянским титулом «граф» связывает общее происхождение от латинского слова « графио » - пишу.

Благодаря этой рекламе сайт может продолжать свое существование, спасибо за просмотр.

Задача о Кенигсбергских мостах Город Кенигсберг (после мировой войны он называется Калининград) стоит на реке Прегель. Некогда там было 7 мостов, которые связывали между собой берега и два острова. Жители города заметили, что они никак не могут совершить прогулку по всем семи мостам, пройдя по каждому из них ровно один раз. Так возникла головоломка: “можно ли пройти все семь кенигсбергских мостов ровно один раз и вернуться в исходное место?”. Выстроив алгоритм, Эйлер получил отрицательный ответ в задаче о мостах.

Впервые над задачами такого типа задумался Леонард Эйлер после посещения города Кенигсберга (теперь Калининград). В городе было семь мостов через реку Прегель.

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

Что такое граф Для решения задачи о мостах Эйлер ввёл следующие определения: Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами. Рёбра графа Вершина графа

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

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

Уникурсальные фигуры Уникурсальная фигура – это фигура, которую можно начертить одним росчерком, то есть, не отрывая карандаша от бумаги и не проводя одну и ту же линию дважды. Существует правило, позволяющее определить, можно ли начертить фигуру одним росчерком. Оно основывается на понятиях четной и нечетной вершины графа: вершину графа называют четной, если из нее исходит четное число ребер, и нечетной, если из нее исходит нечетное число ребер. Граф – это фигура, состоящая из конечного множества точек плоскости и отрезков, соединяющих некоторые из этих точек. Точки называются вершинами графа, а отрезки – ребрами графа. Правило: фигуру можно начертить одним росчерком, если: все ее вершины четные, при этом движение можно начинать с любой вершины и закончить в той же вершине(Нечетных вершин нет) у нее только две нечетные вершины, при этом движение нужно начать с одной из этих нечетных вершин и закончить другой. В других случаях построение невозможно!!!

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

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

Одним росчерком Благодаря Леонарду Эйлеру существует общий прием решения подобных задач: преобразовать рисунок в граф (определить его вершины и рёбра), определить степень каждой вершины, посчитать количество нечётных вершин, сделать выводы: а) заданный обход возможен, если - все вершины чётные (его можно начать с любой вершины), - две вершины нечётные (его нужно начать с одной из нечётных вершин), б) заданный обход невозможен, если нечётных вершин больше двух, указать начало и конец пути.

А,Б,В можно Г,Д нельзя

Одним росчерком Говорят, что Магомет вместо подписи (он был неграмотен) описывал одним росчерком состоящий из двух рогов луны знак, представленный на рисунке. Возможно ли это?

Решение. Да, потому что в данном случае мы имеем дело с вершинами четного порядка.

Некоторые буквы, например, С, легко нарисовать одной чертой, не отрывая карандаш от бумаги и не проходя дважды по одному и тому же месту. А вот нарисовать печатную букву Ю, не отрывая карандаш от бумаги и не проводя ни одну линию дважды у вас вряд ли получится. А можно ли написать таким образом букву Р? Букву Х или букву К? В чём разница между этими буквами? А печатную букву А? Какие из русских букв можно написать, не отрывая карандаш от бумаги? Очевидно, легко нарисовать буквы типа Г, З, И, С, Л, М, П. Их можно выпрямить в одну линию

Начинаем выкладывать А, но получается только Л — чтобы попасть к перекладине, надо или оторвать карандаш, или пройти ножку два раза.

Рассмотрим примеры решения задач с помощью графов

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

Задачи с лабиринтом Лабиринт - это граф. А исследовать его - это найти путь в этом графе. дальше

Задачи с лабиринтом Можно ли обойти все данные комнаты, пройдя через каждую дверь ровно один раз и выйти на улицу через комнату 1 или 10? С какой комнаты надо начинать?

Пусть комнаты – вершины графа, а двери – ребра. Проверим степени вершин: Решение: Только две вершины имеют нечетную степень. Начать движение можно из комнаты 10, а закончить в комнате 8, либо наоборот.

Но, чтобы выйти на улицу (из комнаты 10), надо начинать из комнаты 8. В этом случае пройдём все двери один раз и попадём в комнату 10, но окажемся внутри комнаты, а не снаружи: Решение:

Почтальон Печкин разнес почту во все дома деревни и зашел к Дяде Фёдору выпить молока. На рисунке показаны все тропинки, которые проходил Печкин, причем по каждой тропинке он прошёл только один раз. Укажи номерами порядок прохождения тропинок, а стрелками – направление. В каком доме живёт Дядя Фёдор? Применим вышеизложенное правило к данной задаче: Вершина - является четной, т.к. она имеет четное число рёбер (четыре). Вершины 2, 3, 4, 6, 7 – также четные. Вершина 5 и вершина под названием «почта» – нечетные, т.к. они имеют нечетное количество рёбер (по три каждая). Согласно пункту 2 вышеизложенного правила, мы имеет возможность весь путь «начертить одним росчерком», т.к. в нашей задаче только две нечетные вершины. При этом движение мы должны начать с одной из этих нечетных вершин и закончить другой. Попробуем начать с вершины «почта» и закончить вершиной 5. Ответ: п-1-3-п-7-1-2-3-4-5-6-7-5. Дядя Фёдор живет в домике №5.

Логические задачи Аркадий, Борис. Владимир, Григорий и Дмитрий при встрече обменялись рукопожатиями (каждый пожал руку каждому по одному разу). Сколько всего рукопожатий было сделано? Решение: Пусть каждому из пяти молодых людей соответствует определенная точка на плоскости, названная первой буквой его имени, а производимому рукопожатию — отрезок или часть кривой, соединяющая конкретные точки — имена. Если подсчитать число ребер графа, изображенного на рисунке, или по формуле n(n-1)/2, это число и будет равно количеству совершенных рукопожатий между пятью молодыми людьми. Их 10.

Логические задачи В деревне 10 домов, и из каждого выходит по 7 тропинок, идущих к другим домам. Сколько всего тропинок приходит между домами? Решение. Пусть дома- вершины графа, тропинки- рёбра. По условию из каждого дома (вершины) выходит 7 тропинок (рёбер), тогда степень каждой вершины 7, сумма степеней вершин 7×10=70, а число рёбер 70 : 2= 35. Таким образом, между домами проходит 35 тропинок. Ответ. 35 тропинок

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

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

Графом является и система улиц города. Его вершины – площади и перекрестки, а ребра – улицы. дальше Применение графов

Схема линий московского метрополите-на

Применение графов Графы есть и на картах звездного неба.

Применение графов Графами являются блок – схемы программ для ЭВМ. дальше

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

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

Продолжим решение задачи 1 Покажем синим цветом еще не проведенные игры. Сколько еще нужно провести игр? Ответ: 8.

Задача 2 В школьном кружке решили ставить гоголевского «Ревизора». И тут разгорелся жаркий спор. Ляпкина-Тяпкина хотели играть: Гена, Дима. Гена согласен уступить, если ему дадут роль Хлестакова. А Дима уступит, если ему дадут роль Осипа. Вова хочет быть Городничим или Земляникой. Алик и Боря хотят быть Городничим или Хлестаковым. Удастся ли распределить роли так, чтобы все были довольны? Составьте схему для решения этой задачи

Ответ к задаче 2 Ответ: Играют: Гена – Ляпкина-Тяпкина, Дима – Осипа, Вова – Землянику, Алик – Хлестакова, Боря – Городничего.

Решение

Задача 4 Корзины, полные яблок. В пяти корзинах лежат яблоки пяти разных сортов. Яблоки первого сорта лежат в корзинах Г и Д, яблоки второго сорта в корзинах А, Б и Г, в корзинах А, Б и В имеются яблоки пятого сорта, в корзине В имеются к тому же яблоки четвертого сорта, а в корзине Д — третьего. Требуется дать каждой корзине номер, но так, чтобы в корзине №1 были яблоки первого сорта (хотя бы одно), в корзине №2 — второго и т. д.

Решение задачи 4 Составим схему по условию задачи

Решение задачи 4

Решение задачи 4 и ответ

Задача 5 В автомобильных гонках Коля, Боря, Юра заняли первые четыре места. На вопрос, какие места они заняли, трое из них ответили: 1)Коля ни первое, ни четвертое, 2)Боря второе, 3)Вова не был последним. Какое место занял каждый мальчик? Решите самостоятельно

К решению задачи 5 В автомобильных гонках Коля, Боря, Юра заняли первые четыре места. На вопрос, какие места они заняли, трое из них ответили: 1)Коля ни первое, ни четвертое, 2)Боря второе, 3)Вова не был последним. Какое место занял каждый мальчик?

Решение задачи 5

Ответ к задаче 5 Ответ: I место - Вова II место - Боря III место - Коля IV место - Юра

Геометрические искажения Иллюзия Геринга (иллюзия веера). Прямые, на самом деле, параллельны.

Иллюзия Вундта (1896). Линии в центре, в действительности, параллельны.

Здесь тоже линии параллельны.

Иллюзия Поггендорфа (Poggendorf, 1860) На одной прямой лежат линии BC, а не AC, как кажется.

Иллюзия Перельмана. Буквы на самом деле параллельны друг другу.

горизонтальные линии параллельны.

Круги или спирали?

Задача 1. Три друга — Алеша, Боря и Витя — учатся в одном классе. Один из них ездит домой из школы на автобусе, один — на трамвае, один — на троллейбусе. Однажды после уроков Алеша пошел проводить своего друга до остановки автобуса. Когда мимо них проходил троллейбус, третий друг крик­нул из окна: «Боря, ты забыл в школе тетрадку!». Кто на чем ездит домой?

Алеша поедет на трамвае, Боря — на ав­тобусе, Витя — на троллейбусе.

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

медведь — в костюме волка, лиса — в костюме зайца, волк — в костюме лисы, заяц — в костюме медведя.

Задача 3. В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что вода и молоко не в бутылке, сосуд с лимонадом стоит между кувшином и сосудом с квасом, в банке не лимонад и не вода, стакан стоит между банкой и сосудом с молоком. В каком сосуде находится каждая из жидкостей?

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

Задача 4. В небольшом районном городе живут пять друзей: Иванов, Петренко, Сидорчук, Гришин и Капустин. Профессии у них разные: один из них маляр, другой — мельник, третий — плотник, чет­вертый — почтальон, а пятый — парикмахер. Пет­ренко и Гришин никогда не держали в руках ма­лярной кисти. Иванов и Гришин собираются посе­тить мельницу, на которой работает их товарищ. Петренко и Капустин живут в одном доме с почта­льоном. Сидорчук был недавно в ЗАГСе одним из свидетелей, когда Петренко и дочь парикмахера сочетались законным браком. Иванов и Петренко каждое воскресенье играют в городки с плотником и маляром. Гришин и Капустин по субботам обяза­тельно встречаются в парикмахерской, где работает их друг. Почтальон предпочитает бриться сам. Кто есть кто?

Иванов — парикмахер, Петренко — мельник, Сидорчук — почтальон, Гришин — плотник, Капустин — маляр.

Беседуют трое друзей: Белокуров, Рыжов и Чернов. Брюнет сказал Белокурову: «Любопытно, что один из нас блондин, другой — брюнет, третий — рыжий, но ни у кого цвет волос не соответствует фа­милии». Какой цвет волос у каждого из друзей?