Раздел «Графы»
Задан граф списком рёбер:
Рёбра |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
Вершины |
A |
A |
B |
B |
C |
C |
D |
E |
E |
G |
B |
G |
Вершины |
B |
B |
C |
C |
D |
F |
E |
F |
G |
F |
F |
A |
Начертите его графическое изображение на плоскости (диаграмму графа), постройте его матрицы инцидентности и смежности. Определите тремя способами число его рёбер.
Задан граф списком рёбер:
Рёбра |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
Вершины |
E |
A |
D |
B |
C |
C |
D |
E |
E |
G |
B |
G |
Вершины |
E |
B |
D |
C |
D |
F |
E |
F |
G |
F |
F |
A |
Начертите его графическое изображение на плоскости, постройте его матрицы инцидентности и смежности. Определите тремя способами число его рёбер.
Задан граф списком рёбер:
Рёбра |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
Вершины |
E |
A |
D |
B |
C |
E |
D |
E |
E |
D |
B |
G |
Вершины |
E |
B |
D |
C |
D |
D |
E |
F |
G |
D |
F |
A |
Начертите его графическое изображение на плоскости, постройте его матрицы инцидентности и смежности. Определите тремя способами число его рёбер.
Подсчитать количество помеченных орграфов с 6 вершинами, содержащих от 3 до 4 рёбер.
Подсчитать количество помеченных неориентированных графов с 6 вершинами, содержащих от 2 до 4 рёбер.
Граф задан списком рёбер:
1 |
A1–A2 |
9 |
A7–A7 |
2 |
A1–A2 |
10 |
A7–A8 |
3 |
A2–A3 |
11 |
A7–A8 |
4 |
A2–A9 |
12 |
A4–A5 |
5 |
A1–A9 |
13 |
A5–A7 |
6 |
A3–A4 |
14 |
A5–A6 |
7 |
A3–A7 |
15 |
A6–A7 |
8 |
A9–A8 |
|
|
Построить графическое изображение и проверить формулу Эйлера для числа вершин, рёбер и граней графа.
Граф задан матрицей инцидентности:
|
I |
II |
III |
IV |
V |
1 |
1 |
1 |
|
|
|
2 |
|
1 |
|
1 |
|
3 |
1 |
|
1 |
|
|
4 |
|
|
1 |
1 |
|
5 |
|
1 |
|
|
1 |
6 |
1 |
|
|
1 |
|
7 |
1 |
|
|
|
1 |
Постройте его графическое изображение, список рёбер и матрицу смежности.
Подсчитать количество помеченных неориентированных графов с 6 вершинами, содержащих не менее 13 рёбер.
Найти минимальную линию, соединяющую города A, B, C, D, E, F. Попарные расстояния между городами заданы треугольной таблицей:
B
11
C
8
15
D
6
9
11
E
9
12
7
5
F
14
8
10
11
7
A
B
C
D
E
По данной матрице смежности неориентированного псевдографа
1
2
3
4
5
6
1
0
0
0
0
0
0
2
0
0
2
1
0
0
3
0
2
0
0
1
1
4
0
1
0
0
2
0
5
0
0
1
2
0
0
6
0
0
1
0
0
1
нарисовать диаграмму;
восстановить матрицу инцидентности;
составить матрицу связности;
определить степени всех вершин (петлю считать дважды).
По данной матрице смежности ориентированного псевдографа
1
2
3
4
5
6
1
0
0
0
0
0
0
2
0
1
1
0
0
0
3
1
0
0
0
0
1
4
0
0
0
0
0
0
5
0
1
0
2
0
0
6
0
0
1
0
0
0
нарисовать диаграмму;
восстановить матрицу инцидентности;
составить матрицу достижимости;
определить степени всех вершин.
По данной матрице смежности неориентированного псевдографа
1
2
3
4
5
6
1
0
0
0
0
0
0
2
0
0
1
1
3
0
3
0
1
0
1
0
0
4
0
1
1
1
0
1
5
0
3
0
0
0
0
6
0
0
0
1
0
0
нарисовать диаграмму;
восстановить список рёбер;
составить матрицу связности;
определить степени всех вершин (петлю считать дважды).
Разметить графы и установить изоморфизм (номер задания – по номеру студента).
9)
10)
11)
12)
13)
14)
