Привет всем

Кибенематика - математическая кибернетика с намеком на отсыл к едреней фене__(АБС)__

понедельник, 2 ноября 2020 г.

10 Графовых алгоритмов


2020-10-31 19:00

      Графы превратились в невероятно сильное средство моделирования и получения данных из соцсетей, веб-страниц и ссылок, а также определения местоположения и маршрутов в GPS. Любой набор объектов, которые связаны друг с другом, можно сейчас представить с помощью графа.

      В статье опишем 10 основных графовых алгоритмов, которые становятся очень полезными для анализа, а также области их применения.

Начнём с того, что приведём определение графа.

Что такое граф?

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

      Ниже приведён ряд базовых понятий, относящихся к графам. 

Порядок: число вершин в графе.

Размер: число рёбер в графе.

Степень вершины: число рёбер, инцидентных вершине.

Изолированная вершина: вершина, которая не связана ни с одной другой вершиной графа.

Петля: ребро, вершины которого совпадают.

Ориентированный граф: граф, в котором все рёбра имеют направление, определяющее начальную и конечную вершину.

Неориентированный граф: граф с рёбрами, которые не имеют направления.

Взвешенный граф: рёбра такого графа имеют определённый вес.

Невзвешенный граф: рёбра такого графа не имеют никаких весов.

Полностью читать здесь.


Комментариев нет:

Отправить комментарий