Практическая работа №3Количество часов, отводимых на выполнение практической работы 2ч

Тема: Решение задач по теме «Графы. Эйлеровы графы»

Цель: отработка навыков работы с графами.

Общие теоретические сведения:

Основные понятия теории графов

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

, (3.1)

где - график ;

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

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

Рис. 3.2. Граф

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

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

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

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

,

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

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

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

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

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

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

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

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

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

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

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

	2	-1	+1	0	0	+1	-1
	0	+1	0	0	0	0	0
	0	0	-1	-1	0	0	0
	0	0	0	+1	-1	0	0
	0	0	0	0	+1	-1	0
	0	0	0	0	0	0	+1

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

	2	-1	+1			+1	-1
		+1
			-1	-1
				+1	-1
					+1	-1
							+1

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