"Информационные модели на графах"
план-конспект урока по информатике и икт (7 класс) на тему

Деятельность учителя

Деятельность ученика

Организационный момент

Приветствие, проверка отсутствующих

Актуализация знаний

Актуализация знаний может иметь два варианта: классический – опрос учащихся или компьютерное тестирование (приложение 2)

Классический вариант:

Давайте вспомним, что мы называем схемой?

Для чего мы используем схемы?

Какие виды схем вы знаете?

Схема – это представление некоторого объекта в общих, главных чертах с помощью условных обозначений.

Схемы мы используем для представления внешнего вида объекта и его структуры.

Географическая карты, схема метро, схема движения автотранспорта, схема эвакуации.

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

Мы с вами повторили, что схемы нам  дают представление о некоторых объектах в виде условных обозначений и знаков.

Но иногда нам необходимо представление систем некоторых объектов и ее структуры, например, в наглядном виде представленные дороги, которые соединяют населенные пункты. Для этого представления мы будем использовать графы.

Итак, записываем тему нашего урока «Графы. Понятие и виды графов» (слайд 1)

Граф – это наглядное средство представления состава и структуры системы в виде совокупности вершин и линий, соединяющих данные вершины.

Граф состоит, как мы уже сказали, из вершин. Они могут обозначаться точкой, кружочком или прямоугольником (слайд 2)

Некоторые вершины связанны друг с другом линиями. Если линия направлена (со стрелкой), то она называется дугой и граф имеет название ориентированным. В ориентированном графе можно передвигаться от вершины к вершине только по стрелкам в том направлении, которое они показывают.

Если линия ненаправленная, то она называется ребром графа, а граф имеет название неориентированный. В неориентированном  же графе можно передвигаться от вершины к вершине в любом направлении.

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

В графе различают: цепь и цикл.

Цепь – это путь по вершинам и ребрам (дугам) графа не более одного раза (слайд 3)

Например, Юра – Аня – Витя – Коля.

Назовите еще пример цепи по данному графу.

Цикл – это цепь, у которой начальная и конечная вершины совпадают.

Давайте вместе определим, где в данном графе будут циклы.

Мы сейчас с вами работали с графом неориентированным, теперь назовите мне цепи и циклы в следующем графе, который является ориентированным (слайд 4)

Молодцы! Различают еще один вид графа – взвешенный граф. Бывают ситуации, когда на вершинах графа, его ребрах или дугах нам необходимо добавить информацию.

Например, это может быть такой граф «города Золотого кольца» (слайд 5)

Что здесь будет являться вершинами графа?

Какой это будет граф и почему?

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

Итак, давайте теперь подумаем, какую информацию мы можем добавить к вершинам?

Хорошо, добавим к вершинам год основания.

А какую информацию можно добавить к ребрам?

Молодцы, давайте отразим расстояние между городами (слайд 5).Таким образом, мы получили с вами взвешенный граф.

Запишем, что

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

Как правило, ребра (дуги) графа описывают однородные отношения между объектами некоторой системы. Но бывают случаи, когда нам необходимо, чтобы ребрами (дугами) были отражены разнородные отношения между объектами. Например, давайте посмотрим граф, представляющий информационную модель сказки про Царевну-лягушку (слайд 6)

Что на представленном графе будет являться его вершинами?

А какой это будет граф и почему?

Да верно, как вы видите, весом каждой дуги является отношение между объектами сказки, причем отношения разные: «нашел», «превратилась», «победил» и т.д.

Такой граф называется семантической сетью.

Запишем:

Семантическая сеть – это граф, на котором отражены объекты (понятия) и связи (отношения) между ними.

записывают тему урока

записывают определение в тетрадь

записывают за учителем и рисуют примеры с презентации

Ориентированным графом можно представить отношение «меньше» между некоторыми целыми числам, а неориентированным – отношение «учиться в одном классе» между учащимися школы.

Маша – Юра – Аня – Витя – Коля.

Маша – Аня – Коля – Витя.

Аня – Коля – Витя – Аня.

Маша – Аня – Юра – Маша.

Цепь: Аня – Юра – Маша

Цикл: Аня – Витя – Коля – Аня

Вершинами графа являются названия городов Золотого кольца

Граф будет неориентированный, потому что  его вершины соединены ребрами

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

На ребрах можно отразить значение расстояний между городами, а еще можно отразить, сколько времени в пути затрачивается.

Записывают определения в тетрадь

Вершинами графа будут являться персонажи и объекты из сказки

Это будет ориентированный граф, потому что вершины соединены дугами, и взвешенный граф, потому что у дуг есть вес.

Записывают определения в тетради.

Первичное закрепление изученного материала

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

Каждому ученику раздаются карточки с заданиями (приложение 1)

Задание 1. Начертите граф, на котором были бы изображены высказывания «кратно» между числами 15, 3, 4, 12, 5, 6, 1, 2.

Сначала определим, что будет являться вершинами графа?

Какой это будем граф и почему?

Почему в данном случае вершины будут соединены дугами?

Все верно, располагаем вершины и соединяем их дугами. Еще раз повторим, что дуги будут обозначать отношение «кратно»

Построение вместе с учащимся у доски.

Задание 2.

Составьте граф, отражающий расстояние между городами Нижегородской области по следующему тексту:

