Слайд 2 Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор
![Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/978735/slide-1.jpg)
рёбер( соединений между парами вершин).
Слайд 3ВИДЫ ГРАФОВ
Графы, в которых все рёбра являются звеньями (порядок двух концов ребра
![ВИДЫ ГРАФОВ Графы, в которых все рёбра являются звеньями (порядок двух концов](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/978735/slide-2.jpg)
графа не существенен), называются неориентированными.
Графы, в которых все рёбра являются дугами (порядок двух концов ребра графа существенен), называются ориентированными графами или орграфами
Слайд 4АЛГОРИТМ ДЕЙКСТРЫ
Алгоритм голландского ученого Эдсгера Дейкстры находит все кратчайшие пути из одной
![АЛГОРИТМ ДЕЙКСТРЫ Алгоритм голландского ученого Эдсгера Дейкстры находит все кратчайшие пути из](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/978735/slide-3.jpg)
изначально заданной вершины графа до всех остальных.
Минусом данного метода является невозможность обработки графов, в которых имеются ребра с отрицательным весом.
Слайд 6АЛГОРИТМ КРАСКАЛА
Алгоритм Краскала — эффективный алгоритм построения минимального остовного дерева взвешенного связного
![АЛГОРИТМ КРАСКАЛА Алгоритм Краскала — эффективный алгоритм построения минимального остовного дерева взвешенного](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/978735/slide-5.jpg)
неориентированного графа. Также алгоритм используется для нахождения некоторых приближений для задачи Штейнера. Алгоритм впервые описан Джозефом Крускалом в 1956 году.
Слайд 8АЛГОРИТМ ПРИМА
Алгоритм Прима — это алгоритм поиска минимального остовного дерева в связном
![АЛГОРИТМ ПРИМА Алгоритм Прима — это алгоритм поиска минимального остовного дерева в](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/978735/slide-7.jpg)
графе. С помощью алгоритма Прима можно выделить только те ребра графа, с помощью которых можно соединить каждую из вершин этого графа и при этом суммарная стоимость этих ребер будет минимальна.