teoriya_grafov_lekcii_i_praktika_arslanov_kgasu

Пусть, например, Г(P,U) имеет вид, изображённый на рисунке.

Рядом изображена матрица инцидентности этого орграфа

p2	u2	p3 p5		1		0	1	1	0
						1	0	0	0
u1	u3	u5		1
			А		0	1	1	0	0
p1 u4		p4
				0		0	0	1	1
					0	0	0	0
									1

В отличие от работы [2], где в обозначениях дуг используются обозначения векторов ui , мы пишем просто ui.

Существуют и другие аналитические способы задания графа,

например, через матрицу смежности. Этот способ мы рассмотрим в конце лекции.

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

Эквивалентные или изоморфные графы. 2 графа считаются эквивалентными или изоморфными, если, во-первых, у них одинаковые числа вершин и рёбер (дуг), а во-вторых, соответствующие, т.е. имеющие одинаковые номера рёбра (дуги) соединяют соответствующие вершины.

Способ доказательства изоморфизма двух графов с помощью

матрицы инцидентности. Чтобы показать, что 2 графа изоморфны,

используя матрицы инцидентности, надо, если матрицы не совпадают,

перенумеровать вершины и рёбра одного графа, чтобы соответствующая матрица инцидентности стала совпадать с матрицей другого графа. То есть если после перестановки рёбер и столбцов 1-й матрицы она совпадает с другой, то соответствующие графы будут изоморфны.

Принцип изоморфизма. Для того, чтобы показать, что 2 графа изоморфны, изоморфизм из одного в другой должен быть найден. Для

11

5354.ru

того, чтобы показать, что 2 графа неизоморфны, должны быть найдены такие свойства графа, которыми обладает один граф, но не обладает другой [1].

Матрица смежности. Матрицей смежности вершин графа Г с N

вершинами называется матрица A равная A=(aij)NxN , в которой элемент aij

равен числу дуг (рёбер), идущих из pi в pj (соединяющих pi и pj).

При установлении изоморфизма двух графов по матрицам смежности путём изменения нумерации вершин одного графа надо учитывать, что при этом надо менять не только строки, но и одновременно соответствующие столбцы. Поэтому, по-видимому, непосредственно по матрицам смежности установить изоморфизм графов невозможно.

Задача 1. Построить матрицы смежности для неориентированного и ориентированного графов

p2	u2	p3
	u3
u1		u4
	p1

	p4	p2	u2	p3	p4
			u3
	u5	u1		u4	u5
			p1
	p5				p5

Ответ:

	0		1	1	1	0			0		1	0	1	0
			0	1	0						0	1	0
	1					0			0					0
A		1	1	0	0	0		A		1	0	0	0	0
			0	0	0						0	0	0
	1					1			0					1
		0	0	0	1	0				0	0	0	0	0

Задача 2. Для матрицы инцидентности n m (n вершин, m рёбер)

сколько существует неизоморфных графов? Для неориентированных графов и орграфов? Учитывать, что элементы матрицы 0, 1 и 0, 1, –1

соответственно.

12

5354.ru

Практическое занятие 1. Матрица инцидентности. Изоморфизм

графов

■ УПРАЖНЕНИЯ

Аудиторные задания

1.Построить матрицу инцидентности для неориентированного графа.

Ответ:

p2	u2	p3	u3
	u4		p4

u1

p1u6 u5 p5

	1		0	0	1	1	1
			1	0	0	0
	1						0
A		0	1	1	1	0	0
			0	0	0	0
	0						0
		0	0	0	0	1	1

2. Построить матрицу инцидентности для ориентированного графа.

						Ответ:
u2		u3		1		0	0	1	1	1
p2 u4 p3		p4				1	0	0	0
				1						0
u1	u5		A		0	1	1	1	0	0
p1
		p5		0		0	0	0	0	0
u6
					0	0	0	0	1	1

3. Восстановить геометрическое представление графа по матрице

инцидентности для:

а) неориентированного графа									Ответ:
u1 u2 u3 u4 u5 u6									p3		u3
1 1 0			0	0	1		p
							1	p2			u4
