🧛25. Динамические структуры данных. Графы. Виды графов (по типу рёбер, по числу рёбер, по ...

достижимости узлов). Способы задания графов.

Динамическая структура данных

• Это структуры данных, память под которые выделяется и освобождается по мере необходимости. Примером таких структур можно считать деревья, списки, очередь, стек.

Граф

Это абстрактный тип данных, который предназначен для реализации понятий неориентированного и ориентированного графа из области теории графов в математике.

Структура данных графа состоит из конечного набора вершин вместе с набором неупорядоченных пар этих вершин для неориентированного графа или набором упорядоченных пар для ориентированного графа.

Область применения графов

• Геолокация

• Планирование процессов

• Компьютерные сети

• Структура программы

• Химические соединения

• Связи между людьми

Основные понятия теории графов

Ориентированный граф - G(V, E) - пара из V(конечного множества) и Е(подмножества декартового произведения множества V*V).

Неориентированный граф - ребра есть неупорядоченные пары. Если для любой пары вершин существует путь, граф неориентированный.

Взвешенный граф - граф, в котором каждому ребру приписан вес. С(U, V)

Взвешенный граф

Вершины графа - элементы множества V.

Ребра графа - элементы множества Е.

Петля - ребро из вершины Vi в само себя.

Вершины Vi и Vj смежны, если между ними имеется связь (Vi, Vj).

Путем из V0 в Vn называется последовательность рёбер таких, что Е1 = (V0, V1), E2 = (V1, V2)... En = (Vn-1, Vn)

Простым путем называется путь, в котором все вершины попарно различны.

Длина пути - количество рёбер в пути.

Цикл - путь, в котором V0=Vn.

Связанная компонента вершины V - множество вершин неориентированного графа до которых существует путь из V.

Ориентированный граф с петлями у вершин 2 и 6

Виды графов

По числу рёбер

1. Нулевой

2. Неполный

3. Полный

По достижимости узлов

• связный(сильно связанный или слабо связанный)

• несвязный