Головна

Діаметр, радіус і центр графа

  1. A) Регулювання процентних ставок по позиках Центрального банку, що надаються комерційним банкам;
  2. N Концентрація напружень в зоні контакту і середній тиск порядку 15 ... 20 МПа обумовлюють взаємну дифузію металів, що сприяє підвищенню надійності з'єднання.
  3. V. Початок об'єднання російських земель. Піднесення Москви. Національно- визвольних (антіординскіе) рух. Освіта централізованої Московської держави. (XIV-XV ст.)
  4. VI. Зміцнення централізованої держави. Станово-представницька монархія
  5. А) соціоцентрична (К. Маркс)
  6. А. Держави Центральної та Південно-Східної Європи.
  7. Автоматизована система централізованої підготовки та оформлення перевізних документів (Етра)

Заданий одиничний зв'язний неорієнтований граф G.

Мінімальна довжина простий ланцюга з початком V 'і кінцем V "називається відстанню між цими вершинами d (V', V").

Діаметр графа - максимальне з відстаней між будь-якими парами вершин:

D (G) = max d (V ', V ").

(V ", V ') c G

Якщо взяти за точку відліку відстаней одну з вершин графа (наприклад V), то максимальне з відстаней від V до будь-якої з вершин графа G називається максимальним віддаленням:

r (V) = max d (V (i)).

V (i) c G

Вершина V називається центром графа, якщо максимальне видалення від неї приймає мінімальне значення. Максимальне видалення від центру називається радіусом графа.

r (G) = min r (V)

V c G

Будь-яка проста ланцюг від центру V до максимально віддаленої від нього вершини називається радіальної ланцюгом.

Розглянемо на прикладі визначення цих параметрів графа (аналіз графа на мінімум).

Заданий одиничний неорієнтовані граф G:

V = {a, b, c, d, e, f}; E = {ab, ac, bc, cd, ce, de, ef}. Визначити діаметр, центр (центри) і радіус цього графа.

Для визначення цих параметрів зобразимо граф G і складемо матрицю відстаней: (на перетині шпальти і рядки (вершини графа) матриці вказується відстань між цими вершинами; така матриця (виділена на малюнку) симетрична щодо головної діагоналі).

--- T - T - T - T - T - T - T --- T ---

| |a |b |c |d |e |f |r (V) |центр|

+ --- Г == + == + == + == + == + == --- + --- +

| A | 0| 1| 1| 2| 2| 3| 3 | |

+ --- + - + - + - + - + - + - + --- + --- +

| B | 1| 0| 1| 2| 2| 3| 3 | |

+ --- + - + - + - + - + - + - + --- + --- +

| C | 1| 1| 0| 1| 1| 2| 2 | v |

+ --- + - + - + - + - + - + - + --- + --- +

| D | 2| 2| 1| 0| 1| 2| 2 | v |

+ --- + - + - + - + - + - + - + --- + --- +

| E | 2| 2| 1| 1| 0| 1| 2 | v |

+ --- + - + - + - + - + - + - + --- + --- +

| F | 3| 3| 2| 2| 1| 0| 3 | |

L --- L == | == | == | == | == | == --- + ---

У стовпці з заголовком r (V) вкажемо віддалення від відповідних вершин (максимальне значення відстані кожного рядка). Максимальна з вилучень і буде діаметром графа (т. Е. Максимально можливим відстанню між вершинами в досліджуваному графі): D (G) = 3.

Вершини, для яких видалення r (V) приймає мінімальне значення (позначені v), є центрами графа G, а значення видалення - радіусом графа: r (G) = 2.

Якщо ребра графа навантажені (кожному ребру поставлено у відповідність визначене числове значення), то процедура дослідження аналогічна описаній вище, але при заповненні матриці потрібно визначати відстань між вершинами не по числу ребер, а за сумарною їх довжині.

 



Операції з частинами графа | Параметри протяжності (діаметр, радіус і центр) графа

ДОНБАСЬКИЙ ІНСТИТУТ ТЕХНІКИ І МЕНЕДЖМЕНТУ | МІЖНАРОДНОГО НАУКОВО-ТЕХНІЧНОГО УНІВЕРСИТЕТУ | Безлічі. Способи завдання множин | Операції над множинами | Число елементів безлічі | Властивості бінарних відносин | Операції з бінарними відносинами | Складові висловлювання; таблиці істинності | Логічні закони | Відносини між висловлюваннями |

© um.co.ua - учбові матеріали та реферати