План - конспект открытого урока на тему «Основы теории графов » по дисциплине «дискретная математика» (стр. 1 )

Государственное бюджетное образовательное учреждение Астраханской области

среднего профессионального образования

«Астраханский колледж вычислительной техники»

план - конспект

открытого урока

на тему «основы теории графов »

по дисциплине «дискретная математика»

Составил преподаватель                                                        

Рассмотрено на заседании цикловой комиссии специальности 230105 «Программное обеспечение вычислительной техники и автоматизированных систем»

Протокол №__ от «__»___________20  г.

Председатель цикловой комиссии                                                

2012

Тема урока

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

Тип урока

Урок систематизации и обобщения знаний

Вид урока

Урок - игра

Цели урока

Дидактическая:

- обобщить и  систематизировать знания о свойствах, характеристиках и видах графов.

Развивающая:

- способствовать развитию профессиональной любознательности и стремлению использовать практические навыки в будущей профессии;

- развивать логическое мышление, память и внимательность.

Воспитательная:

- развивать познавательный интерес;

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

Дидактические средства ПЭВМ Проектор Интерактивная доска Средства SMART Board
Межпредметные связи Информационные технологии Математические методы Информатика План урока Организационный момент (5 мин) Основной этап урока (30 мин) Этап 1 «Истина или ложь» Этап 2 «Кроссворд» Этап 3 «Найди пару» Подведение итогов (5 мин) Домашнее задание (5 мин)
Ход урока Организационный момент

Здравствуйте!

Объявление темы урока, целей урока (отметить отсутствующих).

Тема нашего сегодняшнего занятия – «Основы теории графов».

Цель занятия – повторение и обобщение полученных ранее знаний по разделу «Основы теории графов». Мы вспомним основные понятия теории графов, свойства, характеристики, виды графов. Сегодня мы проведем наш урок  в виде игры, которая состоит из 3 этапов. Итак, начнем игру!

Основной этап урока Этап 1 «Истина или ложь»

Вам даются утверждения и необходимо определить истинно оно или ложно. Ответ нужно пояснить.

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

Ответ: ложь, т. к. дерево – это связный граф не содержащий циклов

2. Ребро ab – это петля?

Ответ: ложь, т. к. петлей называется ребро у которого начало и конец совпадают. Петля это ребро сс

3. Кратчайший путь из вершины а в вершину d равен 6?

Ответ: ложь, т. к. кратчайший путь из вершины а в вершину d равен 5

4. Лист – это ребро, объединяющее две вершины

Ответ: ложь, т. к. лист - концевая вершина дерева (v1, v3, v5, v6)

5. Данный граф является звездным?

Ответ: истина, т. к. звездный граф – это граф, в котором одна из вершин является концевой для всех ребер.

6. Данный граф является полным?

Ответ: истина, т. к. полный граф – это такой граф, между любыми двумя вершинами которого есть ребро.

7. Данный граф является транспортной сетью?

Ответ: ложь, т. к. транспортная сеть это ориентированный граф

8. Ребра ab и bd кратные

Овтет: ложь, т. к. кратными называются два ребра, принадлежащие одной и той же паре вершин.

9. Вершинная раскраска данного графа верная

Ответ: истина, т. к. раскраской графа называется такое приписывание цветов его вершинам, что никакие две смежные вершины не получают одинаковый цвет.

Этап 2 «Кроссворд»

Необходимо решить 9 кроссвордов. После чего мы узнаем 9 основных понятий из раздела.

Вариант 1

			м	а	т	р	и	ц	а
								1							2
	3	4										5
					6					7
		8
								9
						10

ПО ГОРИЗОНТАЛИ:

3. Число (γ) графа, которое показывает минимальное количество ребер, которое необходимо изъять из графа, чтобы он стал деревом?

8. Линия, связывающая между собой вершины графа?

9. Вершина в самой верхней части каждого дерева?

10. Свойство вершин,  при котором две вершины принадлежат одному и тому же ребру?

ПО ВЕРТИКАЛИ:

1. Вершина, в которую входят дуга в транспортной сети?

2. Путь из корня в лист?

4. Числовая характеристика, одинаковая для всех изоморфных графов?

5. Число ребер, инцидентных данной вершине?

6. Совокупность вершин и ребер?

7. Точка, где могут сходиться/выходить рёбра и/или дуги?

Вариант 2

				д	е	р	е	в	о
						1
												2
		3
					4					5
				6
			7
												8
									9
				10

ПО ГОРИЗОНТАЛИ: