Неориентированный граф Задачи на кратчайшее расстояние
Графы I. два варианта значения слова “граф”: 1) удобная форма описания структур типа дорожной сети или сети передачи данных; 2) математический объект G := (V, E), где V — это непустое множество вершин, а E — множество ребер (пар вершин). Для описания графа часто используют квадратную таблицу, которая описывает все возможные связи между узлами (без учета дублирования). Если, например, на пересечении строки A и столбца B записано число 1, это означает, что есть ребро, соединяющее вершины A и B; число 0 в этой ячейке означает, что такого ребра нет. Такую таблицу называют матрицей смежности. А2 и А13 на графы Единица на главной диагонали (выделенной зеленым цветом) показывает, что в графе есть петля —ребро, которое начинается и заканчивается в одной и той же вершине. Неориентированный граф — ребра не имеют направления и каждое из них учтено в матрице смежности дважды. “Длину” связей между вершинами называют “весом”. Весовая матрица