Презентация, доклад по информатике на тему Введение в теорию графов (11 класс)

РЕШЕНИЕ ЗАДАЧИ:
Определение маршрута прокладки кабеля минимальной длины, но при этом подходящего к каждому дому.

Для решения таких задач используют теорию графов.

1

4

5

3

6

2

400

700

100

200

100

800

200

300

200

600

R-Ребра (дороги, линии связи между компьютерами, стороны геометрических фигур)

Смежные вершины
(соединенные ребром)

Ребро и любая из его двух
вершин называются инцидентными

Степень вершины –
количество инцидентных ей рёбер

V-5 R-8

Замкнутая цепь – начальная и конечная вершины совпадают

Связной граф – любая вершина достижима из любой другой вершины

Изолированные вершины - не имеют инцидентных ребер (например v6)