Расстояние между Арзамасом и Балахной 143 км. Расстояние между Кулебаками и Бором 218 км. Расстояние между Нижним Новгородом и Балахной 184 км. Расстояние между Павловом и Нижним Новгородом 75 км. Расстояние между Выксой и Арзамасом 129 км. Расстояние между Нижним Новгородом и Бором 34 км. Расстояние между Павловым и Балахной 105 км. Расстояние между Арзамасом и Кулебаками 91 км. Расстояние между Нижним Новгородом и Выксой 180 км. Расстояние между Арзамасом и Нижним Новгородом 106 км.

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

Правильно, а будет ли граф содержать какую-то дополнительную информацию? Будет ли он являться взвешенным?

Давайте, попробуем его построить.

Вызывает учащегося к доске.

Вершинами графа будут являться числа.

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

Потому что, отношение «кратно» может быть выполнено только в одну сторону, так как «15 кратно 3», но не может быть, что «3 кратно 15»

Выполняют задание:

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

Да, граф будет взвешенным, он содержит информацию от протяженности в километрах между городами. Информация будет отражена в виде веса ребра.

Выполняют задание

Подведение итога урока. Домашнее задание

Мы сегодня с вами изучили еще один вид информационных моделей, это графы.

Давайте еще раз вспомним, что же это такое?

Какие бывают графы и как они отличаются?

Правильно.

А теперь записываем домашнее задание:

1. §2.10 (стр.101 – 104) учить.
   
2. §2.10 (стр.97 – 101) повторить
   
3. Творческое задание: изменить граф «города Нижегородской области» таким образом, чтобы весом ребра стало время пути между городами. Добавить вес вершины (год основания, численность жителей, площадь и т.д.) – по выбору учащегося.

Граф – это наглядное средство представления состава и структуры системы в виде совокупности вершин и линий, соединяющих данные вершины.

Графы бывают ориентированные, если их вершины соединены дугами (стрелками) и неориентированные, если их вершины соединены ребрами (линиями).

Если на графе отображена дополнительная информация на вершинах или ребрах (дугах), то граф называется взвешенным.

Записывают домашнее задание.

Задание 1. Начертите граф, на котором были бы изображены высказывания «кратно» между числами 15, 3, 4, 12, 5, 6, 1, 2.

Задание 2.

Составьте граф, отражающий расстояние между городами Нижегородской области по следующему тексту: Расстояние между Арзамасом и Балахной 143 км. Расстояние между Кулебаками и Бором 218 км. Расстояние между Нижним Новгородом и Балахной 184 км. Расстояние между Павловом и Нижним Новгородом 75 км. Расстояние между Выксой и Арзамасом 129 км. Расстояние между Нижним Новгородом и Бором 34 км. Расстояние между Павловым и Балахной 105 км. Расстояние между Арзамасом и Кулебаками 91 км. Расстояние между Нижним Новгородом и Выксой 180 км. Расстояние между Арзамасом и Нижним Новгородом 106 км.

Задание 1. Начертите граф, на котором были бы изображены высказывания «кратно» между числами 15, 3, 4, 12, 5, 6, 1, 2.

Задание 2.

Составьте граф, отражающий расстояние между городами Нижегородской области по следующему тексту: Расстояние между Арзамасом и Балахной 143 км. Расстояние между Кулебаками и Бором 218 км. Расстояние между Нижним Новгородом и Балахной 184 км. Расстояние между Павловом и Нижним Новгородом 75 км. Расстояние между Выксой и Арзамасом 129 км. Расстояние между Нижним Новгородом и Бором 34 км. Расстояние между Павловым и Балахной 105 км. Расстояние между Арзамасом и Кулебаками 91 км. Расстояние между Нижним Новгородом и Выксой 180 км. Расстояние между Арзамасом и Нижним Новгородом 106 км.

Задание 1. Начертите граф, на котором были бы изображены высказывания «кратно» между числами 15, 3, 4, 12, 5, 6, 1, 2.

Задание 2.

Составьте граф, отражающий расстояние между городами Нижегородской области по следующему тексту: Расстояние между Арзамасом и Балахной 143 км. Расстояние между Кулебаками и Бором 218 км. Расстояние между Нижним Новгородом и Балахной 184 км. Расстояние между Павловом и Нижним Новгородом 75 км. Расстояние между Выксой и Арзамасом 129 км. Расстояние между Нижним Новгородом и Бором 34 км. Расстояние между Павловым и Балахной 105 км. Расстояние между Арзамасом и Кулебаками 91 км. Расстояние между Нижним Новгородом и Выксой 180 км. Расстояние между Арзамасом и Нижним Новгородом 106 км.

Задание 1. Начертите граф, на котором были бы изображены высказывания «кратно» между числами 15, 3, 4, 12, 5, 6, 1, 2.

Задание 2.

Составьте граф, отражающий расстояние между городами Нижегородской области по следующему тексту: Расстояние между Арзамасом и Балахной 143 км. Расстояние между Кулебаками и Бором 218 км. Расстояние между Нижним Новгородом и Балахной 184 км. Расстояние между Павловом и Нижним Новгородом 75 км. Расстояние между Выксой и Арзамасом 129 км. Расстояние между Нижним Новгородом и Бором 34 км. Расстояние между Павловым и Балахной 105 км. Расстояние между Арзамасом и Кулебаками 91 км. Расстояние между Нижним Новгородом и Выксой 180 км. Расстояние между Арзамасом и Нижним Новгородом 106 км.