Семинар ДООМ "Решение задач на применение теории графов"

Материал из ТолВИКИ
Перейти к: навигация, поиск
                               УРОК №2.
           Тема: Решение задач на применение теории графов.


Цели:
      - повторить основные определения по теории графов;
      - отработка навыков решения задач на применение графов;
      - прививать самостоятельность, учить анализировать, развивать нестандартность мышления;


                                АКТУАЛИЗАЦИЯ:


1).Что называется графом; приведите примеры, где в практической деятельности встречаются графы? 
2).Кому принадлежит первая работа по теории графов? 
3).Какие графы называются полными и неполными? 
4).Как подсчитать количество ребер графа, имеющего n-вершин? 
5).Что называется степенью графа? 
6).Какая вершина называется четной и нечетной? 
7).Какой граф называется однородным? 
8).Чему равна сумма степеней всех вершин графа? 
Задача 1 (устно). Докажите, что не существует графа с пятью вершинами, степени которых 4, 4, 4,2? 
Задача 2. (устно). В одном городе всего 25 телефонов. Можно ли их соединить проводами так,
чтобы каждый телефон был соединен ровно с пятью другими?
                           ОТРАБОТКА НАВЫКОВ РЕШЕНИЯ ЗАДАЧ.
ЗАДАЧА 1. В классе 30 человек. Может ли быть так, что 9 из них имеют по 3 друга в этом классе,
11 – по 4 друга, а 10 – по 5 друзей?

РЕШЕНИЕ: представим граф с тридцатью вершинами, у которого 9 вершин имеют степень 3, 11 – степень 4, 10 – степень 5, следовательно, у этого графа 19 нечетных вершин, что противоречит закономерности: число нечетных вершин графа четно. Значит, не может.

ЗАДАЧА 2. В трех различных домах живут три поссорившихся соседа. Недалеко от их домов 
расположены три колодца. Можно ли от каждого дома провести к каждому из колодцев тропинку так,
чтобы никакие 2 из них не пересекались?

Решение: Построим граф , где дома обозначим буквами А, В, С, а колодцы цифрами 1, 2, 3.

 Urok 2 1.JPG
 По рисунку видно, что нельзя.

ЗАДАЧА 3. В государстве система авиалиний устроена так, что любой город соединен авиалиниями не более чем с тремя другими и из любого города в любой другой можно проехать, сделав не более одной пересадки. Какое максимальное число городов может быть в этом государстве? РЕШЕНИЕ: построим граф , по которому показаны существующие авиалинии.

 Urok 2 2.JPG

Если существует некоторый город N, то из него можно добраться не более, чем до трех городов, а из каждого из них не более чем до двух. Тогда всего городов не более чем 1+3+6=10.

САМОСТОЯТЕЛЬНАЯ РАБОТА ( по вариантам).

1 вариант.
ЗАДАЧА. В государстве 100 городов и из каждого из них выходит 4 дороги. Сколько всего дорог в
государстве?
ЗАДАЧА. Можно ли фигуру, изображенную на рисунке, начертить одним росчерком пера? Ответ обоснуйте.
 Urok 2 3.JPG
2 вариант.
ЗАДАЧА. В государстве52 города и из каждого выходит 4 дороги. Сколько всего дорог в
государстве?
ЗАДАЧА. Можно ли фигуру, изображенную на рисунке, начертить одним росчерком пера?
 Urok 2 4.JPG
Личные инструменты
наши друзья
http://аудиохрестоматия.рф/