Страна графов

Слайд 1

Страна графов. Применение теории графов при решении логических задач. Авторы: Мирзабекова А.Х. ученица 7 «в» класса РМЛ Руководитель : Синдикова А.Ю. учитель математики РМЛ

Слайд 2

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

Слайд 3

Графом называется множество точек, изображенных на плоскости (листе бумаги, доске), некоторые пары из которых соединены линиями. Точки называются вершинами графа, линии – ребрами . Степенью вершины называется число ребер, выходящих из вершины. Две вершины, образующие ребро, называются смежными. В этом случае будем говорить, что вершины соединены ребром . Два ребра называются смежными, они имеют общую вершину. Граф называется полным, если любая пара его вершин соединена ребром. Полный граф с n вершинами обозначается К n . Такой граф имеет n ( n – 1)/ 2 ребер. На рисунке изображены полные графы с небольшим числом вершин . Рис.6. Полные графы. Граф называется связным , если от каждой его вершины можно по ребрам перейти к любой другой вершине. Если это сделать невозможно, то граф называется несвязным. Cтепень вершины - это количество ребер графа, исходящих из этой вершины. Вершина называется нечетной - если степень этой вершины нечетная, четной — если степень этой вершины четная. Деревом называется связный граф, не имеющий циклов.

Слайд 4

К XVIII веку через реку, на которой стоял город Кенигсберг (ныне Калининград), было построено 7 мостов, которые связывали с берегами и друг с другом два острова, расположенные в пределах города (см.рисунок) Задача заключается в следующем: нужно пройти (если это возможно) по всем семи мостам так, чтобы на каждом из них побывать лишь по одному разу и вернуться к тому месту, откуда начал маршрут. 4

Слайд 5

Л. Эйлер доказал, что маршрута, который бы отвечал условиям головоломки, не существует, и разработал теорию решения такого рода головоломок. Владея материалом вводной части курса «Знакомство с графами», нетрудно воспроизвести идею рассуждения Л. Эйлера. Для этого нужно предварительно заменить Рисунок 1 схемой, приведенной на рисунке 2, где острова и берега изображаются точками. Схема, приведенная на рисунке 2 не является строго говоря, графом: на ней имеются кратные ребра. Тем не менее 1736 год, когда эта головоломка была решена, принято считать годом рождения теории графов. Рисунок2

Слайд 6

Задача1. Шахматный турнир проводится по круговой системе, при которой каждый участник встречается с каждым ровно один раз, участвуют семь школьников. Известно , что в настоящий момент: Ваня сыграл шесть партий, Толя сыграл пять партий,Леша и Дима сыграли по три партии, Семен и Илья сыграли по две партии, Женя сыграл одну партию. Требуется определить: с кем сыграл Леша.

Слайд 7

7 Число в скобках называют степенью вершины, оно показывает сколько ребер выходит из данной вершины В аня (6) Т оля (5) Л еша (3) Д има (3) С емен (2) И лья (2) Ж еня (1) Изобразим участников турнира точками Для каждой точки укажем ее имя (по первой букве имени игрока) и количество партий, сыгранные этим игроком

Слайд 8

Начать построение ребер следует с вершины В , так как это единственная вершина, которая соединяется со всеми другими вершинами графа В аня (6) Т оля (5) Л еша (3) Д има (3) С емен (2) И лья (2) Ж еня (1) Будем строить ребра графа с учетом степеней вершин 8

Слайд 9

Для вершин В и Ж построены все возможные ребра В аня (6) Т оля (5) Л еша (3) Д има (3) С емен (2) И лья (2) Ж еня (1) Сделаем первые выводы: 9

Слайд 10

Теперь однозначно определяются ребра вершины Т . С учетом ребра ВТ надо построить четыре ребра В аня (6) Т оля (5) Л еша (3) Д има (3) С емен (2) И лья (2) Ж еня (1) Построим следующие ребра 10

Слайд 11

Все возможные ребра теперь построены для вершин Ж, В, Т , а также для вершин С и И В аня (6) Т оля (5 ) Л еша (3) Д има (3) С емен (2) И лья (2) Ж еня (1) Пора делать новые выводы 11

Слайд 12

ОТВЕТ: Леша играл с Толей, Ваней и Димой В аня (6) Т оля (5) Л еша (3) Д има (3) С емен (2) И лья (2) Ж еня (1) Требовалось определить: с кем сыграл Леша. Граф к задаче построен 12

Слайд 13

задача 2 В одном дворе живут четыре друга. Вадим и шофер старше Сергея, Николай и слесарь занимаются боксом, Электрик-младший из друзей. По вечерам Андрей и токарь играют в домино против Сергея и электрика. Определите профессию каждого из друзей. 13

Слайд 14

Вадим Коля Сергей Андрей слесарь токарь электрик шофер Начинаем анализировать полученную схему. От каждого верхнего кружка должно исходить 4 линии к кружкам нижнего ряда,одна из которых сплошная(прочная связь) , три-пунктирные . (разрывная связь). И от кружков нижнего ряда-аналогично . От Сергея отходит 3 разрывные связи, значит, четвертая- прочная связь Ответ готов : Вадим-токарь, Сергей-слесарь, Коля-электрик, Андрей-шофер 14

Слайд 15

Выводы: Знание теории графов дают возможность приобрести навыки сведения реальных ситуаций к графовым моделям, научиться строить простейшие алгоритмы. Графы можно широко применять в рамках учебной деятельности школьников, в частности, при обработке данных анкет, в которых выясняются отношения человека к человеку или человека к какому-либо предмету. Многие логические задачи лучше представить в виде чертежа, рисунка, схемы, в которых используются графы. Это облегчает решение задачи, делает его более убедительным и наглядным. Научиться решать задачи с использованием графов можно, если изучить элементарную теорию графов и разумно, последовательно применять ее при решении логических задач, переходя от решения простых задач к более сложным.