Студопедия.Орг Главная | Случайная страница | Контакты | Мы поможем в написании вашей работы!  
 

Зважені (відзначені) графи



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

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

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

Таблиця 15.1

  x1 x2 x3
x1      
x2      
x3      

Рис. 15.9. Зважений орграф

Контрольні запитання

1. Що є маршрутом, довжиною маршруту?

2. Що є ланцюгом, простим ланцюгом, циклом, простим циклом?

3. Яка різниця між ейлеревим та гамільтоновим циклами?

4. Що є підграфом, яка різниця між початковою та кінцевою вершинами?

5. Що є потужно зв’язаним, зв'язаним, слабо зв’язаним графами?

6. Що є роздільним графом, точкою зчленування, мостом?

7. Що є деревом, які відношення між кількостями вершин і ребер є у дереві?

8. Яка різниця між ексцентриситетом, радіусом і центром?

9. Яка різниця між графом та зваженим графом?





Дата публикования: 2014-11-18; Прочитано: 2932 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!



studopedia.org - Студопедия.Орг - 2014-2024 год. Студопедия не является автором материалов, которые размещены. Но предоставляет возможность бесплатного использования (0.007 с)...