Построить матрицы смежности и весовые матрицы

Содержание

1 Содержание
2 Определение [ править | править код ]
- 2.1 Матрица смежности двудольного графа [ править | править код ]
3 Примеры [ править | править код ]
4 Свойства [ править | править код ]
- 4.1 Степени матрицы [ править | править код ]
5 Структура данных [ править | править код ]
6 Ответ или решение 1

На этой странице вы можете задать матрицу смежности и построить по ней граф

© Граф Online — создание и визуализация графа в два клика или по матрице смежности и поиск кратчайшего пути, поиск компоненты связности, поиск Эйлеровго цикла. Поделиться: Twitter, Facebook, В Контакте. 2015 — 2019

Матрица смежности — один из способов представления графа в виде матрицы.

Содержание

Определение [ править | править код ]

Матрица смежности графа G с конечным числом вершин n (пронумерованных числами от 1 до n) — это квадратная матрица A размера n, в которой значение элемента a_ij равно числу рёбер из i-й вершины графа в j-ю вершину.

Иногда, особенно в случае неориентированного графа, петля (ребро из i-й вершины в саму себя) считается за два ребра, то есть значение диагонального элемента a_ii в этом случае равно удвоенному числу петель вокруг i-й вершины.

Матрица смежности простого графа (не содержащего петель и кратных рёбер) является бинарной матрицей и содержит нули на главной диагонали.

Матрица смежности двудольного графа [ править | править код ]

Матрица смежности A двудольного графа, доли которого имеют r и s вершин, может быть записана в следующем виде

A = ( 0 r , r B B T 0 s , s ) , <displaystyle A=<egin0_&B\B^&0_end>,>

где B является r × s <displaystyle r imes s> матрицей, а 0 r , r <displaystyle 0_> и 0 s , s <displaystyle 0_> представляют r × r <displaystyle r imes r> и s × s <displaystyle s imes s> нулевые матрицы. В этом случае меньшая матрица B единственным образом представляет граф, а оставшиеся части матрицы A можно отбросить. B иногда называется матрицей бисмежности.

Формально, пусть G = ( U , V , E ) <displaystyle G=(U,V,E)> будет двудольным графом с долями U = < u 1 , … , u r ><displaystyle U=<1>,dots ,u_>> и V = < v 1 , … , v s ><displaystyle V=<1>,dots ,v_>> . Бисопряжённая матрица является r × s <displaystyle r imes s> 0–1 матрицей B, в которой b i , j = 1 <displaystyle b_=1> тогда и только тогда, когда ( u i , v j ) ∈ E <displaystyle (u_,v_)in E> .

Если G является двудольным мультиграфом или взвешенным графом, то элементами b i , j <displaystyle b_> будет число рёбер между вершинами или веса рёбер ( u i , v j ) <displaystyle (u_,v_)> соответственно.

Примеры [ править | править код ]

Ниже приведён пример неориентированного графа и соответствующей ему матрицы смежности A. Этот граф содержит петлю вокруг вершины 1, при этом в зависимости от конкретных приложений элемент a 11 <displaystyle a_<11>>может считаться равным либо одному (как показано ниже), либо двум.

Граф	Матрица смежности
	( 1 1 0 0 1 0 1 0 1 0 1 0 0 1 0 1 0 0 0 0 1 0 1 1 1 1 0 1 0 0 0 0 0 1 0 0 ) <displaystyle <egin1&1&0&0&1&0\1&0&1&0&1&0\0&1&0&1&0&0\0&0&1&0&1&1\1&1&0&1&0&0\0&0&0&1&0&0end>>

a_ij — число рёбер, связывающих вершины v i <displaystyle v_>и v j <displaystyle v_>, причём в некоторых приложениях каждая петля (ребро < v i , v i ><displaystyle ,v_>>при некотором i <displaystyle i>) учитывается дважды.

Матрица смежности пустого графа, не содержащего ни одного ребра, состоит из одних нулей.

Свойства [ править | править код ]

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

Два графа G₁ и G₂ с матрицами смежности A₁ и A₂ являются изоморфными тогда и только тогда, когда существует перестановочная матрица P, такая что

Из этого следует, что матрицы A₁ и A₂ подобны, а значит имеют равные наборы собственных значений, определители и характеристические многочлены. Однако обратное утверждение не всегда верно — два графа с подобными матрицами смежности могут быть неизоморфны (это бывает в случае, если матрица P не является перестановочной, например, матрицы ( 0 1 0 0 ) <displaystyle <egin0&1\0&0end>> и ( 0 2 0 0 ) <displaystyle <egin0&2\0&0end>> являются подобными, но соответствующие им графы не изоморфны).

Степени матрицы [ править | править код ]

Если A — матрица смежности графа G, то матрица A m обладает следующим свойством: элемент в i-й строке, j-м столбце равен числу путей из i-й вершины в j-ю, состоящих из ровно m ребер.

Структура данных [ править | править код ]

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

Использование матрицы смежности предпочтительно только в случае неразреженных графов, с большим числом рёбер, так как она требует хранения по одному биту данных для каждого элемента. Если граф разрежён, то большая часть памяти напрасно будет тратиться на хранение нулей, зато в случае неразреженных графов матрица смежности достаточно компактно представляет граф в памяти, используя примерно n 2 <displaystyle n^<2>> бит памяти, что может быть на порядок лучше списков смежности.

В алгоритмах, работающих со взвешенными графами (например, в алгоритме Флойда-Уоршелла), элементы матрицы смежности вместо чисел 0 и 1, указывающих на присутствие или отсутствие ребра, часто содержат веса самих рёбер. При этом на место отсутствующих рёбер ставят некоторое специальное граничное значение (англ. sentinel ), зависящее от решаемой задачи, обычно 0 или ∞ <displaystyle infty > .