1. Что такое граф? Какой граф называют взвешенным?

Граф — это математическая модель, состоящая из вершин и соединяющих их рёбер. Вершины изображают объекты, а рёбра — связи между ними.

Взвешенный граф — граф, рёбрам которого приписаны числа — веса. Они могут обозначать, например, расстояние, стоимость или время.