Контрольные вопросы
1. Нарисуйте следующие графы:
а) К5; б) К1,4.
2. Изоморфны ли следующие графы?
а
)
б
)
3. Найдите дополнения приведенных ниже графов.
а) б)
4
.
Найдите точки сочленения, мосты, блоки.
5. Которые из приведенных ниже графов являются деревьями?
а) б) в)
5. Способы задания графов
Представление проиллюстрируем на следующих примерах:
Граф
G Граф D
5.1. Матрица смежности
Представление графа с помощью квадратной булевской матрицы M: array [1..p, 1..p] of 0..1, отражающей смежность вершин, называется матрицей смежности, где
Пример.
|
|
1 |
2 |
3 |
4 |
|
|
|
1 |
2 |
3 |
4 |
|
1 |
0 |
1 |
0 |
1 |
|
|
1 |
0 |
1 |
0 |
0 |
G: |
2 |
1 |
0 |
1 |
1 |
|
D: |
2 |
0 |
0 |
1 |
1 |
|
3 |
0 |
1 |
0 |
1 |
|
|
3 |
0 |
0 |
0 |
0 |
|
4 |
1 |
1 |
1 |
0 |
|
|
4 |
1 |
0 |
1 |
0 |
5.2. Матрица инциденций
Представление графа с помощью матрицы H: array [1..p, 1..q] of 0..1 (для орграфов H: array [1..p, 1..q] of –1..1), отражающей инцидентность вершин и ребер, называется матрицей инциденций, где для неориентированного графа
а для ориентированного графа
Пример.
|
|
1 |
2 |
3 |
4 |
5 |
|
|
|
1 |
2 |
3 |
4 |
5 |
|
1 |
1 |
0 |
0 |
1 |
0 |
|
|
1 |
1 |
0 |
0 |
–1 |
0 |
G: |
2 |
1 |
1 |
0 |
0 |
1 |
|
D: |
2 |
–1 |
1 |
0 |
0 |
1 |
|
3 |
0 |
1 |
1 |
0 |
0 |
|
|
3 |
0 |
–1 |
–1 |
0 |
0 |
|
4 |
0 |
0 |
1 |
1 |
1 |
|
|
4 |
0 |
0 |
1 |
1 |
–1 |