4. Элементы теории графов

4.1. Основные понятия теории графов Вопросы для повторения

1. Что называется графом?

2. Что такое матрица инцидентности?

3. Что такое список ребер графа?

4. Что такое матрица смежности?

4.1.  Дан граф (рис. 4.1). Задать его матрицей инцидентности, списком ребер и матрицей смежности.

Рис. 4.1. Граф к задаче 4.1

Решение

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

	a	b	c	d	e	f	k	m	n
1	1	1	1	0	1	0	0	0	0
2	1	1	0	1	0	1	0	0	0
3	0	0	0	0	1	0	1	0	0
4	0	0	0	0	0	1	0	1	0
5	0	0	0	0	0	0	0	1	1
6	0	0	0	0	0	0	1	0	1

Список ребер

Ребро	Вершины
a	1 2
b	1 2
c	1 1
d	2 2
e	1 3
f	2 4
k	3 6
m	4 5
n	5 6

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

	1	2	3	4	5	6
1	1	2	1	0	0	0
2	2	1	0	1	0	0
3	1	0	0	0	0	1
4	0	1	0	0	1	0
5	0	0	0	0	1	1
6	0	0	1	0	1	0

4.2.  Дан направленный граф (рис. 4.2). Задать его матрицей инцидентности, списком ребер и матрицей смежности.

Рис. 4.2. Граф к задаче 4.2

Решение

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

	a	b	c	d	e	f	k	m	n
1	-1	-1	2	0	-1	0	0	0	0
2	1	1	0	1	0	1	0	0	0
3	0	0	0	0	1	0	-1	0	0
4	0	0	0	0	0	-1	0	-1	0
5	0	0	0	0	0	0	0	1	-1
6	0	0	0	0	0	0	1	0	1

Список ребер

Ребро	Вершины
a	1 2
b	1 2
c	1 1
d	2 2
e	1 3
f	2 4
k	3 6
m	4 5
n	5 6

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

	1	2	3	4	5	6
1	1	2	1	0	0	0
2	0	1	0	0	0	0
3	0	0	0	0	0	1
4	0	1	0	0	1	0
5	0	0	0	0	0	1
6	0	0	0	0	0	0

4.3.  Задана матрица инцидентности

	a	b	c	d	e	f	k	m	n
1	-1	1	0	0	0	0	0	0	1
2	1	-1	0	-1	0	1	0	0	0
3	0	0	1	0	2	0	-1	0	0
4	0	0	0	0	0	-1	0	-1	0
5	0	0	-1	1	0	0	0	1	-1
6	0	0	0	0	0	0	1	0	0

Построить граф и записать матрицу смежности.

4.4.  Задана матрица смежности

	1	2	3	4	5	6
1	1	0	1	0	0	0
2	0	1	0	3	0	0
3	0	0	0	0	0	1
4	0	1	0	0	1	0
5	0	0	0	0	0	1
6	0	0	0	0	0	1

Построить граф и записать матрицу инцидентности.