br/>В
Заради скорочення мові термін граф вживається замість термінів мультіграф , орграф та ін, але подібні випадки або спеціально обумовлюються, або ясні з контексту.
Часто кожній дузі графа ставлять у відповідність одне або кілька чисел. Такий граф називається зваженим (або мережею). Приклад зваженого графа представлений на рис. 3.7. br/>В
Розглянемо деякі поняття теорії графів.
Нехай v 1 , v 2 , ..., v n , v n +1 - довільна послідовність вершин орграфа.
Ланцюгом називається будь-яка послідовність дуг e 1 , e 2 , ..., e n , така, що кінцевими вершинами дуги e i є вершини v i і v i +1 , тобто e i = (v i , v i +1 ) або e i = (v i +1 , v i ) для i = 1,2, ..., n.
Ланцюг, для якої e i = (v i , v i +1 ) при всіх i = 1,2, ..., n, називається шляхом.
Циклом називається ланцюг, у якої початкова та кінцева вершини збігаються.
Контуром називається шлях, у якого початкова та кінцева вершини збігаються.
Ланцюг, шлях, цикл або контур називаються простими, якщо вони не містять всередині себе циклів.
У графа, зображеного на рис. 3.8. p align="justify"> дуги (v 2 , v 1 ), (v 2 , v 2 ), (v 3 ...
