Билет 30.

Графы. Основные понятия. Аналитические способы задания графов.

Граф – совокупность множеств двух видов – множество вершин графа и множество ребёр, характеризующих связь между этими вершинами. Ориентированный граф – дуги имеют направление. Если вершина v я вляется концом или началом дуги x, то говорят что они инцидентны. Степень вершины – число ребер инцидентных ей. Вершина имеющая степень 0 – изолированная, 1 – висячая. Полустепень исхода вершины – число дуг орграфа исходящих из вершины (полустепень захода аналогично). контур – замкнутый путь. Транспонированный граф – получен из исходного путём изменения направления всех дуг на противоположное. Симметричный граф – для любых i,j для (xi,xj) существует xj,xi симметрично относительно диагонали. Путь – в ор. графе последовательность перемещения от вершины к вершине с учетом направления дуг.

Способы задания(анал.):

1) задать множество вершин и рёбер

2) ор. граф в виде G(X,F), где Х={x1,x2..xn}, F={Fx1,Fx2..Fxn}, где Fxi={xj}-множество вершин в которые ведут дуги исходящие из хi

оба этих способа можно использовать для задания неориент. графа. Для этого каждое звено заменяется на две дуги противоположных направлений.

3) матричный способ. матрица смежности строки и столбцы- вершины графа. элементы r_ij= для неориентированного графа матрица смежности симметрична относ. диагонали. Матрица инцидентности. а_ij=

Дата добавления: 2015-07-26