Определение и основные понятия графа (10 класс)

1.

УРОК 13 • ИНФОРМАТИКА 10 КЛАСС
Определение и основные понятия
графа
Полный разбор теории по учебнику: вершины, рёбра, дуги, петли,
кратные рёбра, матрица смежности и список рёбер.
Алматыкітап
Представление в ПК

2.

ИСТОРИЯ И ОПРЕДЕЛЕНИЕ
Что такое Граф?
Определение из учебника
Граф — это схема из множества точек (вершин),
соединенных отрезками или дугами (ребрами).
• Первые сведения появились в XVIII веке (задача о Кёнигсбергских
мостах).
• Термин «граф» впервые ввёл венгерский математик Д. Кениг.
Обозначение: G = (V, E), где |V| — порядок графа (число вершин), |E| —
размер графа (число рёбер).
Схема графа G = (V, E)

3.

ПО РИСУНКАМ 1 И 2 ИЗ УЧЕБНИКА
Неориентированный и Ориентированный граф
Неориентированный граф
Направления ребер не указываются. Связь двусторонняя.
Ориентированный граф (Дуги)
Ребра имеют направление от начальной вершины к конечной
(называются дугами).

4.

ЭЛЕМЕНТЫ ГРАФА
Вес ребра, Петли и Кратные рёбра
Вес ребра
Числовое значение ребра (расстояние, стоимость).
Петля
Ребро, соединяющее вершину саму с собой.
Кратные рёбра
Различные рёбра, соединяющие одну пару вершин.

5.

ПРЕДСТАВЛЕНИЕ В ПРОГРАММИРОВАНИИ (СПОСОБ 1)
Матрица смежности
Матрица A[5,5] (к Рисунку 1 из учебника)
Матрица смежности — это квадратная таблица размерностью N × N (где N —
количество вершин графа).
Элемент A[i, j] равен весу ребра (или 1, если есть связь) между вершинами i и j.
Если связи нет — ставится 0.
• На главной диагонали A[i, i] = 0 (если нет петель).
• Для неориентированного графа матрица симметрична относительно диагонали.
i, j
1
2
3
4
5
1
0
10
7
0
0
2
10
0
0
8
9
3
7
0
0
3
0
4
0
8
3
0
6
0
9
0
6
0
5
Пример: A[2,5] = 9 (вес ребра между вершиной 2 и 5 равен 9)

6.

ПРЕДСТАВЛЕНИЕ В ПРОГРАММИРОВАНИИ (СПОСОБ 2)
Представление через Список рёбер
input.txt (Список рёбер)
Список рёбер — таблица или файл, где в каждой строке записываются
две смежные вершины и вес ребра между ними.
Структура файла:
• Первая строка: N M (N — вершин, M — рёбер)
• Следующие M строк: X Y Z (откуда, куда, вес)
N=5 вершин, M=6 рёбер
5 6 // N вершин, M рёбер 1 2 10 // Ребро (1-2), вес 10 1 3 7 // Ребро (1-3),
вес 7 2 4 8 // Ребро (2-4), вес 8 2 5 9 // Ребро (2-5), вес 9 3 4 3 // Ребро
(3-4), вес 3 4 5 6 // Ребро (4-5), вес 6

7.

ЗАКРЕПЛЕНИЕ МАТЕРИАЛА
Практические задания из учебника
ЗАДАНИЕ 1
ЗАДАНИЕ 2
Изображение схемы
Получение матрицы
По предложенной матрице смежности постройте граф:
Заданную схему описать матрицей смежности и списком рёбер:
010011
100101
001010
010010
101101
010010
Ответ: неориентированный граф с N=6 вершин
Составить таблицу 4×4 по стрелкам

8.

ПРИМЕНЕНИЕ В ЖИЗНИ
Где применяются графы?
Схемы дорог
Города — вершины, дороги — вес с расстоянием.
Коммуникации
Программирование
Газопроводы, теплосети и электросети.
Анализ связей между объектами и алгоритмы.

9.

ИТОГИ УРОКА
Главные термины Темы 13
Термин
Суть понятия
Вершины (V) и Рёбра (E)
Точки (объекты) и соединяющие их отрезки.
Ориентированный граф (Дуги)
Рёбра имеют направление от начала к концу.
Петля / Кратные рёбра
Ребро в себя же / Несколько рёбер между 2 вершинами.
Матрица смежности
Квадратная таблица N×N с весами связей.
Список рёбер
Строки вида (X Y Z), содержащие пары вершин и вес.

10.

Тема 13 освоена!
Готовы к решению практических задач из учебника на составление матриц
смежности.
Алматыкітап • 10 класс