Тема: Графы и их применение к решению задач

Занятие 27 ЛОГИКА 5 класс 03.04.2023

Тема: Графы и их применение к решению задач

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

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

Использование графов при решении задач https://www.youtube.com/watch?v=TvFSNYDWwQU&t=4s

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

Особым видом графа является дерево. Это способ организации информации об отношении между объектами. В нем нет циклов. Примерам такого дерева может служить генеологическое дерево.

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

Рассмотрим решение задач:

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

Решение: Пусть телефоны – вершины графа, а провода – его ребра. Степень каждой вершины графа 5. Чтобы найти число проводов, надо просуммировать степени всех вершин графа и полученный результат разделить на 2. Но в результате получим дробное число. Значит, каждый телефон нельзя соединить ровно с 5 другими телефонами.

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

Решение: 100·4:2=200

3. Нарисовать фигуру, не отрывая карандаша от бумаги и не проводя два раза по одной линии. Все ли фигуры получились? Почему?

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

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

Решить на практике эту задачу никто из жителей не смог. Покорилась она лишь Эйлеру, в то время работавшему в Петербурге. Легендарный математик не только расставил все точки над i, но и разработал общий принцип решения таких задач.

Изначальные семь мостов "стянулись" в четыре точки

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

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

• из 1-ой - выходит три ребра;

• из 2-ой - пять ребер;

• из 3-ой - три ребра;

• из 4-ой - три ребра.

Все четыре вершины графа оказались "нечетными".

Немного поэкспериментировав, Эйлер вывел четыре основных правила для решения таких задач:

1. Число нечетных вершин графа всегда чётно. Невозможно начертить граф, который имел бы нечетное число нечетных вершин. (можете попробовать на досуге).

2. Если у графа все вершины четные, то его можно начертить одним росчерком пера, причем неважно, где начинать.

У этих графов все вершины четные

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

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

Я думаю, Вы уже догадались, что задача о мостах Кёнигсберга решений не имеет, ведь в ней целых четыре нечетных вершины! Однако в наших силах, вооружившись новыми знаниями, "дополнить" архитектурные изыски Калининграда таким образом, чтобы разрешить проблему:

Спасибо за внимание!