Пусть G = G(V,E) – неориентированный граф с вершинами v0, v1, v2, v3, …, vk множества V и ребрами e1, e2, e3, …, ek множества Е. Определение. Путем (маршрутом) длины k из v0 в vk (или между v0 и vk) называется последовательность v0e1v1e2v2e3v3…vkekvk такая, что eі = {ѵі-1, vі}. Таким образом, путь длины k имеет k ребер. Определение. Если нет рёбер, предшествующих e1, то вершина v0 называется начальной, если нет рёбер, следующих после ek, то вершина vk называется конечной, вершины пути, не являющиеся начальной или конечной, называются внутренними...

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