Матрица смежности, расстояний, структурная.

22 Шектестер, арақашықтық, құрылымдық матрицасы

Отображать графы можно в виде чертежа, перечня его вершин и дуг, находящихся в некотором соотношении, и специальными таблицами – матрицами.

x₂=Гx₁

x₁=Гx₂

x₃=Гx₂

…

Рисунок 8.1

Матрица смежности

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

Диагональные элементы матрицы не определены, в клетках ставятся «-».

	x1	x2	x3	x4
x1	-
x2		-
x3			-
x4				-

Преимущества представления графа в виде матрицы смежности – простота и формализованность, но запись в ЭВМ требует большого объема памяти.

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

Если в качестве веса ребра рассматривается - пропускная способность,

Матрица инциденций

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

Для неориентированных графов матрица строится по правилу

Для орграфов матрица строится по правилу

Структурная матрица

Структурная матрица представляет собой квадратную таблицу, строки и столбцы которой соответствуют вершинам графа. Элементы матрицы отражают связи между узлами:

Пусть дан граф

		a	b
			c	d
				m

Дата добавления: 2015-07-17