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

РАЗДЕЛ III

ОПТИМИЗАЦИОННЫЕ ЗАДАЧИ НА ГРАФАХ

Существует ряд задач, которые удобно представлять в виде графических структур. Например, графически можно представить процесс принятия решения, транспортировку продукции, передачу информации и т.д. Анализ графических структур позволяет находить оптимальные решения этих задач. Для построения и исследования графических структур разработана система методов, изучаемая в теории графов.

Глава 5. Элементы теории графов

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

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

Последовательность неповторяющихся ребер, ведущая от некоторой вершины к другой, образует путь.

Конечный путь в орграфе, у которого начальная вершина совпадает с конечной, называется контуром, а в неориентированном графе – циклом.

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

В экономике чаще всего используются два вида графов: дерево и сеть.

Дерево представляет собой связный граф без циклов, имеющий исходную вершину (корень) и крайние вершины; пути от исходной вершины к крайним вершинам называются ветвями.

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

Известно несколько типов матриц, позволяющих задавать граф в удобном виде.

1. Матрица смежности графа (содержит n вершин) – матрица , каждый  элемент которой определяется по формуле:

2. Матрица инцидентности ориентированного графа с n вершинами и m ребрами называется матрица , каждый  элемент которой определяется по формуле: