Графовое представление связей между объектами

Множество самых разнообразных задач естественно формулируется в терминах точек и связей между ними, т. е. в терминах графов. Поэтому эффективные алгоритмы решения задач теории графов имеют большое практическое применение.

Связи могут быть «направленными», как, например, в генеалогическом дереве или в сети дорог с односторонним движением. В соответствии с этим в теории графов выделяют два основных типа графов: ориентированные и неориентированные.

Наиболее известный и популярный способ представления графов состоит в геометрическом изображении точек (вершин) и линий (ребер) на бумаге. При численном решении задач на вычислительных машинах граф должен быть представлен дискретным способом. Существует довольно много способов такого рода представления графов. Однако простота использования представления графа, как и эффективность алгоритма, в основе которого он лежит, в полной мере зависит от конкретного выбора этого представления. Одно из направлений теории графов связано с их матричным представлением. Существуют различные виды матриц, ассоциированные с графами. Эти алгебраические формы используются для решения многих задач теории графов.

Матрицей смежности ориентированного помеченного графа с n вершинами называется матрица A=[a_ij], i, j=1,2…n, в которой:

a_ij= m, если существует m ребер (x_i, x_j),.

0, если вершины x_{i ,} x_j не связаны ребром (x_i, x_j).

Матрица смежности однозначно определяет структуру графа.

Граф называется взвешенным, если с каждым его ребром сопоставлено число. Простой взвешенный граф может быть представлен своей матрицей весов W=[w_ij], где w_ij — вес ребра, соединяющего вершины i, j =1,2.n. Веса несуществующих ребер полагают равными. Матрица весов является простым обобщением матрицы смежности.

При описании графа списком его ребер каждое ребро представляется парой его вершин. Это представление можно реализовать двумя массивами r=(r₁, r₂,…, r_n) и t=(t₁, t₂,…, t_n), где n — количество вершин в графе. Ребро L_{i, j} графа выходит из вершины ri и входит в вершину tj. Здесь L — характеристика ребра, например вес ребра.

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