• Гідрологія і Гідрометрія
• Господарське право
• Економіка будівництва
• Економіка природокористування
• Економічна теорія
• Земельне право
• Історія України
• Кримінально виконавче право
• Медична радіологія
• Методи аналізу
• Міжнародне приватне право
• Міжнародний маркетинг
• Основи екології
• Предмет Політологія
• Соціальне страхування
• Технічні засоби організації дорожнього руху
• Товарознавство продовольчих товарів

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

Нехай G - зв’язний, неорієнтований граф. Оскільки дві довільні вершини „a” і „b” – зв’язані, то в загальному випадку існує декілька простих ланцюгів S_i(a, b), які з’єднують „a” і „b”. В цій множині ланцюгів має існувати ланцюг, який має найменшу довжину. Ця найменша довжина і називається відстанню між „a” і „b”: d(a, b). Будемо вважати за визначенням, що d(a, a) = 0.

Введена відстань задовольняє всі аксіоми метрики:

1) d(a, b) ³ 0;

2) d(a, b) = 0 тоді і тільки тоді, коли a = b;

3) d(a, b) = d(b, a);

4) d(a, b) + d(b, c) ³ d(a, c).

Для скінченного графу можна ввести поняття діаметру.

Визначення. Діаметр графу G(V):

.

Виберемо деяку вершину c Î V і позначимо через

,

віддаль від с до найбільш віддаленої вершини графу.

Назвемо c₀ центром графу G, якщо

.

Зауважимо, що центр графу не єдиний.

Рис.6

Наприклад, для графу, зображеного на рис. 6, радіус r₀ = 1; центр графу c₀ = v₂ або c₀ = v₄.

Читайте також:

1. I. Доповнення до параграфу про точкову оцінку параметрів розподілу
2. IV. Система зв’язків всередині центральної нервової системи
3. А джерелами фінансування державні капітальні вкладення поділяються на централізовані та децентралізовані.
4. А. Центрогенна ДН
5. Алгоритм проходження графу вглиб
6. Аналіз витрат за центрами відповідальності.
7. Аналіз відхилень – основний інструмент оцінки діяльності центрів відповідальності
8. Аналіз відхилень — основний інструмент оцінки діяльності центрів відповідальності
9. Аналіз результатів практичної діяльності Київського освітньо-методичного центру соціальної роботи
10. АНАТОМІЯ І ФІЗІОЛОГІЯ ЦЕНТРАЛЬНОЇ ТА ПЕРИФЕРИЧНОЇ НЕРВОВОЇ СИСТЕМИ, ЇЇ ВІКОВІ ОСОБЛИВОСТІ
11. Антиукраїнська політика російського царизму. Посилення централізаторсько-шовіністичних тенденцій
12. Арматура та вимірювальні прилади, якими обладнуються відцентрові насоси

Переглядів: 1039