ГРАФЫ И ИХ ПРИМЕНЕНИЕ ПРИ РЕШЕНИИ ЗАДАЧ

ГРАФЫ И ИХ ПРИМЕНЕНИЕ ПРИ РЕШЕНИИ ЗАДАЧ Методическая разработка Задачи, приводящие к графам 1. Женя, Дима, Максим и Алеша сыграли между собой по одной партии  в шахматы. Сколько всего партий было сыграно? Решение: Женя сыграл партию с Димой, партию с Максимом и партию с Алешей ­  всего три партии. Дима также сыграл три партии ­ с Женей, Максимом и Алешей. Но партию Димы с Женей мы уже посчитали. Остается  добавить одну партию, которую сыграли Максим с Алешей. Поэтому  искомое число партий равно значению выражения 3+2+1. Проще решить эту задачу с помощью рисунка. Каждая линия обозначает сыгранную партию. Всего на схеме 6 линий,  значит всего сыграно 6 партий. 2. Вася, Коля, Петя, Аня и Наташа ­ лучшие лыжники в пятом классе.  Для участия в соревнованиях нужно выбрать из них одного мальчика и  одну девочку. Сколькими способами это можно сделать? Решение: Эту задачу можно решить с помощью следующей схемы. Ответ: 6 способов. 3. Пятеро ученых, участвовавших в научной конференции, обменялись  рукопожатиями. Сколько всего было сделано рукопожатий? На прощание эти ученые обменялись визитными карточками. Сколько  карточек было передано из рук в руки? Решение: карточек. Ответ: 10 рукопожатий, 20 визитных  Задача 4. Между девятью планетами солнечной системы  установлено космическое сообщение. Рейсовые ракеты летают по  следующим маршрутам: Земля – Меркурий; Плутон – Венера; Земля –  Плутон; Плутон – Меркурий; Меркурий – Вене; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс и Марс – Уран. Можно ли долететь на рейсовых ракетах с Земли до Марса ? Решение: Нарисуем схему условия: планеты изобразим точками, а  маршруты ракет – линиями. Теперь сразу видно, что долететь с Земли до Марса нельзя. 5. На рисунке ­ схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге  можно двигаться только в одном направлении, указанном стрелкой. Сколько существует  различных путей из города А в город Ж? Задача 6. На пришкольном участке растут 8 деревьев: яблоня, тополь, береза, рябина, дуб,  клен, лиственница и сосна. Рябина выше лиственницы, яблоня выше клена, дуб  ниже березы, но выше сосны, сосна выше рябины, береза ниже тополя, а  лиственница выше яблони. Расположите деревья от самого низкого к самому  высокому. Решение: Вершины графа ­ это деревья, обозначенный первой буквой названия дерева. В  данной задача два отношения: “быть ниже” и “быть выше”. Рассмотрим  отношение “быть ниже” и проведем стрелки от более низкого дерева к более  высокому. Если в задаче сказано, что рябина выше лиственницы, то стрелку  ставим от лиственницы к рябине и т.д. Получаем граф, на котором видно, что  самое низкое дерево – клен, затем идут яблоня, лиственница, рябина, сосна, дуб, береза и тополь. Задача 7. У Наташи есть 2 конверта: обычный и авиа, и 3 марки: прямоугольная,  квадратная и треугольная. Сколькими способами Наташа может выбрать конверт и марку, чтобы отправить письмо? Решение: