Главная страница Случайная страница
КАТЕГОРИИ:
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Задание 2. Матрица длин дуг v0 v1 v2 v3 v4 v5 v0 ∞ ∞ v1 ∞
|
|
Матрица длин дуг
| v0 | v1 | v2 | v3 | v4 | v5 | |
| v0 | ∞ | ∞ | ||||
| v1 | ∞ | ∞ | ||||
| v2 | ∞ | ∞ | ∞ | |||
| v3 | ∞ | ∞ | ∞ | ∞ | ||
| v4 | ∞ | ∞ | ||||
| v5 | ∞ | ∞ | ∞ | ∞ | ∞ |
1.
2. Неориентированный граф G=(V, X). V={v0, v1, v2, v3, v4, v5}, X={x0, x1, x2, x3, x4, x5, x6, x7, x8}. x0={v0, v1}, x1={v0, v5}, x2={v1, v2}, x3={v1, v4}, x4={v1, v3}, x5={v0, v2}, x6={v0, v4}, x7={v2, v4}, x8={v3, v4}.
3. v5 – висячая вершина.
4. d(v0)=4, d(v1)=4, d(v2)=3, d(v3)=2, d(v4)=4, d(v5)=1.
5.
Матрица смежности
| v0 | v1 | v2 | v3 | v4 | v5 | |
| v0 | ||||||
| v1 | ||||||
| v2 | ||||||
| v3 | ||||||
| v4 | ||||||
| v5 |
Матрица инцидентности
| x0 | x1 | x2 | x3 | х4 | х5 | х6 | х7 | x8 | |
| v0 | |||||||||
| v1 | |||||||||
| v2 | |||||||||
| v3 | |||||||||
| v4 | |||||||||
| v5 |
Матрица связности:
| v0 | v1 | v2 | v3 | v4 | v5 | |
| v0 | ||||||
| v1 | ||||||
| v2 | ||||||
| v3 | ||||||
| v4 | ||||||
| v5 |
Матрица достижимости:
| v0 | v1 | v2 | v3 | v4 | v5 | |
| v0 | ||||||
| v1 | ||||||
| v2 | ||||||
| v3 | ||||||
| v4 | ||||||
| v5 |
6. Простой цикл: v0х0v1х2v2х5v0
Цикл: v4x6v0x5v2x7v4x3v1x4v3х8v4
Простая цепь: v2х5v0х1v5
Цепь: v0х0v1х2v2х7v4х3v1х4v3
7. Числовые характеристики
a) Максимальное удаление – r(v) = maxwd(v, w)
r(v0)=2, r(v1)=2, r(v2)=2, r(v3)=3, r(v4)=2, r(v5)=3
б) Диаметр графа d(G)=maxv, wd(v, w)
d(G)=3
в) Радиус графа G- r(G)=minv r(v)
R(G)=2
г) Центры графа-v| R(G)=r(v)
центры графа - вершины v0, v1, v2, v4.
8.
Рассчитаем остовное дерево графа:
Рассчитаем минимальное остовное дерево графа:
9. Обход графа в глубину: v0®v1®v2®v4®v3®v5.
Обход графа в ширину. 1 ярус: v0; 2 ярус: v1, v2, v4, v5; 3 ярус: v3.
10. Число циклов в базисе (цикломатическое число графа)
.
Чтобы найти базис циклов графа, к остовному дереву будем добавлять по одному ребра, которые в остовное дерево не вошли. При этом на каждом шаге будем получать один простой цикл.
Добавим ребро x3:
Получим цикл 1: v4x6v0x0v1x3v4.
Добавим ребро x4:
Получим цикл 2: v3x8v4x6v0x0v1x4v3.
Добавим ребро x5:
Получим цикл 3: v0x0v1x2v2x5v0.
Добавим ребро x7:
Получим цикл 4: v4x6v0x0v1x2v2x7v4
Полученные циклы и образуют базис циклов графа.