Данный раздел курса требует умения устанавливать соответствие между разными типами данных, основными из которых являются таблицы и графы. В задачах этого раздела необходимо уметь преобразовывать таблицы в графы и наоборот. Граф, взвешенный граф. Граф (или сетевая модель данных) представляет собой набор вершин, соединенных ребрами, и обычно описывается в виде таблицы, например, матрицы смежности или весовой матрицы. Взвешенный граф – это граф, в котором каждому ребру присвоен вес, который может обозначать, например, расстояние между городами или стоимость перевозки...

Прежде всего давайте осмыслим — что мы имеем. Мы имеем произвольный ориентированный взвешенный мультиграф с петлями, веса дуг в котором строго больше нуля. Напомним, что мы имеем дело с графом D ≝ ⟨Ω, V, φ(V)⟩, где Ω — множество субъектов (вершины), а V ⊂ (Ω×Ω) — множество обязательств (дуги) и φ: V → Q, причём ∀v∈V ∃ε∈Q: ε = φ(v), а (Q ⊂ ℚ): (q ∈ Q) ∧ (q>0) — множество обязательств (дуги) весовая функция на множестве дуг. Введём ещё два обозначения: входящую степень вершины μ обозначим как in(μ), а внешнюю степень вершины μ как ех(μ)...

Определение 1. Пусть G – неориентированный граф. Пусть Mc – квадратная матрица, строки и столбцы которой обозначены вершинами неориентированного графа G. Элемент i-ой строки и j-гo столбца матрицы Mc, обозначаемый cij, равен единице, если имеется ребро из i-ой вершины в j-ую вершину, и равен нулю в противном случае. Матрица Mc называется матрицей смежности графа G. Заметим, что для сокращения записи обозначения строк и столбцов в матрицах смежности можно опускать, но рекомендуется их оставлять особенно в матрицах больших размерностей...