8(495)912-63-37 
gmc@edu.mos.ru
FacebookВКонтактеYouTubeInstagram

Среда, 19 Май 2021 10:45

Рабочая программа учебного курса по выбору «Графы и их применение»

Программа рассчитана для учащихся 9-х классов.

Программа предусматривает индивидуальные, групповые и иные формы работы.

Режим занятий: 1 занятие 45 мин. 1 раз в неделю.

Срок реализации программы – 1 год (34 часа)

I. Планируемые результаты

Выпускник научится:

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

II. Содержание курса

Основные разделы программы учебного курса.

Раздел 1. Основные понятия теории графов.

Введение в теорию графов: экскурс в историю возникновения и развития теории графов. Сведения о приложениях теории графов (примеры). Понятия граф, вершина и ребро графа. Степень вершины графа. Смежность вершин и ребёр графа. Виды графов: простой граф, мультиграф, гипперграф, псевдограф, орграф и др. Пустой и полный граф. Двудольный граф. Способы задания графа. Лемма о рукопожатиях и следствие из неё. Решение задач с использованием различных видов графов.

Раздел 2. Обходы в графах.

Определение маршрута, виды маршрутов: замкнутый маршрут; цепь; цикл; простая цепь; простой цикл. Связные и несвязные графы. Алгоритмы поиска маршрутов в графе в ширину и глубину. Задачи на нахождение цикла, цепи, поиск кратчайшего маршрута. Задача о кёнигсбергских мостах. Эйлеров граф. Гамильтонов граф. Игра Гамильтона «Кругосветное путешествие» и её близость к практическим задачам. Фигуры, обводимые одним росчерком.

Раздел 3. Деревья.

Понятие «дерево». Их свойства. Понятия нагруженного графа, остовного дерева. Вес ребра, минимальное остовное дерево. Алгоритмы Краскала и Прима. Задачи на построение дерева вариантов.

Раздел 4. Укладка графа.

Понятие плоские, планарные графы. Укладка графа на плоскости и в пространстве. Задача «о трёх домах и трёх колодцах». Грани плоского графа. Формула Эйлера. Критерий планарности графа.

Раздел 5. Раскраски графов.

Вершинная k-раскраска графа, краски, цвета. Алгоритм последовательной раскраски. Хроматическое число. Оценка хроматического числа. Хроматическая функция. Понятие плоские, планарные графы. Раскраска планарных графов. Карта. Проблема четырёх красок.

Раздел 6. Ориентированные графы.

Основные понятия ориентированного графа. Гамильтоновы и эйлеровы ориентированные графы. Турниры.

Раздел 7. Приложение теории графов.

Логические задачи, задачи на оптимизацию. Сетевое планирование и управление. Сетевые графики. Критический путь. Решение задач из смежных дисциплин.

III. Тематическое планирование

Название разделов

Всего

1.

Основные понятия теории графов

6

2.

Обходы в графах

8

3.

Деревья

4

4.

Укладка графа

4

5.

Раскраски графов

4

6.

Ориентированные графы

4

7.

Приложения теории графов

4

 

Всего:

34