Виды и способы задания графов. (27)

Графом называется алгебраическая система G=<M,R>, где R – двухместный предикатный символ. Элементы носителя М называются вершинами графа G, а элементы бинарного отношения - дугами. Таким образом, дугами являются пары вершин . При этом дуга (a,b) называется исходящей из вершины a и заходящей в вершину b.

Мультиграфом G называется тройка <M,U,P>, в которой M – множество вершин, U – множество дуг, а - трехместный предикат, называемый инцидентором и представляемый следующим образом: тогда и только тогда, когда дуга u исходит из вершины a и заходит в вершину b.

Граф G=<M,R> называется ориентированным (орграфом), если найдется дуга такая, что .

Граф G называется неориентированным (неорграфом), если отношение R симметрично, т.е. из следует .

Если одновременно пары (a,b) и (b,a) принадлежат R, то информацию об этих дугах можно представить множество [a,b]={(a,b),(b,a)}, называемым ребром, соединяющим вершины a и b.

Понятия морфизмов алгебраических систем для графов представляются следующим образом. Пусть G=<M,R>, G’=<M’,R’> - графы. Тогда отображения φ=M→M’ является изоморфизмом графов, если .

Информация о структуре графа может быть задана матрицей бинарного отношения. Пусть G=<M,R> - граф, в котором множество вершин имеет n элементов M={a₁,…,a_n}. Матрицей смежности A_G=(A_ij) графа G называется матрица порядка n, определенная следующим образом: . Если A_ij=1, то вершина a_j называется последователем вершины a_i, а a_i – предшественником a_j. Вершины a_i и a_j называются смежными, если A_ij=1 или A_ji=1. Если G -мультиграф, то в матрице смежности элемент A_ij равен числу дуг, исходящих из вершины a_i и заходящих в вершину a_j.

Петлей в графе G называется дуга, соединяющая вершину саму с собой.

Теорема: Графы изоморфны тогда и только тогда, когда их матрицы смежности получаются друг из друга одновременными перестановками строк и столбцов.

Матрицей инцидентности B_G=(B_ij) мультиграфа G называется матрица размера m на n (где m – количество дуг в графе), определяемая по правилу: .

Теорема: Мультиграфы G и G’ изоморфны тогда и только тогда, когда их матрицы инцидентности получаются друг из друга некоторыми перестановками строк и столбцов.

Пометкой или распределением меток графа G=<M,R> называется пара функций f:M→S_M (распределение меток вершин), g:R→S_R (распределение меток дуг). Четверка <M,R,d,g> называется взвешенным или помеченным графом.

Информацию о весах дуг во взвешенном графе можно представить в виде матрицы весов W=(w_ij), где w_ij – вес дуги (a_i,a_j), если эта дуга существует и ∞ в противном случае.

Если граф G=<M,R> является разреженным, т.е. |R|<<|M|, то можно задать граф в виде списка дуг: два набора , где (a_mi,a_ni) – i-ая дуга графа G.

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