Графы в информатике конспект

Обновлено: 30.06.2024

Автор: Гатина Рузиля Маратовна

Населенный пункт: Республика Татарстан, г. Нурлат

Пояснительная записка

Обеспечить усвоение понятий графы, вершины, применять эти знания в практической деятельности.
Развивать логическое и пространственное мышление, умение обобщать и делать выводы, применять знания в новой ситуации.
Повышать ИКТ-компетенцию учащихся.
Способствовать развитию интереса к предмету через показ его практической значимости, воспитанию привычки работать осмысленно и упорядоченно, согласно инструкции.
Содействовать воспитанию интереса к предмету информатика и ИКТ, воспитывать чувство коллективизма, самоконтроля, ответственности.

Данная работа может быть использована для преподавания информатики и ИКТ в средней общеобразовательной школе.

Методическая разработка урока информатики по теме

Предмет информатика
Класс, характеристика класса 9 класс

5. Образовательные результаты, на достижение которых направлено содержание урока:

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

7. Используемые оборудования компьютер, видеопроектор, записи на доске, презентация, мобильный телефон.

В данный момент вы не можете посмотреть или раздать видеоурок ученикам

Чтобы получить доступ к этому и другим видеоурокам комплекта, вам нужно добавить его в личный кабинет, приобретя в каталоге.

Получите невероятные возможности

Конспект урока "Графические информационные модели. Графы"

Граф – это совокупность объектов со связями между ними. Графически это будет выглядеть следующим образом:

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

На данном уроке мы с вами познакомимся с ориентированными и неориентированными графами. В ориентированном графе связями между вершинами будут дуги, а в неориентированном – рёбра.

Решим задачу: В соревнованиях по шахматам участвовало 6 учащихся с 9 по 11 класс. При встрече они все обменялись рукопожатиями. Вопрос: сколько всего было сделано рукопожатий?

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

Для ответа на вопрос остается сосчитать, сколько линий изображено на графе. Ответ: на турнире было сделано 15 рукопожатий.

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

Давайте сами нарисуем взвешенный граф на основе задачи со следующим условием: Между городами A, B, C, D, Е построены дороги. Необходимо найти кратчайший путь из города А в город Е, если известно, что из города А в город В расстояние 100 километров, из А в С – 260 километров, из В в С – 140 километров, из В в Е – 400 километров, из С в D – 50 километров, из С в Е – 100 километров и из D в Е – 40 километров.

Итак, для решения данной задачи необходимо нарисовать взвешенный граф, так как нам дано расстояние, то есть вес рёбер. Для начала нарисуем вершину А. Из неё будут выходить два ребра в вершины В и С. Ребро из А в В будет короче, чем из А в С, так как расстояние из пункта А в пункт В 100 километров, а из пункта А в пункт С – 260 километров.

Далее нарисуем ребро из В в С и его вес будет равен 140.

Теперь нарисуем ребро из вершины С в вершину D и укажем вес 50

У нас получился взвешенный граф.

Нам осталось найти кратчайший путь. Для этого из вершины А будем идти в вершину В – это 100 километров, затем сразу в вершину Е. Слаживаем 100 и 400, получим 500 километров.

Аналогичным образом проходим по остальным рёбрам и получим, что путь через вершины A, B, C, E равен 340 километров. Через вершины A, C, E 360 километров. A, B, C, D, E - 330, A, C, B, E 800 километров и через вершины A, C, D, E равен 350 километров. Нам необходимо выбрать кратчайший – это путь через города A, B, C, D, E и равен он 330 километров.

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

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

Разберём ещё один пример. У Антона в семье есть мама Татьяна, папа Юрий и сестра Маша. Изобразим каждого члена семьи как вершину нашего графа и обозначим первыми буквами имён. От каждого из них проведём рёбра к оставшимся троим. Над каждым из рёбер укажем, кто кем и кому приходится. Например, если идти от вершины Антона к Юрию, то Антон является сыном. А если идти наоборот, от Юрия к Антону, то Юрий является отцом. Аналогичным образом можно провести отношения между всеми членами семьи. Данный граф является примером семантической, или же смысловой сети.

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

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

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

Разберёмся более подробно на примере:

Ученик Антон решил составить генеалогическое дерево своей семьи. Для этого ему необходимо было узнать, кто в каких отношениях находится. То есть он является сыном своего отца Юрия и мамы Татьяны. В свою очередь Татьяна является дочерью Леонида (дедушки Антона) и Елены (бабушки Антона). Юрий является сыном Григория (дедушки Антона) и Марии (бабушки Антона). У Антона есть сестра Маша. Так как словесное описание трудно для восприятия, давайте поможем Антону представить это все в виде дерева и построим генеалогическое дерево.

