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

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

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

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

 

Таблиця 15.1

	x1	x2	x3
x1
x2
x3

 

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