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

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

## **Динамическая структура данных**&#x20;

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

## Граф

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

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

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

* Геолокация
* Планирование процессов
* Компьютерные сети
* Структура программы
* Химические соединения
* Связи между людьми

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

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

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

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

<figure><img src="https://3644367790-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUZOUsWlbTNqsUYoinAff%2Fuploads%2FOPtTxi6ADn0SWZP9iIJt%2Fimage.png?alt=media&#x26;token=bf5ca9df-545a-4a44-a7cb-bac2572f2121" alt=""><figcaption><p>Взвешенный граф</p></figcaption></figure>

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

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

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

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

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

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

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

**Цикл** - путь, в котором V0=Vn.&#x20;

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

<figure><img src="https://3644367790-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUZOUsWlbTNqsUYoinAff%2Fuploads%2F6OHKDS15GsMujhtwWDHo%2Fimage.png?alt=media&#x26;token=1314430f-e113-42a9-a043-a56ecc2c4674" alt=""><figcaption><p>Ориентированный граф с петлями у вершин 2 и 6</p></figcaption></figure>

## Виды графов

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

1. Нулевой

![](https://3644367790-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUZOUsWlbTNqsUYoinAff%2Fuploads%2FLt1lU00W8lVgUm0SOc3E%2Fimage.png?alt=media\&token=81a9b144-2a8d-448d-8074-3d853e9fd935)

2. Неполный

![](https://3644367790-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUZOUsWlbTNqsUYoinAff%2Fuploads%2FMH7LM2f4qd2E3UPLjmEd%2Fimage.png?alt=media\&token=09cc0ae9-caaa-4b7f-bd96-c115c1f708a3)

3. Полный&#x20;

![](https://3644367790-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUZOUsWlbTNqsUYoinAff%2Fuploads%2F5EGh3HKNsFdrhdbe5nN8%2Fimage.png?alt=media\&token=94f23120-7e94-4a5a-9442-58dc4362fdd9)

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

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

![](https://3644367790-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUZOUsWlbTNqsUYoinAff%2Fuploads%2FrX7weqEvMGE9S1JCSo8Z%2Fimage.png?alt=media\&token=8ba5316f-a8a4-4f2f-8fae-33452c636c25)

* несвязный&#x20;

![](https://3644367790-files.gitbook.io/~/files/v0/b/gitbook-x-prod.appspot.com/o/spaces%2FUZOUsWlbTNqsUYoinAff%2Fuploads%2F4FBNM4DFxC39OhzpTkaZ%2Fimage.png?alt=media\&token=e74deb28-0d94-4fea-9f7a-1452fb933e95)



