Главная | Информатика и информационно-коммуникационные технологии | Планирование уроков и материалы к урокам | 9 классы | Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, углубленный уровень) | §17. Графы
Уроки 27 - 28
§17. Графы
Содержание урока
Что такое граф?
Что такое граф?
Ключевые слова:
• граф • вершина • ребро • матрица смежности • степень вершины • связный граф • взвешенный граф • весовая матрица • ориентированный граф • оптимальный путь • количество путей
Давайте подумаем, как можно наглядно представить такую информацию:
От пос. Васюки три дороги идут в Солнцево, Грибное и Ягодное. Между Солнцевом и Грибным и между Грибным и Ягодным также есть дороги. Кроме того, есть дорога, которая идет из Грибного в лес и возвращается обратно в Грибное.
Нарисуйте в тетради схему дорог по этому описанию.
Можно, например, нарисовать такую схему (рис. 3.17, а).
Рис. 3.17
В информатике для исследования таких схем используют графы.
Граф — это набор вершин (узлов) и связей между ними — рёбер.
Граф, соответствующий нашей схеме дорог, показан на рис. 3.17, б, для краткости населённые пункты обозначены латинскими буквами.
Следующая страница 
Матрица смежности графа
Cкачать материалы урока
