Ориентированные и неориентированные графы. Дерево, корень, вершина, лист, ребро (дуга) дерева

23-24 урок, 9 класс

Учитель: Брух Т.В.

Дата: ____________

Тема урока: «Ориентированные и неориентированные графы. Дерево, корень, вершина, лист, ребро (дуга) дерева»

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

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

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

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

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

Ход урока:

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

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

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

Теперь мы с вами перейдем к изучению нового материала. Открывайте тетради, записывайте тему урока: «Ориентированные и неориентированные графы. Дерево, корень, вершина, лист, ребро (дуга) дерева».

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.  Закрепление материала

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

Граф.

Верно, а назовите вид этих графов?

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

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

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

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

4. Практическая работа

1 .     Задание:

2 .     Задание:

3.     Задание:

4 .     Задание:

5 . Задание:

5.  Итог урока.

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