1. Понятие графа: вершины и рёбра

В жизни мы постоянно сталкиваемся с системами, в которых есть объекты и связи между ними. Например:

  • станции метро и линии между ними;

  • люди и дружба между ними;

  • города и дороги.

Математическая модель, которая описывает такие системы, называется графом.

Определение:
Граф — это набор вершин (точек) и соединяющих их рёбер (линий).

  • Вершины — объекты (города, люди, станции).

  • Рёбра — связи (дороги, дружба, линии метро).

Граф — это геометрическая модель, то есть рисунок, но важны не точные координаты, а то, какие вершины соединены.

Пример 1. Простейший граф:
Вершины: А, В, С.
Рёбра: А–В, В–С.
Рисуем: три точки, А соединена с В, В соединена с С, А с С не соединена.