0 0 0			0	0	0 p2			u1	u2p4		u5 p5
0	1	0	0	0	0	p
							3				u6
0	0	1	1	1	0	p4			p1
0	0	1	1	1	0	p
							5

13

5354.ru

б) ориентированного графа										Ответ:
u1		u2		u3	u4	u5 u6				p3	u3
							1 p1		p2
1		1 0			0	0					u4
									u1u2	p4	u5 p5
0 0			0		0	0	0 p2
	0	1		0	0	0	0	p			u6
								3	p1
0		0		1	1	1	0 p4
	0	0		1	1	1	0
								p5

4.Попробовать для двух неориентированных графов,

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

								Ответ:
p3	p4			q3	q4			p4	p2
p2			q2				p6
p1		p5	q1			q5	p1		p7
p7	p6		q7		q6		p3	p5
Решение. Проверим сначала, что число рёбер совпадает. Причём
совпадение должно быть не только по сумме, но и по количеству рёбер у
каждой пары вершин сравниваемых графов. То, что число рёбер совпадает,
– очевидно.

Число рёбер 1-го графа=12 i 12 4 4 4 4 4 4 4 14.

Число рёбер 2-го графа=12 i 12 4 4 4 4 4 4 4 14.

Методом подбора находим новую нумерацию вершин 2-го графа,

соответствующую вершинам 1-го графа. В качестве p1 можем взять любую из точек qi. Пусть p1 = q1. В качестве p2 пробуем взять q2. Так как в первом графе p1 и p2 соединены с p7, а на втором с q5, то q5 = p7. Рассуждая подобным образом, приходим к противоречию. Поэтому в качестве p2

нельзя брать q2. В конце концов находим, что в качестве p2 можно взять q4.

14

5354.ru

В этом случае соответствие остальных вершин pi и qj находится, что показано на рисунке. Кстати, возможен и другой вариант, когда в качестве p2 берётся q5. Учитывая, что в качестве p1 можно было взять 7 вариантов точек, получаем 2x7=14 вариантов перенумерации вершин 2-го графа,

показывающих изоморфизм двух графов.

5.Показать изоморфизм обоих графов задачи 4 с помощью матриц инцидентности. Для этого записать матрицы инцидентности для обоих графов задачи 4 и найти порядок перестановки столбцов

		1			.
(1,2,3,...) (...) и строк	2				.	, которые переводят одну матрицу
		3			.

в другую. После этого расставить новую нумерацию вершин и рёбер 2-го графа, соответствующую вершинам и рёбрам 1-го графа. В действительности осуществить это сложно, поскольку мы не знаем алгоритма. Этот алгоритм, в принципе, можно создать. Например, путём перебора, но тогда надо этот алгоритм осуществлять на компьютере, поскольку алгоритм перебора очень трудоёмкий, да и на компьютере при большом количестве вершин и рёбер, возможно, может потребоваться много времени.

Предлагаю, всё же сделать вручную, но для графов-дополнений,

которые в данной задаче являются более простыми. Для графа Г(P,U) дополнение графа Гдоп.(P,Uдоп.) имеет те же вершины, что и граф Г(P,U), а ребро между pi и pj тогда и только тогда, когда в графе Г(P,U) ребро между pi и pj отсутствует. После нахождения соответствия вершин для графов-дополнений, если таковое соответствие существует, такое же соответствие следует использовать для исходных графов. Если у них рёбра не множественные, то это соответствие будет искомым. Если у них

15

5354.ru

есть множественные рёбра, то надо будет проверить, что их количество совпадает у соответствующих вершин.

Решение. Изобразим на первом графе рёбра и получим матрицу

инцидентности

u1 u2 u3 u4 u5 u6 u7 u8 u9 u10 u11 u12 u13 u14

p2	u7	p3	u9	p4
	u3	u6 u8			u11
u4
p1	u5		u10		p5
u1	u2		u12		u13

p7 u14 p6

1		1	1	1	0	0	0	0	0	0	0	0	0	0		p
		0	0	1	1	1	1	0	0	0	0	0	0			1
0														0 p2
	0	0	1	0	0	0	1	1	1	0	0	0	0	0	p
																3
