3.1. Справочный материал

Кратко напомним определения, известные из курса дискретной математики.

Определения. Граф – пара G(V,E), где V = {V₁,V₂, …,V_n} – множество вершин графа G, E – множество ребёр (дуг) графа: Е={ (V_1i, V_2i) }.

Рёбра можно задавать разными способами, например матрицей инцидентности или списком ребёр.

Неориентированный граф – граф, удовлетворяющий условию, что если (a, b) E, то и (b, a) E, т.е. порядок расположения концов дуг графа не существенен.

Матрица инцидентности такого графа симметрична.

Взвешенный граф – граф, каждой дуге которого приписан её вес.

Цикл в графе – маршрут, заданный последовательностью вершин, каждая вершина посещается по одному разу, и начальная вершина совпадает с конечной.

Граф без цикла – куст.

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

Связный куст – дерево.

Компонента связности – совокупность вершин, для каждой из которых существует пусть в любую другую вершину этой совокупности.