Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, базовый уровень)



Уроки 13 - 14
§17. Графы




Содержание урока

Что такое граф?

Матрица смежности графа

Связный граф

Взвешенный граф

Оптимальный путь в графе

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

Количество путей

Выводы

Вопросы и задания


Что такое граф?


Ключевые слова:

• граф	
• вершина	
• ребро	
• матрица смежности	
• степень вершины	
• связный граф
• взвешенный граф
• весовая матрица
• ориентированный граф
• оптимальный путь
• количество путей

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

От пос. Васюки три дороги идут в Солнцево, Грибное и Ягодное. Между Солнцевом и Грибным и между Грибным и Ягодным также есть дороги. Кроме того, есть дорога, которая идет из Грибного в лес и возвращается обратно в Грибное.
Нарисуйте в тетради схему дорог по этому описанию.

Можно, например, нарисовать такую схему (рис. 3.17, а).

Рис. 3.17

Рис. 3.17

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

Граф — это набор вершин (узлов) и связей между ними — рёбер.

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

Следующая страница Матрица смежности графа



Cкачать материалы урока








Наверх