A 0		0	0	0	0	1	0	0	1	1	1	0	0	0 p4
	0	0	0	0	0	0	0	1	0	0	1	1	1	0	p
		1	0	0	0	0	0	0	0	1	0	0	1			5
0														1 p
	1	0	0	0	1	0	0	0	0	0	0	1	0	1		6
															p7

Изобразим соответствующий граф-дополнение и получим матрицу инцидентности для него

								v1 v2 v3 v4 v5 v6 v7
		p3	p4				1 0 0				0	0	0	1 p1
	p2 v6										0	1	1
			v4				0 0 0							0 p2
			v2
p1	v1			p5		доп.		0	0	1	1	0	0	0	p3
	v3		v7		A		1 1 0				0	0	0	0 p4
			v5					0	0	0	0	0	1	1
	p7														p5
			p6				0		0	0	1	1	0	0 p
								0	1	1	0	0	0	0	6
															p7

Изобразим на втором графе рёбра и получим матрицу инцидентности

q2	v7	q3		v10	q4
	v6v8		v9
v4 vv35					v11 v12
q1					q5
v1 v2					v13
	q7	v14		q6

v1 v2 v3 v4 v5 v6 v7 v8 v9 v10 v11 v12 v13 v14

1 1 1 1 0 0							0	0	0	0	0	0	0	0 q
							1	0	0	0	0	0	0		1
0 0 0 1 1 1														0 q2
	0	0	0	0	0	0	1	1	1	1	0	0	0	0	q
															3
B 0 0 1 0 0 0							0	0	0	1	1	1	0	0 q4
	0	1	0	0	0	1	0	0	0	0	0	1	1	0
															q5
0		0	0	0	1	0	0	0	1	0	0	0	1	1 q6
	1	0	0	0	0	0	0	1	0	0	1	0	0	1
															q7

Изобразим соответствующий граф-дополнение и получим матрицу

инцидентности для него

16

5354.ru

q2	w5	q3 w2	q4
q1 w1			w6
			q5

	w4	w7	w3
			q6
	q7

w1 w2			w3 w4 w5 w6 w7
1		0	0	0	0	0	1	q
			0	1	1	0		1
0 0							0 q2
	1	1	0	0	0	0	0	q
								3
Bдоп. 0		0	0	0	1	1	0	q4
	0	1	1	0	0	0	0	q
								5
0 0			0	0	0	1	1 q6
	0 0		1	1	0	0	0
								q7

Найдём порядок перестановки строк,

который переводит эту матрицу Bдоп

в матрицу B1доп , совпадающую с Aдоп.

Получили следующее соответствие вершин: p1 q1, p2 q4, p3 q7, p4 q3, p5 q6, p6 q2 и p7 q5.

w1 w2			w3 w4 w5 w6 w7
1		0	0	0	0	0	1	q
			0	0	1	1		1
0 0							0 q4
	0	0	1	1	0	0	0	q
		1	0	0	0	0	0	7
Bдоп. 1								q
1								3
	0	0	0	0	0	1	1	q
								6
0 0			0	1	1	0	0 q2
	0 1		1	0	0	0	0
								q5

6. Показать, что два неориентированных графа неизоморфны

p1	p6	p2	q1	q6	q2
p5			q5

p8 p7

p4 p3

q8 q7

q4

q3

Решение 1. Проверим сначала, что степени вершин совпадают. Да, это так. Если бы степени вершин у двух графов отличались, то это сразу показало бы отсутствие изоморфизма.

Можно заметить, что на первом графе имеется последовательность из восьми смежных рёбер, возвращающаяся к начальной вершине. В этом цикле все вершины проходятся по одному разу. Например, его можно задать перечислением вершин p1, p2, p3, p4, p8, p7, p6, p5, p1. При этом некоторые рёбра остались неиспользованными. Можно эту же

17

5354.ru

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

