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