• Главная

Площадь многоугольника

Площадь многоугольника

Постановка задачи

Пусть требуется определить площадь полигона A1, A2, A3, A4, A5 с координатами вершин x1,y1; x2,y2; x3,y3; x4,y4; x5,y5. Площадь полигона S можно представить трапециями, у которых абсциссы являются основаниями, а разности ординат соседних точек высотами

Алгоритм Дейкстры

01

Алгоритм Дейкстры (Dijkstra’s algorithm) — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса. Алгоритм широко применяется в программировании и технологиях.

Эйлеров и Гамильтонов графы

Гамильтонов граф

Эйлеров граф

Эйлеров путьв графе — это путь, проходящий по всем рёбрам графа и притом только по одному разу.

Эйлеров цикл — это эйлеров путь, являющийся циклом.

Эйлеров граф — граф, содержащий эйлеров цикл.

MST. Алгоритмы Прима и Крускала

Это минимальное остовное дерево не уникально

Итак, имеется n городов, которые нужно объединить в единую телефонную сеть. Для этого достаточно проложить (n-1) телефонных линий между городами. Как соединить города так, чтобы суммарная стоимость соединений (телефонного кабеля) была минимальна?