194 читали · 2 года назад
Основные характеристики графа
Определение. Если {а, b} – неориентированное ребро, тогда вершины а и b называются концами или концевыми вершинами ребра {а, b}. Ребро {а, b} называют также инцидентным вершинам а и b. Обратно, говорят, что вершины а и b инцидентны к ребру {а, b}. Пример 1. В неориентированном графе G1 (см. рис. ниже) вершина а инцидентна рёбрам{a, c} и {a, b}, вершина b инцидентна двум рёбрам {a, b} и{b, d}, вершина с инцидентна трём рёбрам {a, c}, {c, d} и {c, е}, вершина d инцидентна трём рёбрам {b, d}, {c, d} и {d, f}, вершина e инцидентна ребру {c, e}, вершина f инцидентна ребру {d, f}...
06:44
1,0×
00:00/06:44
29,5 тыс смотрели · 3 года назад
Формула под названием "Эврика-граф" (Eureka-graph).
Формула под названием "Эврика-граф" (Eureka-graph). Eureka-graph = (V, E, w) V - множество вершин графа; E - множество рёбер графа; w - функция, которая сопоставляет вес каждому ребру графа. Для нахождения кратчайшего пути между двумя вершинами в Eureka-graph используется алгоритм Дейкстры. Суть алгоритма состоит в обходе графа от стартовой вершины до конечной, постепенно наращивая длину найденного пути. Для определения минимального остовного дерева на графе используется алгоритм Крускала. Алгоритм...