Предположим, что это так. Во втором графе вершины q2 и q4 имеют каждая только по два смежных ребра, следовательно, эти четыре ребра должны быть в последовательности рёбер соответствующего цикла, но тогда для перехода к вершинам q5, q6, q7, q8 необходимо использовать ребро (q1, q5) или (q3, q7). Следовательно, в соответствующей последовательности вершин и рёбер второго графа будет вершина, из которой исходят три ребра, чего быть не может. В цикле из каждой вершины может исходить только 2 ребра. Следовательно, наше предположение не верно, т.е. два графа не изоморфны.

Решение 2. Это решение аналогично предыдущему, но сделано с использованием понятия “гамильтонов цикл”. Это цикл, проходящий через все вершины по одному разу. У первого графа имеется гамильтонов цикл p1, p2, p3, p4, p8, p7, p6, p5, p1. Чтобы был изоморфизм, второй граф тоже должен иметь гамильтонов цикл. Так как вершины q2, q4, q6, q8 –

двухвалентны, то все рёбра, исходящие из них, должны присутствовать в этом гамильтоновом цикле. Для вершин q2, q4 это четыре ребра q1-q2-q3-q4- q1. Для вершин q6, q8 это четыре ребра q5-q6-q7-q8-q5. Так как в гамильтоновом цикле в каждой вершине должны быть использованы только 2 ребра, следовательно, рёбра q1-q5 и q3-q7 не могут быть использованы. Но тогда от вершин q1, q2, q3, q4 невозможно перейти к вершинам q5, q6, q7, q8. Следовательно, предположение, что 2-й граф имеет гамильтонов цикл, неверно. Графы не изоморфны, так как обладают

разными свойствами.

18

5354.ru

Домашние задания

1.Построить матрицу инцидентности для неориентированного графа. Ответ:

	p2	u2	u3	u7
			p3	p4
		u4

u1

p1u6 u5 p5

1	0	0	1	1	1	0
	1	0	0	0	0
1						0

A 0 1 1 1 0 0 1

0 0 0 0 0 0 0

0 0 0 0 1 1 0

2. Построить матрицу инцидентности для ориентированного графа.

							Ответ:
		u3	u7	1		0	0	1	1	1	0
	u2
				1		1	0	0	0	0	0
	p2 u4	p3	p4
						1	1	1	0	0
	u1			A 0							1
		u5			0	0	0	0	0	0	0
	p1
	u6	p5			0	0	0	0	1	1	0

3. Восстановить геометрическое представление по матрицам

инцидентности неориентированного и ориентированного графов.

	u1 u2 u3 u4								u1 u2 u3			u4
1 0 1				1		p		1 0 1				1	p
		0	1			1				0	1			1
0				0 p2				0				0 p2
	1	0	0	1	p		3		1	0	0	1 p		3
0		0	0	0 p4				0		0	0	0 p4
	0	1	0	0					0	1	0
					p5							0 p5

Ответ:

	p1	u3	p2	p1	u3	p2
	u4	u1		u4	u1
		p5	u2		p5	u2
	p3	p4		p3	p4

19

5354.ru

4.Попробовать для двух неориентированных графов,

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

	p2		q1
	p3
	p4
	p5	p6	q6
			q5
	p1

Ответ:

q2

p1

p2

q3 p4

p5

q4 p6 p3

Решение. Проверим сначала, что число рёбер совпадает. Причём совпадение должно быть не только по сумме, но и по количеству рёбер у каждой пары вершин сравниваемых графов. То, что число рёбер совпадает,

– очевидно.

Число рёбер 1-го графа = 12 i 12 5 3 4 4 3 5 12 .

Число рёбер 2-го графа = 12 i 12 5 3 4 4 5 3 12 .

Методом подбора находим новую нумерацию вершин 2-го графа,

соответствующую вершинам 1-го графа.

5.Показать изоморфизм обоих графов задачи 4 с помощью матриц инцидентности. Для этого записать матрицы инцидентности для обоих графов задачи 4 и найти порядок перестановки столбцов и строк, которые переводят одну матрицу в другую. После этого расставить новую нумерацию вершин и рёбер 2-го графа,

соответствующую вершинам и рёбрам 1-го графа.

6.Показать, что два неориентированных графа неизоморфны, путём поиска соответствующей перенумерации вершин или другим способом.

20

5354.ru