КАКОЕ НАИБОЛЬШЕЕ ЧИСЛО РЕБЕР МОЖЕТ СОДЕРЖАТЬ ГРАФ, ИМЕЮЩИЙ N ВЕРШИН?
методическая разработка по информатике и икт (10 класс) по теме

КАКОЕ НАИБОЛЬШЕЕ ЧИСЛО РЕБЕР МОЖЕТ СОДЕРЖАТЬ ГРАФ,

ИМЕЮЩИЙ N ВЕРШИН?

Выполнили: Воробьева Элиза Александровна, Тищенко Алина Витальевна ученицы 10 класса, руководитель: Славянская Лариса Владимировна. Волгоград 2013

Введение.

Тема «Графы» в школьном курсе информатики изучается в седьмом классе в теме «Математические модели», в 10 классе базовый уровень «Информационные модели»,   в 10 классе профильный уровень «Дискретные приближения непрерывных моделей.

Постановка проблемы.

 В учебнике 1 «Информатика и ИКТ» мы прочитали задачу: Какое наибольшее число ребер может содержать граф, имеющий n вершин?

Цель исследования: Выявить, обосновать и экспериментально проверить одно из свойств графов.

Задача исследования:

1. Разработать принцип построение  модели графов
2. Выявить и обосновать методику подсчета ребер
3. При построение  модели графов учесть наглядность данного свойства

 Объект исследования: изучение свойств  графов.

Предмет исследования: установление  зависимость  количество ребер графа от количества его вершин.

Понятие графа. Простейшие свойства

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

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

Если две различные вершины графа соединены ребром, то такие вершины называются смежными. Количество ребер, выходящих из одной вершины, называется степенью этой вершины. Для петли будем считать, что это ребро выходит из вершины дважды. Степень вершины а будем обозначать v(а).

Свойство, относящееся к любым графам.

Теорема 1. Сумма степеней всех вершин графа равна удвоенному числу его ребер.

Лемма о рукопожатиях. Теорема 2. Количество вершин нечетной степени любого графа всегда четно.

Маршрутом на графе называется последовательность ребер е1, е2, …, еk, в которой конец одного ребра служит началом следующего. Если при этом конец последнего ребра последовательности совпал с началом первого ребра, то маршрут называется циклическим. Для графа, изображенного на рис. 2, последовательности е1, е2, е4, е5, е2, е3 и е2, е4, е5 являются маршрутами, причем второй из них — циклический. А последовательность е1, е2, е5 маршрутом не является. Рис. 2

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

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

При решении задачи мы увидели закономерность, которая подтвердилась при анализ большого количества примеров. На сайте  http://rain.ifmo.ru/cat/view.php/theory/graph-general/random-2005   факультета  «Информационных технологий и программирования», кафедра компьютерных технологий в разделе «Дискретная математика: алгоритмы» в теме  «Модель Эрдёша-Реньи»   упоминается формула   максимального количество ребер, что совпадает с первым столбцом нашего исследования. О решении задачи информация нам не попалась, было просмотрено около 10 сайтов по данной теме. На просмотренных сайтах мы не нашли решение данной задачи:

При построении  схем графов участвовали все учащиеся класса. Сложность построения заключается в том, чтобы не пропустить ребер, правильно их посчитать. Для построения использовался векторный графический редактор, встроенный в текстовый редактор «Word».

Вывод теоретический  . Рассмотренная задача решена практическим методом построения последовательности графов. Для графов с вершинами без петель  зависимость  количество ребер графа от количества его вершин выражается формулой R=N*(N-1)/2. Для графов с вершинами с петлями  зависимость  количество ребер графа от количества его вершин выражается формулой R= N +N *(N-1)/2.

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

Литература

Информатика и ИКТ,  А.Г. Гейн, А.И. Сенокосов, Москва, «Просвещение» 2009.

Электронные ресурсы

1. http://inf.1september.ru/article.php?ID=200702001
2. http://elar.urfu.ru/bitstream/10995/1659/5/1334886_schoolbook.pdf 
3. http://rain.ifmo.ru/cat/view.php/theory/graph-general/random-2005