Видим, что самыми старшими являются дедушки и бабушки Антона, поэтому расположим их в самом верху. У Леонида и Елены есть дочь Татьяна, а у Григория и Марии сын Юрий. Значит, разместим их на втором уровне (если считать сверху) и укажем их отношения с родителями в виде стрелок. У Татьяны и Юрия есть сын Антон и дочь Маша. Разместим их аналогичным образом на нашей схеме.

Таким образом, мы построили родословное дерево.

Важно запомнить:

· Граф – это совокупность объектов со связями между ними.

· Вершины – это объекты, а ребра – это связи.

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

· Цепь – это путь по вершинам и рёбрам графа, в который любое ребро графа входит не более одного раза.

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

· Сеть – это граф с циклом.

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

· Дерево – это граф, в котором нет циклов, то есть в нём нельзя из некоторой вершины пройти по различным рёбрам и вернуться в ту же вершину.
- Для учеников 1-11 классов и дошкольников
- Бесплатные сертификаты учителям и участникам
Конспект урока

Дата проведения: 09 .03.2016 г.

Методист (Захарова Н.В.)

Учитель (Захарова Н.В.)

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

Задачи урока:

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

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

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

Тип урока: комбинированный (рассказ с элементами визуализации и практическая работа).

Оборудование: мультимедийный проектор, интерактивная доска для показа презентаций, компьютерный класс с ПО MSOfficeExcel 2007.

Организационный момент (1 минута)

Домашнее задание (1 минута)

Проверка домашнего задания (5 минут)

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

Дата проведения: 15.03.2016 г.

Методист (Захарова Н.В.)

Учитель (Захарова Н.В.)

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

Задачи урока:

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

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

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

Тип урока: комбинированный (рассказ с элементами визуализации и практическая работа).

Оборудование: мультимедийный проектор, интерактивная доска для показа презентаций, компьютерный класс с ПО MSOfficeExcel 2007.

Организационный момент (1 минута)

Домашнее задание (1 минута)

Проверка домашнего задания (5 минут)

Изложение нового материала (15 минут)

Физ. минутка (1 минута)

Закрепление нового материала (2 минута)

Практическая работа (14минут)

Итог урока (1 минута)

Организационный момент (1 минута)

Учитель: Здравствуйте, ребята. Садитесь. Сегодня на уроке мы проверим ранее изученную вами тему, затем изучим новый материал, закрепим его и выполним практическую работу, после чего подведем итоги урока. Для начала отметим отсутствующих. ( Отмечает отсутствующих ).

Домашнее задание (1 минута)

Учитель: Открываем дневники и записываем задание на следующий урок:

Проверка домашнего задания и ранее изученного материала (5 минут).

Учитель: На прошлом уроке мы изучали тему? (Многообразие схем)

Фамилия ученика__________ Какие способы представления информации представлены на слайде?

Учитель : Что такое схема?

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

Учитель: Что такое блок-схема?

Ученик: Блок - схема – это один из наиболее наглядных способов записи алгоритмов, при котором каждому действию ставится в соответствие определенная геометрическая фигура.

Учитель: На слайде представлены условные обозначения блок-схемы, что они обозначают?

Изложение нового материала (15 минут).

Ребята, как вы считаете, есть ли что-то общее у диаграмм, графиков, схем и графов?

Ученики : Да, есть. Они служат для визуализации данных, для наглядного представления.

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

Посмотрите на слайд. Перед вами изображен граф.

Граф состоит из вершин, связанных линиями.

Направленная линия (со стрелкой) называется дугой.

Ненаправленная линия (без стрелки) называется ребром.

Граф называется неориентированным, если его вершины соединены ребрами.

Граф называется ориентированным , если его вершины соединены дугами.

Линия, выходящая из некоторой вершины и входящая в нее же, называется петлей .

Путь по вершинам и ребрам графа, включающий любое ребро графа не более одного раза, называется цепью . (Например, Юра — Аня — Витя — Коля).

Цепь, начальная и конечная вершины которой совпадают, называется циклом. (Например, Аня — Коля — Витя — Аня).

Граф называется взвешенным , если его вершины или ребра (дуги) характеризуются некоторой дополнительной информацией – весом вершины или ребра (дуги). Предположим, что наш граф – это информация о городах Золотого кольца. Веса его вершин – года основания городов, веса ребер – расстояния в километрах между городами.

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

