Открытый урок по Дискретной математике «Двудольные графы. Полный двудольный граф. Изоморфные графы»

Федеральное агентство по образованию ФГОУ СПО

Тольяттинский политехнический колледж

«УТВЕРЖДАЮ»

заместитель директора

по учебной работе

_________С.А.Гришина

ПЛАН

открытого урока по Дискретной математике

Тема: «Двудольные графы. Полный двудольный граф. Изоморфные графы»

Группа: В-21

Дата проведения: 08.11.06

Преподаватель: Малова Е.С.

Рассмотрено на заседании
цикловой комиссии
по специальности «Информатика и ВТ»
Председатель комиссии
________Л.Г. Светличная

2006

План открытого урока

Группа В-21 курс 2

Тема урока: Двудольные графы. Полный двудольный граф. Изоморфные графы.

1. Цели урока.

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

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

Воспитательные: воспитывать аккуратность, познавательную активность, внимание и организованность.

2. Основные знания и умения:

Знать: определение двудольного графа, полного двудольного графа, изоморфного графа.

Уметь: проверять граф на двудольность, проверять пару графов на изоморфность.

3. Вид урока: комбинированный урок.

4. К уроку приготовить: компьютер, плакат, рисунки в программе WORD

5. Содержание и ход урока:

• Организационный момент-2 мин.

• Проверка домашнего задания и опрос-10 мин.

1. Проверка домашнего задания: решение задач (у доски)

2. Опрос по определениям, пройденным на уроках №33, №34

   • Объяснение нового материала-40 мин

1. Двудольные графы

2. Полный двудольный граф

3. Изоморфные графы

4. Методика проверки пары графов на изоморфность

   • Заключение и закрепление материала -25 мин

1.Решение задач

2. Подведение итогов урока, оценки за урок

• Домашнее задание-3мин.

1. Пояснение к домашнему заданию

Подпись

Число 08.11.06г.

Конспект урока

Здравствуйте, садитесь.

Отмечаются отсутствующие.

Проверка домашнего задания и опрос

1. Решение домашнего задания у доски

2. Опрос

• Свойства отображений (сюръекция, инъекция, биекция)

• Понятие сюръекции (каждый элемент множества имеет свой прообраз)

• Понятие инъекции (для каждого элемента существует не более одного прообраза)

• Понятие взаимно однозначного отображения (сюръекция и биекция)

• Определение графа (Граф G(V,E) представляет собой не пустое множество точек V и множество отрезков E, оба конца которых принадлежат заданному множеству точек.)

• Понятие цикла в графе (Цепь называется циклом, если начальная и конечная вершины цепи равны)

Определение простого цикла (Цикл называется простым, если все его вершины различны).

• Определение длины цикла (Число ребер цикла называют его длиной.)

• Определение степени вершины (число ребер выходящих из нее)

• Понятие смежных вершин (Две вершины называются смежными, если существует соединяющее их ребро)

Объяснение нового материала

Двудольный граф- это граф, у которого множество вершин V разбивается на два непересекающихся множества V₁ и V₂, причем всякое ребро из множества E соединяет вершину из V₁ с вершиной из V₂. Множества V₁ и V₂ называются долями двудольного графа. Если двудольный граф содержит все ребра, соединяющие множества V₁ и V₂, то он называется полным двудольным графом.

Теорема. Граф является двудольным, если все его простые циклы имеют четную длину.

Пример полного двудольного графа показываю на плакате. Комментарий: верхние три вершины на рисунке 1 содержатся во множестве V₁, нижние принадлежат множеству V₂.

Рисунок 1.

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

Рисунок 2.

Графы называются изоморфными, если существует взаимнооднозначное соответствие между их вершинами и ребрами и такое, что соответствующие ребра соединяют соответствующие вершины.

Существует два способа проверки графов на изоморфность:

1способ: В каждом графе определить

• число вершин

• число ребер

• степень каждой вершины

• смежность соответствующих вершин

Если результаты совпадают, то графы изоморфны, иначе не изоморфны

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

Пример. Построить к звездочке изоморфные графы (показывается на компьютере, а студенты зарисовывают графы, полученные на рисунке 3)

1 2 3

Рисунок 3.

Проверяется правильность решения задачи:

1 2 3

v=5 v=5 v=5 вершины

r=5 r=5 r=5 ребра

d=2 d=2 d=2 степень каждой вершины

Смежные вершины показываются указкой.

Все пункты проверки графов на изоморфность совпадают, значит, графы изоморфны.

Заключение и закрепление материала

Задание представлено на компьютере

1. Являются ли следующие графы двудольными?

а) б)

Решение: а) Граф является двудольным, так как все его простые циклы имеют четную длину

Все простые циклы графа представлены на рисунке 3. Эти циклы студент должен обнаружить на графе.

Рисунок 3.

Убеждаемся, что в каждом цикле по 4 ребра, то есть длина циклов четное число.

б) Граф является двудольным, так как все его простые циклы имеют четную длину

Все простые циклы графа представлены на рисунке 4. Эти циклы студент должен показать на графе б)

Рисунок 4.

2. Изоморфны ли графы

а)

Графы не изоморфны, так как количество вершин не совпадает.

б)

Графы не изоморфны, так как во втором графе отсутствует одно ребро

в)

Графы изоморфны. Все пункты проверки графов на изоморфность выполняются

г)

Графы изоморфны. Все пункты проверки графов на изоморфность выполняются.

д)

Графы изоморфны. Все пункты проверки графов на изоморфность выполняются.

3. Построить графы изоморфные к данному графу

Решение

2 3

Проверяется правильность решения задачи:

1 2 3

v=6 v=6 v=6 вершины

r=6 r=6 r=6 ребра

d=2 d=2 d=2 степень каждой вершины

Смежные вершины показываются указкой.

Подведение итогов урока:

1. Какие графы называются двудольными?

2. Как определить является ли граф двудольным?

3. Какие графы называются изоморфными?

4. Как проверить пару графов на изоморфность?

Домашнее задание

1. Построить графы изоморфные к данному

Спасибо за урок. До свидания

Приложение

Решение домашнего задания к открытому уроку:

Определить все простые циклы графа

2

3

5

6

7

1

4

8

9

Решение

(1,2,3,1) (1,4,3,1) (5,6,7,5) (5,8,9,5) (1,2,3,4,1)

Литература

1. Березина Л. Ю. Графы и их применение. М.: Просвещение, 1978г.

2. Гончарова Г.А. Элементы дискретной математики. М.: Форум-Инфра - М, 2003г.

3. Новиков Ф.А. Дискретная математика для программистов. М.: Питер,2002г.