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

B

A

Рис. 3.1. Иллюстрация к задаче о Кенигсбергских мостах.

Такую задачу не предоставляется возможным решить классическими методами математики. Для решения такой задачи был предложен качественно новый аппарат – аппарат теории графов.

Графом называется пара следующего вида:

, (3.1)

где - график ;

- множество вершин.

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

Рис. 3.2. Граф

Граф, представленный на рис. 3. 2, состоит из множества вершин и множество дуг

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

1. перечислением:

2. множеством образов:

,

где - образ вершины - множество вершин, в которые исходят дуги из данной вершины.

Матрица инцидентности - это матрица вершин и инцидентных им дуг.

Дуга инцидентна вершине, если эта дуга исходит или заходит в данную вершину.

Вершина инцидентна дуге, если в эту вершину заходит или исходит данная дуга.

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

· , если из i-той вершины исходит j-тая дуга:

· , если в i-той вершину заходит j-тая дуга;

· , если i-тая вершина не инцидента j-той дуге;

· , если из i-той вершины исходит j-тая дуга и в нее же заходит, т.е. в i-той вершине j-тая дуга образует петлю.

Для графа, представленного на рис. 3.2 матрица инцидентности имеет вид:

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

На практике в матрице инцидентности иногда нули не проставляются для наглядности.

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

Свойство матрицы инцидентности – сумма элементов по столбцам равна 0 или 2.

Дата добавления: 2013-12-12