Алгоритмы на графах

1

Алгоритмы на графах

Граф – абстрактная структура данных, которая представляет собой множество вершин и множество ребер, соединяющих пары различных вершин (одно ребро может соединять только одну пару вершин).

Количество ребер не превышает значения V*(V-1)/2, где V – количество вершин.

Например,

ребро

вершина

2

Алгоритмы на графах

Области применения

1.Путешествия (определение пути следования из одной точки в

другую с наименьшими временными затратами).

2.Обработка гипертекста (поиск информации в глобальной сети).

3.Расписание (распределение занятий с учетом не больше трех пар в

день и учебной нагрузки преподавателя).

4.Связь (отслеживание трафика).

5.Создание микросхем (распределение элементов таким образом,

чтобы не создать короткое замыкание или шины не должны пересекаться).

6.Создание сети (обеспечение надежности функционирования при

изменении конфигурации).

7.Программное обеспечение (оценка использование ресурсов

системы).

3

Алгоритмы на графах

Терминология

Граф, который содержит параллельные ребра, называется

мультиграфом.

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

4