Физ.минутка (1 минута)

Ах, как долго мы писали,
Глазки у ребят устали.
(Поморгать глазами)
Посмотрите все в окно
(посмотреть вправо-влево)
Ах, как солнце высоко
( посмотрите вверх)
Мы глаза сейчас закроем,
( закрыть глаза ладошками)
В классе радугу построим
Вверх по радуге пойдём,
(Посмотреть по дуге вверх - влево и вверх - вправо)
Вправо-влево повернём,
А потом скатимся вниз,
( Посмотреть вниз)
Жмурься сильно, но держись
( Зажмурить глаза. Открыть и поморгать ими)

Закрепление материала (4 минута)

Учитель: Ребята, посмотрите на слайд, ответьте, что вы видите?

Ученики: Граф.

Учитель: Верно, а назовите вид этих графов?

Ученики: 1 - неориентированный, 2 – ориентированный.

Учитель: Хорошо. Перед вами граф. Назовите, какой путь в данном случае будет называться цепью, а какой циклом?

Ученики: Цепь: Аня — Юра — Маша. Цикл: Аня — Витя — Коля — Аня.

Учитель: Молодцы. Теперь вам предстоит ответить, какой из предложенных графов, является ориентированным?

Загрузить презентацию (915 кБ)
- компьютерный класс, оснащенный современной техникой, видеопроектор, экран;
- компьютеры с ОС Windows XP, программа Microsoft Office 2003 PowerPoint;
- оборудование доски (тема урока, новые термины). Раздаточный материал.
I. Организационный момент. Актуализация знаний.

II. Изложение нового материала. (10 мин. )

III. Закрепление материала. Практическая работа. (15-20 мин.)

IV. Подведение итога урока.(2 мин)

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

I. Организационный момент. Актуализация знаний.

Здравствуйте! Наш урок называется “Графы”. Мы познакомимся с понятие “Графы”, научимся их изображать и решать задачи по этой теме.

II Изложение нового материала.

Первая работа по теории графов принадлежит Леонарду Эйлеру (1736 г.), хотя термин “граф” впервые ввел в 1936 году венгерский математик Денеш Кениг. Графами были названы схемы, состоящие из точек и соединяющих эти точки отрезков прямых или кривых (примеры графов изображены на рисунке 1)

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

Граф – (от греческого grapho – пишу) - это средство наглядного представления элементов объекта связей между ними. Это замечательные математические объекты, с их помощью можно решать очень много различных, внешне не похожих друг на друга задач.

Граф – это некоторая информационная модель

Граф состоит из вершин или узлов, связанных дугами или отрезками - рёбрами. Линия может быть направлена, т. е. иметь стрелку (дуга), если не направлена – ребро. Две вершины, соединённые дугой или ребром называются смежными.

Примеры графов (Слайд 4, 5, 6)

Задание 1 (Слайд 7):

Земля – Меркурий; Плутон – Венера; Земля – Плутон; Плутон – Меркурий; Меркурий – Венера; Уран – Нептун; Нептун – Сатурн; Сатурн – Юпитер; Юпитер – Марс; Марс – Уран.

Можно ли долететь на рейсовых ракетах с Земли до Марса ?

Решение: Нарисуем схему условия: планеты изобразим точками, а маршруты ракет – линиями.

Теперь сразу видно, что долететь с Земли до Марса нельзя.

Две вершины, соединённые дугой или ребром называются смежными. Каждому ребру или дуге соотносится какое-нибудь число. Число может обозначать расстояние между населёнными пунктами, время перехода от одной вершины к другой и т. д.

Задание 2 (9 слайд) – решение у доски. Маша пришла в зоопарк и хочет увидеть как можно больше зверей. По какой тропинке ей надо идти? Желтая, красная, зеленая?

Задание 3 (11 слайд) – решение у доски. Пять футбольных команд А, Б, В, Г, Д должны сыграть в матчи друг с другом. Уже сыграли А с Б, В, Г; Б с А, В, Д. сколько матчей уже сыграно? Сколько осталось сыграть?

Представление графов (Слайд 12)

Граф может быть представлен в виде списка дуг (АВ; 7), графически или с помощью таблицы.

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

Задание 2 (Слайд 13)

Задание 3 (Слайд14)

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

- Что могут обозначать вершины графа? (Города; объекты, которые; связаны.)

Читайте также: