double arrow

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


Графом называется алгебраическая система 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={a1,…,an}. Матрицей смежности AG=(Aij) графа G называется матрица порядка n, определенная следующим образом: . Если Aij=1, то вершина aj называется последователем вершины ai, а aiпредшественником aj. Вершины ai и aj называются смежными, если Aij=1 или Aji=1. Если G -мультиграф, то в матрице смежности элемент Aij равен числу дуг, исходящих из вершины ai и заходящих в вершину aj.

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

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

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

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

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

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

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

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


Сейчас читают про: