Решение логических задач с помощью графов сообщение
Обновлено: 18.04.2024
Текст работы размещён без изображений и формул.
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Развитию творческой активности, инициативы, любознательности, смекалки способствует решение нестандартных задач, логических.
Логические задачи – это неотъемлемая часть сегодняшнего дня. Они не покидают ученика в течение всего обучения в школе.
В наше время очень часто успех человека зависит от его способности четко мыслить, логически рассуждать и ясно излагать свои мысли. Без приобретения навыков умственного труда, культуры мышления невозможно успешное овладение основами наук.
Поэтому целью этой работы является изучение видов логических задач, методов их решения, а также возможности развивать свои способности, умения рассуждать и делать правильные выводы.
2. Используя литературу, изучить типы логических задач.
3. Изучение основных методов решения логических задач.
4. Проведение диагностики на выявление уровня логического мышления учащихся 6 класса.
Актуальность темы очевидна, так как логические задачи помогают расширить свой кругозор и развить логическое мышление.
I . Что такое логика?
Итак, логика - одна из древнейших наук. Отдельные истоки логического учения можно обнаружить еще в Индии, в конце II тысячелетия до н. э. Основоположником логики как науки является древнегреческий философ и ученый Аристотель. Именно он обратил внимание на то, что в рассуждениях мы из одних утверждений выводим другие, исходя не из конкретного содержания утверждений, а из определенной взаимосвязи между их формами, структурами.
Чтобы правильно рассуждать, надо изучить правильные способы и методы рассуждении. Научится правильно составлять высказывания, или, как говориться в математической логике, выполнять операции над высказываниями. При этом необходимо знать, вытекает ли истинность сложных высказываний из истинности составляющих их более простых предложений. Анализом методов рассуждений занимается наука логика, а исследованием и изучением математических рассуждений – математическая логика . Логика служит одним из инструментов почти любой науки.
II. Типы логических задач.
Нечисловые задачи очень разнообразны по сложности, содержанию и способности решения. Логические задачи составляют обширный класс нестандартных задач. Сюда относятся, прежде всего, текстовые задачи, в которых требуется распознать объекты или расположить их в определенном порядке по имеющимся свойствам. При этом часть утверждений условия задачи может выступать с различной истинностной оценкой (быть истинной или ложной).
В се логические задачи делятся на определенные группы (типы):
Задачи, решаемые с конца
Задачи на переливание
Задачи на взвешивание
Задачи на пересечение и объединение множеств
III . М етоды решения логических задач .
Решать логические задачи очень увлекательно. В них вроде бы нет никакой математики - нет ни чисел, ни треугольников, а есть только лжецы и мудрецы, истина и ложь. В то же время дух математики в них чувствуется ярче всего - половина решения любой математической задачи (а иногда и гораздо больше половины) состоит в том, чтобы как следует разобраться в условии, распутать все связи между участвующими объектами.
При решении определенного типа задач существует свой оптимальный метод решения :
При решении задач данного типа лучше всего использовать метод рассуждений . Он позволяет проводить рассуждения, используя последовательно все условия задачи, и приходить к выводу, который и будет являться ответом задачи.
Задачи на пересечение и объединение множеств
Это тип задач, в которых требуется найти некоторое пересечение множеств или их объединение, соблюдая условия задачи. Метод Эйлера является незаменимым при решении задач этого типа, а также упрощает рассуждения. Однако, прежде чем приступить к решению задачи, нужно проанализировать условие.
Задачи на переливание
При решении текстовых логических задач на переливание применяется метод построения таблиц . Таблицы не только позволяют наглядно представить условие задачи или ее ответ, но в значительной степени помогают делать правильные логические выводы в ходе решения задачи.
Задачи на взвешивание
В таких задачах от решающего требуется локализовать отличающийся от остальных предмет по весу за ограниченное число взвешиваний. Поиск решения в этом случае осуществляется путем операций сравнения, правда, не только одиночных элементов, но и групп элементов между собой. Задачи данного типа чаще всего решаются методом рассуждений.
Записи восстанавливаются на основании логических рассуждений. При этом нельзя ограничиваться отысканием только одного решения. Испытание нужно доводить до конца, чтобы убедиться, что нет других решений, или найти все решения.
Задачи, решаемые с конца
Такие задачи очень часто ребята задают друг другу в виде головоломок на задуманное число . Задачи решаются методом математических вычислений, основанных на конечном результате в условии .
IV. Подробное рассмотрение трёх способов решения логических задач.
Разнообразие логических задач очень велико. Способов их решения тоже немало. Рассмотр им три самых часто используемых способов решения л огических задач:
- метод графов;
-круги Эйлера;
- табличный;
1) Метод графов.
Если точке из одного множества соответствует точка другого множества, будем соединять эти точки сплошной линией, если не соответствует – то штриховой. Заметим, что по условию задачи у человека только один любимый мультфильм. Поэтому ну жно найти единственно возможное соответствие между элементами двух множеств.
Правило : если какая-то точка оказывается соединенной с двумя точками другого множества штриховыми линиями, то с третьей точкой она должна быть соединена сплошной.
Поэтому граф на рисунке будет выглядеть следующим образом:
Задача решена .
2) Круги Эйлера . Второй способ, которым решаются такие задачи круги Эйлера – задачи на пересечение или объединение множеств.
Это новый тип задач, в которых требуется найти некоторое пересечение множеств или их объединение, соблюдая условия задачи.
Круги Эйлера — геометрическая схема, с помощью которой можно изобразить отношения между подмножествами, для наглядного представления.
Метод Эйлера является незаменимым при решении некоторых задач, а также упрощает рассуждения. Однако, прежде чем приступить к решению задачи, нужно проанализировать условие. Иногда с помощью арифметических действий решить задачу легче.
Решение. Чертим два множества таким образом:
3) Решение логических задач табличным способом.
Основной прием, который используется при решении текстовых логических задач, заключается в построении таблиц. Таблицы не только позволяют наглядно представить условие задачи или ее ответ, но в значительной степени помогают делать правильные логические выводы в ходе решения задачи. Рассмотрим способ решения на конкретной задаче.
Задача. Три клоуна Бим, Бам и Бом вышли на арену в красной, зеленой и синей рубашках. Их туфли были тех же цветов. У Бима цвета рубашки и туфель совпадали. У Бома ни туфли, ни рубашка не были красными. Бам был в зеленых туфлях, а в рубашке другого цвета. Как были одеты клоуны?
Решение. Составим таблицу, в столбцах которой отметим возможные цвета рубашек и туфель клоунов. Будем заполнять таблицу, используя условия задачи. Туфли Бама зеленые, а рубашка не является зеленой. Следовательно, у Бима и Бома туфли уже не могут быть зелеными, так же как не могут быть туфли Бама синими или красными.
Отметим все это в таблице:
Ответ : Б ом – в синих туфлях и зелёной рубашке, Бим – во всём красном, Бам – в зеленых туфлях и синий рубашке.
V. Интересны ли логические задачи учащимся 6 класса ?
Задачи следующего содержания:
Задача 1 . Леня, Женя и Миша имеют фамилию Орлов, Соколов и Ястребов. Какую фамилию имеет каждый мальчик, если Женя, Миша и Соколов - члены математического кружка, а Миша и Ястребов занимаются музыкой? ( Ответ : Алёша Соколов, Женя Ястребов, Миша Орлов).
Задача 2. В семье четверо детей им 5, 8, 13 и 15 лет.
Зовут их Таня, Юра, Света и Лена.
Сколько лет каждому из них, если одна девочка ходит в детский сад, Таня старше, чем Юра, а сумма лет Тани и Светы делится на 3? (Ответ: Свете 5, Юре 8, Тане 13, Лене 15 ).
Среди учеников моего класса, в количестве 30 человек, с двумя предложенными задачами типа "Кто есть кто?" справилось 19 человек, среди которых 11 девочек и 8 мальчиков. С первой задачей справились почти все учащиеся. Вторая задача, вызвала у затруднения.
Результаты решения представлены на диаграмме:
Из диаграммы видно, что 63% (19 человек) успешно справились с двумя задачами, только с первой задачей — 73% (22 человека). Не решили ни одну из задач верно — 27%
Ребята со всей ответственностью и большим интересом отнеслись к решению логических задач. Несмотря на то, что с задачами справились не все ученики, этот процесс их очень увлек. Подводя итог, можно сделать вывод, что если при обучении математике использов ать решение нестандартных задач, то э то приведет к повышению интереса к урокам математики и развитию математических способностей учащихся.
VI. Логические задачи на уроках математики в общеобразовательных школах.
Я решил составить таблицу соответствия некоторых логических задач темам, изучаемым на уроках математики.
Вот, что у меня получилось:
Логические задачи
Тема урока по математике
1. Деду, отцу и сыну вместе 100 лет. Отцу и сыну вместе 45 лет. Сын на 25 лет моложе отца. Сколько кому лет?
Решение: деду 100-45=55 лет; сыну10 лет; отцу 35 лет.
2. Разделите 5 яблок поровну между шестью детьми, не разрезав никакое яблоко больше, чем на 3 части
Решение: 3 яблока разрезать на две равные части. 2 яблока на три. Получим 6 половин и 6 третей. Дать каждому половину и треть.
3. Белка за 20 минут приносит орех в гнездо. Далеко ли орешник от гнезда, если известно, что налегке белка бежит со скоростью 5 м/с , а с орехом — 3 м/с?
Решение: Пусть х – искомый путь. 20мин=20∙60=1200с.
х/5 +х/3 =1200
х = 1200*15:8
Ответ: 2250 м.
4. Решите: К · О · Т = У · Ч · Ё · Н · Ы · Й
Разложение на множители
5. Груша тяжелее яблока,а яблоко тяжелее персика. Что тяжелее: груша или персик?
Решение: Груша тяжелее всех, затем яблоко, и самый лёгкий это персик
Основные выводы: п рименение логических задач на уроках математики в общеобразовательных школах помогает развитию логического мышления у учащихся, расширяет математический кругозор, а также способствуют развитию силы воли, трудолюбия, настойчивости в преодолении трудностей, упорства в достижении целей.
VII . Заключение
Из вышеизложенного можно сделать вывод — необходимо включить изучение логических задач в программу по математике в общеобразовательных школах. Так как это способствует повышению интереса учащихся к данному предмету, развитию нестандартного мышления, трудолюбия и внимания.
VIII. Библиография:
Выяснить особенности применения теории графов при решении логических задач и в практической деятельности.
Предварительный просмотр:
Кожемякина Ирина Семеновна
2. Глава 1.Теория графов
2.1. История возникновения графов
2.2. Задача о кёнигсбергских мостах
2.3.Граф и его элементы
2.4. Степени вершин и подсчет числа ребер
2.4. Эйлеровы графы
3. Глава 2. Решение задач с помощью графов
5. Список литературы
На занятиях математического кружка в 5 классе при решении логических задач, мне понравился метод решения задач с помощью построения графов, и захотелось как можно больше узнать о графах, поэтому я и начал заниматься исследовательской работой по данной теме. Графы заинтересовали меня своей возможностью помогать в решении различных головоломок, математических и логических задач.
Предмет моего исследования: графы
Объект исследования: логические задачи, решаемые с помощью построения графов
Актуальность исследования : актуальность моей работы обусловлена большим интересом к теме данного исследования по математике. Кроме этого, выбранная мною тема актуальна, так как в последнее время теория графов стала простым, доступным и мощным средством решения вопросов, относящихся к широкому кругу проблем.
Цели моего исследования :
Выяснить особенности применения теории графов при решении логических задач и в практической деятельности.
- познакомиться с историей возникновения графов;
- познакомиться с основными понятиями графа, видами, элементами;
- рассмотреть решение логических задач с помощью графов;
Можно предположить, что решение многих математических задач упрощается, если удается использовать графы. Представление данных в виде графа придает им наглядность и простоту.
Глава 1. ТЕОРИЯ ГРАФОВ
1.История возникновения теории графов.
Начало теории графов все единодушно относят к 1736 г., когда Леонард Эйлер - один из крупнейших математиков XVIII, члена Петербургской академии наук, не только решил популярную в то время задачу о кёнигсбергских мостах, но и
нашел критерий существования в графе специального маршрута, который сегодня называют эйлеровым циклом.
Однако эти результаты Эйлера более ста лет являлись, по сути, единственным достижением математической дисциплины, которую позднее назовут теорией графов. Лишь в середине XIX века инженер-электрик Г. Кирхгоф разработал
теорию графов, называемых деревьями, для исследования
Рис. 4 Портрет Леонарда Эйлера. электрических цепей, а математик А. Кэли в связи с
описанием строения углеводородов решил перечислительные задачи для трех видов
2. Задача о кёнигсбергских мостах.
Проблема семи мостов Кёнигсберга или Задача о кёнигсбергских мостах — старинная математическая задача, в которой спрашивалось, как можно пройти по всем семи мостам Кёнигсберга, не проходя ни по одному из них дважды. Издавна жители Кёнигсберга пытались пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически, во время прогулок.
Впрочем, доказать или опровергнуть возможность существования такого маршрута никто не мог.
Читая письмо Эйлера выясним, какое же правило он нашел:
"Вопрос состоит, писал Эйлер, в том, чтобы определить, можно ли обойти все эти семь мостов, проходя через каждый только однажды, или нельзя. Мое правило приводит к следующему решению этого вопроса. Прежде всего, нужно смотреть, сколько есть участков, разделенных водой, - таких, у которых нет другого перехода с одного на другой, кроме как через мост. В данном примере таких участков четыре - A, B, C, D."
Эйлеровский ход решения задачи я представлю в виде графа, где вершины - острова и берега, а ребра - мосты. Рис. 1
Построим граф без посторонних линий. Рис. 2
Читаем письмо Эйлера дальше: "Далее нужно различать, является ли число мостов, ведущих к этим отдельным участкам, четным или нечетным. Так, в нашем случае к участку A ведут пять мостов, а к остальным - по три моста. То есть нам нужно определить степень каждой вершины, и узнать какие вершины четные, а какие нечетные. Подпишем степени вершин в кружочках. И посчитаем количество нечетных вершин. Нечетные вершины: А, B, C, D.
Покажу это на графе - Рис. 3.
Читаем письмо: "Когда это определено, применяем следующее правило: если все вершины имеют четную степень, то тогда обход, о котором идет речь, возможен, и начать этот обход можно с любого участка. Если же из этих вершин две нечетные, то и тогда можно совершить переход, как это предписано, но только начало обхода непременно должно быть взято в одной из этих двух вершин, а конец обхода непременно должен быть во второй нечетной вершине. Если, наконец, больше двух нечетных вершин, то тогда такое движение вообще невозможно. ".
Итак, используя правило Леонардо Эйлера мы можем сделать вывод: так как количество нечетных вершин в графе равно 4, а это > 2, то обойти все кенигсбергские мосты, проходя только один раз через каждый из этих мостов нельзя.
В своей работе Эйлер доказал общее утверждение, для решения каждой подобной задачи о мостах - для того, чтобы можно было обойти все рёбра графа по одному разу и вернуться в исходную вершину, необходимо и достаточно выполнение двух условий:
- Из любой вершины графа должен существовать путь по его рёбрам в любую другую вершину.
- Из каждой вершины должно выходить чётное количество рёбер.
3. Г раф и его элементы.
В математике определение графа дается так:
Графом называется конечное множество точек, некоторые из которых соединены линиями. Точки называются вершинами графа, а соединяющие линии – рёбрами .
По рисунку (графу) видно, что с Мариной никто не знаком, а Саша знаком с Олегом, Катей и Леной.
В графе точки называются вершинами графа, а соединяющие их линии (дуги) – рёбрами . Смотрим Рис. 1.
Графы, в которых не построены все возможные ребра, называются неполными графами . (рис.3)
Графы, в которых построены все возможные ребра, называются полными графами . (рис.4)
Если на ребрах графа нанесены стрелочки, указывающие направление ребер, то такой граф называют направленным.
4. Степени вершин и подсчет числа ребер.
Количество рёбер, выходящих из вершины графа, называется степенью вершины . Вершина графа, имеющая нечётную степень, называется нечетной , а чётную степень – чётной .
Если степени всех вершин графа равны, то граф называется однородным. Таким образом, любой полный граф — однородный.
На рисунке 5 изображен граф с пятью вершинами. Степень вершины А обозначим Ст.А.
На рисунке: Ст.А = 1, Ст.Б = 2, Ст.В = 3, Ст. Г= 2, Ст. Д= 0.
Сформулируем некоторые закономерности, присущие определенным графам.
Степени вершин полного графа одинаковы, и каждая из них на 1 меньше числа вершин этого графа.
Сумма степеней вершин графа число четное, равное удвоенному числу ребер графа.
Эта закономерность справедлива не только для полного, но и для любого графа.
Число нечетных вершин любого графа четно.
Если полный граф имеет n вершин, то количество ребер будет равно .
Действительно, количество ребер в полном графе с n-вершинами определяется как число неупорядоченных пар, составленных из всех n-точек-ребер графа, т. е. как число
сочетаний из n по 2. Граф, не являющийся полным, можно дополнить до полного с теми же вершинами, добавив недостающие ребра. Так, например, на рисунке 3 изображен неполный граф с пятью вершинами. На рисунке 4 ребра превращающие граф в полный граф изображены другим цветом, совокупность вершин графа с этими ребрами называется дополнением графа.
5. Эйлеровы графы.
Граф, который можно нарисовать, не отрывая карандаша от бумаги, называется эйлеровым. ( рис.6) Такими графы названы в честь учёного Леонарда Эйлера.
Закономерность 3 (вытекает из рассмотренной нами теоремы).
Невозможно начертить граф с нечетным числом нечетных вершин.
Закономерность 4.
Граф, имеющий всего две нечетные вершины, можно начертить, не отрывая карандаш от бумаги, при этом движение нужно начать с одной из этих нечетных вершин и закончить во второй из них.
рис.6 (Эйлеровы графы)
Глава 2. РЕШЕНИЕ ЗАДАЧ С ПОМОЩЬЮ ГРАФОВ .
Графы часто используют для решения логических проблем, связанных с перебором вариантов.
Задача 1. В бутылке, стакане, кувшине и банке находятся молоко, лимонад, квас и вода. Известно, что вода и молоко не в бутылке, сосуд с лимонадом стоит между кувшином и сосудом с квасом, в банке – не лимонад и не вода. Стакан стоит около банки и сосуда с молоком. Куда налита каждая жидкость?
Автор: Каракозова Марина Анатольевна
Должность: учитель математики
Учебное заведение: МБОУ СОШ р.п.Жадовка МО "Барышский район"
Населённый пункт: р.п.Жадовка
Наименование материала: Методическая разработка внеурочного занятия
Тема: "Решение логических задач с помощью графа"
Раздел: среднее образование
Предметные
: развитие представления о графах как вспомогательных средствах при решении задач;
Метапредметные
: формирование умения выделять существенные признаки объекта и отношения между объектами; умение строить схемы;
Личностные
: формирование способности увязать учебное содержание с собственным жизненным опытом, понять значение информационного моделирования как метода познания окружающей действительности. В ходе занятия у учащихся могут быть сформированы универсальные учебные действия:
Регулятивные УУД.
Обнаружить и сформулировать учебную проблему, составить план выполнения работы
Познавательные
УУД.
Общеучебные действия: поиск и выделение необходимой информации, самостоятельное создание алгоритмов деятельности. Логические действия: построение логической цепи рассуждений.
Коммуникативные
УУД.
Умение с достаточной полнотой и точностью выражать свои мысли, владение монологической и диалогической формами речи в соответствии с грамматическими и синтаксическими нормами родного языка. Ход занятия. В Википедии можно найти следующее определение графа. В общем смысле
граф
представляется как множество вершин (узлов), соединённых рёбрами. В строгом определении графом называется такая пара
м н о ж е с т в . Те о р и я г р а ф о в н а ход и т п р и м е н е н и е , н ап р и м е р , в геоинформационных системах ( Г И С ) . Су щ е с т ву ю щ и е и л и в н о в ь проектируемые дома, сооружения, кварталы и т. п. рассматриваются как вершины, а соединяющие их дороги, инженерные сети, линии электропередачи и т. п. — как рёбра. Применение различных вычислений, производимых на таком графе, позволяет, например, найти кратчайший объездной путь или ближайший продуктовый магазин, спланировать оптимальный маршрут. Теория графов содержит большое количество нерешённых проблем и пока не доказанных гипотез. Но с помощью графов можно решать логические задачи различной тематики. Рассмотрим некоторые из них.
№ 1.
В первенстве класса по шашкам было 6 участников: Андрей, Борис, Виктор, Галина, Дмитрий и Елена. Каждый участник должен сыграть по одной партии друг с другом. К настоящему моменту некоторые партии уже сыграны: Андрей сыграл с Борисом, Галиной и Еленой; Борис с Андреем, Галиной; Виктор - с Галиной, Дмитрием и Елена – с Андреем и Виктором. Сколько игр проведено и сколько осталось провести? Решение: 1. Изобразим точки с начальными буквами имен всех участников. 2. Соединим отрезками те точки – игроков, которые уже сыграли (голубые). 3. Посчитаем количество получившихся отрезков – игр. (7) 4. Соединим другим цветом тех игроков, которые еще не играли.(красные) 5. Посчитаем количество получившихся отрезков – несыгранных игр. (8)
№ 2
Понятие графа целесообразно вводить после того, как разобрано несколько задач, подобных задаче 1, решающее соображение в которых – графическое представление. Важно, чтобы ученики сразу осознали, что один и тот же граф может быть нарисован разными способами. Строгое определение графа, на мой взгляд, давать не нужно, т.к. оно слишком громоздко и это только затруднит обсуждение. На первых порах хватит и интуитивного понятия. При обсуждении понятия изоморфизма можно решить несколько упражнений на определение изоморфных и неизоморфных графов. Одно из центральных мест темы – теорема о четности числа нечетных вершин. Важно, чтобы ученики до конца разобрались в ее доказательстве и научились применять к решению задач. При разборе нескольких задач рекомендую не ссылаться на теорему, а фактически повторять ее доказательство. Чрезвычайно важно также понятие связности графа. Содержательным соображением здесь является рассмотрение компоненты связности, на это необходимо обратить особое внимание. Эйлеровы графы – тема почти игровая.
Первая и главная цель, которую нужно преследовать при изучении графов, –научить школьников видеть граф в условии задачи и грамотно переводить условие на язык теории графов. Не стоят рассказывать обе всем на нескольких занятиях подряд. Лучше разнести занятия по времени на 2–3 учебных года. (Прилагается разработка занятия “Понятие графа. Применение графов к решению задач” в 6 классе).
2. Теоретический материал к теме “Графы”.
Графы – замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач. В математике существует целый раздел – теория графов, который изучает графы, их свойства и применение. Мы же обсудим только самые основные понятия, свойства графов и некоторые способы решения задач.
Рассмотрим две задачи.
Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.
Теперь сразу видно, что долететь с Земли до Марса нельзя.
Задача 2. Доска имеет форму двойного креста, который получается, если из квадрата 4x4 убрать угловые клетки.
Можно ли обойти ее ходом шахматного коня и вернуться на исходную клетку, побывав на всех клетках ровно по одному разу ?
Решение: Занумеруем последовательно клетки доски:
А теперь с помощью рисунка покажем, что такой обход таблицы, как указано в условии, возможен:
Мы рассмотрели две непохожие задачи. Однако решения этих двух задач объединяет общая идея – графическое представление решения. При этом и картинки, нарисованные для каждой задачи, оказались похожими: каждая картинка – это несколько точек, некоторые из которых соединены линиями.
Такие картинки и называются графами. Точки при этом называются вершинами, а линии – ребрами графа. Заметим, что не каждая картинка такого вида будет называться графом. Например. если вас попросят нарисовать в тетради пятиугольник, то такой рисунок графом не будет. Будем называть что рисунок такого вида, как в предыдущих задачах, графом, если есть какая-то конкретная задача для которой такой рисунок построен.
Другое замечание касается вида графа. Попробуйте проверить, что граф для одной и той же задачи можно нарисовать разными способами; и наоборот для разных задач можно нарисовать одинаковые по виду графы. Здесь важно лишь то, какие вершины соединены друг с другом, а какие – нет. Например, граф для задачи 1 можно нарисовать по-другому:
Такие одинаковые, но по-разному нарисованные графы, называются изоморфными.
Степени вершин и подсчет числа ребер графа
Запишем еще одно определение: Степенью вершины графа называется количество выходящих из нее ребер. В связи с этим, вершина, имеющая четную степень, называется четной вершиной, соответственно, вершина, имеющая нечетную степень, называется нечетной вершиной.
С понятием степени вершины связана одна из основных теорем теории графов –теорема о честности числа нечетных вершин. Докажем ее мы немного позднее, а сначала для иллюстрации рассмотрим задачу.
Задача 3. В городе Маленьком 15 телефонов. Можно ли их соединить проводами так, чтобы каждый телефон был соединен ровно с пятью другими ?
Решение: Допустим, что такое соединение телефонов возможно. Тогда представим себе граф, в котором вершины обозначают телефоны, а ребра – провода, их соединяющие. Подсчитаем, сколько всего получится проводов. К каждому телефону подключено ровно 5 проводов, т.е. степень каждой вершины нашего графа – 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2 (т.к. каждый провод имеет два конца, то при суммировании степеней каждый провод будет взят 2 раза). Но тогда количество проводов получится разным . Но это число не целое. Значит наше предположение о том, что можно соединить каждый телефон ровно с пятью другими, оказалось неверным.
Ответ. Соединить телефоны таким образом невозможно.
Теорема: Любой граф содержит четное число нечетных вершин.
Доказательство: Количество ребер графа равно половине суммы степеней его вершин. Так как количество ребер должно быть целым числом, то сумма степеней вершин должна быть четной. А это возможно только в том случае, если граф содержит четное число нечетных вершин.
Связность графа
Есть еще одно важное понятие, относящееся к графам – понятие связности.
Граф называется связным, если из любые две его вершины можно соединить путем, т.е. непрерывной последовательностью ребер. Существует целый ряд задач, решение которых основано на понятии связности графа.
Задача 4. В стране Семерка 15 городов, каждый из городов соединен дорогами не менее, чем с семью другими. Докажите, что из каждого города модно добраться в любой другой.
Доказательство: Рассмотрим два произвольных А и В города и допустим, что между ними нет пути. Каждый из них соединен дорогами не менее, чем с семью другими, причем нет такого города, который был бы соединен с обоими рассматриваемыми городами (в противном случае существовал бы путь из A в B). Нарисуем часть графа, соответствующую этим городам:
Теперь явно видно, что мы получили не менее различных 16 городов, что противоречит условию задачи. Значит утверждение доказано от противного.
Если принять во внимание предыдущее определение, то утверждение задачи можно переформулировать и по-другому: “Доказать, что граф дорог страны Семерка связен.”
Теперь вы знаете, как выглядит связный граф. Несвязный граф имеет вид нескольких “кусков”, каждый из которых – либо отдельная вершина без ребер, либо связный граф. Пример несвязного графа вы видите на рисунке:
Каждый такой отдельный кусок называется компонентой связности графа. Каждая компонента связности представляет собой связный граф и для нее выполняются все утверждения, которые мы доказали для связных графов. Рассмотрим пример задачи, в которой используется компонента связности:
Задача 5. В Тридевятом царстве только один вид транспорта – ковер-самолет. Из столицы выходит 21 ковролиния, из города Дальний – одна, а из всех остальных городов, – по 20. Докажите, что из столицы можно долететь в город Дальний.
Доказательство: Понятно, что если нарисовать граф ковролиний Царства, то он может быть несвязным. Рассмотрим компоненту связности, которая включает в себя столицу Царства. Из столицы выходит 21 ковролиния, а из любых других городов, кроме города Дальний – по 20, поэтому, чтобы выполнялся закон о четном числе нечетных вершин необходимо, чтобы и город Дальний входил в эту же самую компоненту связности. А так как компонента связности – связный граф, то из столицы существует путь по ковролиниям до города Дальний, что и требовалось доказать.
Вы наверняка сталкивались с задачами, в которых требуется нарисовать какую-либо фигуру не отрывая карандаш от бумаги и проводя каждую линию только один раз. Оказывается, что такая задача не всегда разрешима, т.е. существуют фигуры, которые указанным способом нарисовать нельзя. Вопрос разрешимости таких задач также входит в теорию графов. Впервые его исследовал в 1736 году великий немецкий математик Леонард Эйлер, решая задачу о Кенигсбергских мостах. Поэтому графы, которые можно нарисовать указанным способом, называются Эйлеровыми графами.
Задача 6. Можно ли нарисовать изображенный на рисунке граф не отрывая карандаш от бумаги и проводя каждое ребро ровно один раз ?
Решение. Если мы будем рисовать граф так, как сказано в условии, то в каждую вершину, кроме начальной и конечной, мы войдем столько же раз, сколько выйдем из нее. То есть все вершины графа, кроме двух должны быть четными. В нашем же графе имеется три нечетные вершины, поэтому его нельзя нарисовать указанным в условии способом.
Сейчас мы доказали теорему об Эйлеровых графах:
Теорема: Эйлеров граф должен иметь не более двух нечетных вершин.
И в заключение – задача о Кенигсбергских мостах.
Задача 7. На рисунке изображена схема мостов города Кенигсберга.
Можно ли совершить прогулку так, чтобы пройти по каждому мосту ровно 1 раз?
3. Задачи к теме “Графы”
Понятие графа.
1. На квадратной доске 3x3 расставлены 4 коня так, как показано на рис.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 раз?
Мне нравится Проект нравится 23 участникам
Разрешить проблему удалось знаменитому математику Леонарду Эйлеру. Причем, он решил не только эту конкретную задачу, но придумал общий метод решения подобных задач. При решении задачи о Кенигсбергских мостах Эйлер поступил следующим образом: он "сжал" сушу в точки, а мосты "вытянул" в линии. Такую фигуру, состоящую из точек и линий, связывающих эти точки, называют ГРАФОМ.
Граф – это совокупность непустого множества вершин и связей между вершинами. Кружки называются вершинами графа, линии со стрелками – дугами, без стрелок – ребрами.
Виды графов:
1. Ориентированный граф (кратко орграф) — рёбрам которого присвоено направление.
2. Неориентированный граф - это граф, в котором нет направления линий.
3. Взвешенный граф – дуги или ребра имеют вес (дополнительная информация).
Решение задач с помощью графов:
Задача 1.
Решение: Обозначим ученых вершинами графа и проведем от каждой вершины линии к четырем другим вершинам. Получаем 10 линий, которые и будут считаться рукопожатиями.
Задача 2.
На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб, клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а лиственница выше яблони. Расположите деревья от самого низкого к самому высокому.
Вершины графа - это деревья, обозначенный первой буквой названия дерева. В данной задача два отношения: “быть ниже” и “быть выше”. Рассмотрим отношение “быть ниже” и проведем стрелки от более низкого дерева к более высокому. Если в задаче сказано, что рябина выше лиственницы, то стрелку ставим от лиственницы к рябине и т.д. Получаем граф, на котором видно, что самое низкое дерево – клен, затем идут яблоня, лиственница, рябина, сосна, дуб, береза и тополь.
Задача 3.
Читайте также: