Теория графов (8 класс)

1. Теория графов

Алексеева Е.В., учитель информатики и ИКТ МОУ «Сланцевская СОШ №3»
8 класс
Теория графов

2. Граф - это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек.

Алексеева Е.В., учитель информатики и ИКТ МОУ «Сланцевская СОШ №3»
Понятие графа
Граф - это множество точек или вершин и
множество линий или ребер,
соединяющих между собой все или часть
этих точек.
вершина
ребро
Граф с шестью вершинами и семью ребрами

3. Виды графов

Алексеева Е.В., учитель информатики и ИКТ МОУ «Сланцевская СОШ №3»
Виды графов
Ориентированный
(рёбрам присвоено
направление)
Неориентированный
(нет направления линий)
Взвешенный
(ребра имеют вес –
расстояние между
вершинами)

4. Способы задания графов

Алексеева Е.В., учитель информатики и ИКТ МОУ «Сланцевская СОШ №3»
Способы задания графов
1. в графическом виде: вершины
отображаются кругами (точками), а связи
соответствующими линиями (возможно,
со стрелками)
2. в матричном виде (таблица)
3. перечисление всех элементов графа, то
есть рёбер (например
(AC;8),(AD;10),(BE;1),(BD;4),(CE;3),(CD;1).