Граф и его элементы

курсовая работа

1.1 Основные понятия

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

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

Например: сеть дорог, соединяющая города 1, 2, 3, 4, 5 можно представить в виде графа следующим образом: города обозначим точками (вершинами), а дороги неориентированными линиями (рисунок 1). Неориентированные линии означают наличие двустороннего движения между соответствующей парой городов. Пересечения линией не считаются вершинами.

Рисунок 1 - Граф сети дорог

Рассмотрим другой пример, ориентированный граф (рисунок 2).

Рисунок 2 - Граф

Таким образом, математически граф можно рассматривать как множество кружков и множество соединяющих их линий. Кружки называются вершинами графа, линии со стрелками - дугами, без стрелок -ребрами.
В зависимости от наличия или отсутствия ориентации у пар элементов из множества V различают графы:

а) ориентированные,

б) неориентированные (реберные),

в) смешанные.

Делись добром ;)