Основные понятия и виды графов - Граф - это сложная нелинейная многосвязная динамическая структура, отображающая свойства и связи сложного объекта.
- В математической теории и информатике граф — это совокупность непустого множества вершин и множества пар вершин (связей между вершинами).
- Объекты представляются как вершины, или узлы графа, а связи — как дуги, или рёбра.
- Впервые понятие «граф» ввел в 1936 г. венгерский математик Денни Кёниг. Но первая работа по теории графов принадлежала Леонарду Эйлеру и была написана еще в 1736 г.
Виды графов - Когда из любой вершины доступна любая другая вершина, то такой граф называется неориентированным связным графом (рис. 1).
- Если же граф связный, но условие доступа выполняется в одном направлении, тогда такой граф называется ориентированным или орграфом (рис. 2).
Виды графов - Взвешенный граф (weighted graph) – это граф, ребрами (дугам) которого назначены веса.
- Вес ребра (i,j) обозначают как wij
Способы представления графов - Вот некоторые важные обозначения, используемые в теории графов:
- •G=(V, E), здесь G – граф, V – его вершины, а E – ребра;
- • |V| – порядок (число вершин);
- •|E| – размер графа (число рёбер).
- Если граф имеет ребро, у которого начало и конец совпадают, то это ребро называется петлей
Do'stlaringiz bilan baham: |
