Лекція №15. Матричне представлення графів

Графічне та аналітичне представлення графа

Матриця суміжності

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

Матриця ваги

Граф можна задати графічним, аналітичним або матричним способом.

Графічне представлення графа

Рис. 15.1 – орієнтований граф

Аналітичне представлення графа.

, де - множина вершин графа, - відображення, яке задає відповідність між вершинами графа.

Матричне представлення графа

Матриця суміжності графа це матриця , в якій для орієнтованого графа. Для графа, зображеного на малюнку 15.1 матриця суміжності має вигляд:

Для орієнтованого графа для співвіднесеного графа

Петля може бути представлена одиницею на відповідному діагональному елементі. Кратні ребра можуть бути представлені числом більшим одиниці.

Матриця інциденції для неорієнтованого графа з вершинами і ребрами це матриця ,

стрічки якої відповідають вершинам, а стовпці ребрам. Елементи матриці будуються за правилом .

Матрицею інцидентності для орієнтованого графа з вершинами і ребрами називається матриця . Елементи матриці будуються за правилом

Матриця інциденцій для графа, зображеного на малюнку 15.1 має вигляд:

для орієнтованого графа для співвіднесеного графа

	+1
	-1	+1		+1
		-1	+1
			-1	-1	-1
					+1

Граф називається зваженим, якщо кожному його ребру поставлено у відповідність число. Зважений граф може бути представлений своєю матрицею ваги , де -вага ребра, яке з’єднує вершини . Таким чином, матриця ваги графа являється узагальненням матриці суміжності.

Граф називається зваженим, якщо кожному його ребру поставлено у відповідність число. Зважений граф може бути представлений своєю матрицею ваги , де -вага ребра, яке з’єднує вершини . Таким чином, матриця ваги графа являється узагальненням матриці суміжності.

Дата добавления: 2014-01-04