![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Якщо ребрам (дугам) графу приписані деякі ваги (мітки), то такі графи називаються зваженими (відзначеними).
Вага дуги чи ребра може означати довжину, пропускну здатність, напругу чи струм і т. д. Ваги можна приписувати не тільки ребрам (дугам), але і вершинам. Зважені графи знаходять застосування, наприклад у мережному плануванні. Зважені орієнтовані графи називаються графами потоків-сигналів. Зважені орграфи знаходять застосування, наприклад, у теорії ланцюгів. Зважений граф, що не містить кратних ребер, може бути представлений матрицею суміжності. При цьому кожен її ненульовий елемент дорівнює вазі відповідного ребра (дуги).
Приклад. Матриця суміжності і графічне представлення зваженого орграфу
Таблиця 15.1
x1 | x2 | x3 | |
x1 | |||
x2 | |||
x3 |
Рис. 15.9. Зважений орграф
Контрольні запитання
1. Що є маршрутом, довжиною маршруту?
2. Що є ланцюгом, простим ланцюгом, циклом, простим циклом?
3. Яка різниця між ейлеревим та гамільтоновим циклами?
4. Що є підграфом, яка різниця між початковою та кінцевою вершинами?
5. Що є потужно зв’язаним, зв'язаним, слабо зв’язаним графами?
6. Що є роздільним графом, точкою зчленування, мостом?
7. Що є деревом, які відношення між кількостями вершин і ребер є у дереві?
8. Яка різниця між ексцентриситетом, радіусом і центром?
9. Яка різниця між графом та зваженим графом?
Дата публикования: 2014-11-18; Прочитано: 2975 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!