Матрица смежности. Матрица инциденций. Определение Кратчайших расстояний между вершинами графа

G=<Г,х>, |x|=n, x={

Пример:

Для вершины её полустепенью захода называется число , заходящих в неё дуг, а число полустепенью исхода исходящих дуг.

– называется степенью вершины.

Замечание: для неориентированных графов матрица смежностей является симметричными, а элементы определиться следующим образом:

1 – существует ребро.

0 – в остальных случаях.

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

Матрица инциденций:

G=<Г,х>, |x|=n, |Г|=N, x={

Пусть граф не имеет петель.

Замечание: для неориентированного графа инциденты определяются следующим образом:

Алгоритм Флойда-Оршалла