ustify">. Характеристика графа
неорієнтовані граф G = (V, X)
V = {V0, V1, V2, V3, V4, V5, V6}
X = {X0, X1, X2, X3, X4, X5, X6, X7, X8, X9, X10, X11}
X0 = {V0, V1}, X1 = {V0, V2}, X2 = {V0, V3}, X3 = {V2, V4}, X4 = {V1, V4}, X5 = {V1, V2}, X6 = {V2, V3}, X7 = {V4, V5}, X8 = {V3, V5}, X9 = {V2, V5}, X10 = {V4, V6}, X11 = {V5 , V6}
. Спеціальні вершини і ребра
Ні
. Ступені вершин
? (V0) = 3 ? (V1) = 3 ? (V2) = 5 ? (V3) = 3 ? (V4) = 4 ? (V5) = 4 ? (V6) = 2
. Матриці суміжності, інцидентності, досяжності, зв'язності
суміжності Інцидентне досяжними зв'язності . Цикл, ланцюг, простий цикл, проста ланцюг
Простий цикл: V0 X2 V3 X6 V2 X1 V0 Цикл: V0 X0 V1 X4 V4 X10 V6 X11 V5 X9 V2 X1 V0
Простий ланцюг: V4 X7 V5 X8 V3 Ланцюг: V4 X10 V6 X11 V5 X9 V2
. Числові характеристики графа
a) Максимальне видалення - r (V) = max w d (V, W)
r (V0) = 6, r (V1) = 6, r (V2) = 6, r (V3) = 6, r (V4) = 6, r (V5) = 6, r (V6) = 6
б) Діаметр графа d (G) = maxv, wd (v, w) (G) = 6
в) Радіус графа G - r (G) = minv r (V)
R (G) = 6
г) Центри графа-V | R (G) = r (V)
центри графа - вершини V0, V1, V2, V3, V4, V5, V6
. Остовне дерево і мінімальне оставное дерево
Розрахуємо кістяк графа:
В В
Розрахуємо мінімальне кістяк графа:
В
. Обхід графа в глибину і в ширину
Обхід графа в глибину: V0 В® V1 В® V2
