При решении некоторых практических задач (например, нахождении кратчайшего пути между пунктами) имеют значение не только связи между вершинами, но и числа, соответствующие этим связям. Этими числами могут быть, например, расстояния между городами или стоимость проезда. В теории графов числовое значение, поставленное в соответствие каждому ребру графа, называют его весом, а такой граф − взвешенным графом.
Задача
Из каждого из пунктов A, B, C и D имеется путь в остальные пункты, расстояния между которыми известны: AB=7, AC=5, AD=4, BC=6, BD=1, CD=8. Необходимо, начиная от одного из этих пунктов и побывав в каждом из пунктов только один раз, вернуться в исходный пункт. Какой маршрут надо выбрать, чтобы путь оказался кратчайшим?
П а м я т к а
• Взвешенный графВо взвешенном графе вместо матрицы смежности используют весовую матрицу. В ячейках весовой матрицы указывается вес ребер, и если между двумя вершинами нет ребра, соответствующая ячейка остается пустой. На рисунке показана схема, на которой указаны длины путей, соответствующий ей граф и весовая матрица.