Графы

Графы в математике — это способ наглядно описывать связи между объектами. Такой объект называют «вершиной», а связь между двумя объектами — «ребром».

Если говорить проще: граф — это схема, где точки соединены линиями. Точки показывают элементы, а линии — отношения между ними.

Графы помогают изучать, как устроены сети: дороги между городами, электрические цепи, маршруты в интернете, связи между людьми.

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

1. Граф

Граф — это математическая модель, состоящая из вершин и ребер, которые соединяют эти вершины. Записывается как пара (V, E), где:

V — множество вершин,

E — множество ребер (пар вершин).

2. Вершины

Точки, обозначающие объекты.

Примеры: города, люди, компьютеры, страницы сайта.

3. Ребра

Линии, соединяющие вершины.

Бывают:

неориентированные — двусторонние;

ориентированные (дуги) — со стрелкой, показывают направление.

4. Петля

Ребро, которое соединяет вершину саму с собой.

5. Кратные ребра

Несколько ребер между одной и той же парой вершин. Используется в мультиграфах.

6. Инцидентность

Вершина и ребро инцидентны, если ребро выходит из этой вершины или входит в нее.

7. Соседние вершины

Две вершины называются соседними, если они соединены ребром.

8. Смежные ребра

Ребра, которые имеют общую вершину.

9. Порядок графа

Количество вершин в графе. Обозначается |V|.

10. Размер графа

Количество ребер в графе. Обозначается |E|.

• Читайте также: Что такое теория графов. 

Начните учиться бесплатно:
6 онлайн-курсов — в одном месте

IT, нейросети, творчество — всё, чтобы

ребенок развивался и вдохновлялся

• онлайн
• детям 6-16 лет

Начать учиться

Виды графов в математике

1. Неориентированный граф

Граф, в котором ребра не имеют направления. Связь между вершинами двусторонняя: можно двигаться в любую сторону.

2. Ориентированный граф (орграф)

Граф, в котором каждое ребро — это стрелка. Есть направление: из A можно попасть в B, но обратно — не обязательно.

3. Простой граф

Граф без петель и без кратных ребер. Петля — ребро из вершины в нее же. Кратные ребра — несколько ребер между одной парой вершин. В простом графе такого нет.

4. Мультиграф

Граф, в котором допускаются кратные ребра. То есть между двумя вершинами может быть несколько соединений.

5. Псевдограф

Мультиграф, в котором разрешены и кратные ребра, и петли. Это самый «общий» тип графов.

6. Связный граф

Граф, где между любыми двумя вершинами существует путь. То есть все соединено в одну «сеть».

7. Несвязный граф

Граф, который распадается на несколько независимых частей. Каждая часть называется компонентой связности.

8. Дерево

Это связный граф без циклов. Цикл — путь, который возвращается в ту же вершину. Дерево — это структура без замкнутых кругов, напоминающая иерархию.

9. Лес

Граф, состоящий из нескольких деревьев. Если дерево одно — это дерево. Если их несколько и они не соединены — это лес.

10. Полный граф

Граф, где каждая вершина соединена с каждой другой. Никаких пропусков: максимальное количество ребер