Теория графов. Представление логистических систем в виде графов

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

Рисунок 2.1 – Пример графа.

При такой ориентации (рис. 2.1), точка f является истоком, точка a является приемником, при этом точка a является истоком для точки b.

Задача о кенигсбергских мостах: 

Рисунок 2.2 – Схема кенигсбергских мостов.

Задача обхода всех семи мостов города Кенигсберга (ныне Калининграда) таким образом, что по каждому мосту проходят в точности один раз. Задача была поставлена и решена Эйлером в 1736 г. в виде общей проблемы теории графов: при каких условиях связный граф содержит цикл, проходящий через каждое его ребро?

Рисунок 2.3 – Граф, описывающий логистическую систему кенигсбергских мостов.

Вершины a и b являются связанными, если между ними существует ребро, при этом вершины a и b инцидентными ребру, а сами вершины a и b являются смежными. Ребра графа являются смежными, если они инцидентны одной вершине.

Кроме того граф допускает наличие петель (рис. 2.4).

Рисунок 2.4 – Пример графа с наличием петель.

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

Рисунок 2.5 – Пример простых графов.

Мультиграф – если между вершинами несколько ребер.

Псевдограф – если между вершинами ен только несколько ребер, но и существуют петли (рис. 2.6).

Рисунок 2.6 – Пример псевдографа.

Степенью вершин называется количество ребер инцидентных вершине:

deg(v)

Любая Логистическая система может быть представлена в виде графа.

Пример. Есть 3 дома (1,2,3, рис. 2.7), и эти дома надо снабдить одновременно водой (В), газом (Г) и электроэнергией (Э).

Рисунок 2.7 – Задача о снабжении 3х домов.

Литература:

1. Шевченко В.В. Конспект лекций по курсу "Логистика". Донецк, ДонНТУ - 2009 г.
2. Ткачук А.Н. Конспект лекций по курсу "Логистика". Донецк, ДонНТУ - 2008 г.