Граф - это метод наглядного графического представления состава и структуры системы.
Граф состоит из вершин, связанных ребрами (или дугами).
Вершины, прилегающие к одному и тому же ребру, называются смежными. Два ребра, у которых есть общая вершина, также называются смежными (или соседними).
Граф называется ориентированным (или направленным), если некоторые ребра имеют направление. Это означает, что в таком графе некоторая вершина может быть соединена с другой вершиной, а обратного соединения нет. Если ребра ориентированы, что обычно показывают стрелками, то они называются дугами. Смешанный граф G — это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые — неориентированными.
Взвешенный граф — граф, каждому ребру которого поставлено в соответствие некое значение (вес ребра).
Граф может быть представлен в виде матрицы смежности - таблицы, где как столбцы, так и строки соответствуют вершинам графа. В каждой ячейке этой матрицы записывается число, определяющее наличие связи и вес соответствующего ребра от вершины-строки к вершине - столбцу (либо наоборот).
При этом, надо понимать, что одной таблице могут соответствовать графы, которые выглядеть очень по-разному. Важно уметь строить матрицу смежности по графу и наоборот, соотносить разные графы, понимать, что графы различаются не расположением вершин, а наличием либо отсутствием связей (ребер) между вершинами и весом тих ребер.
A
|
B
|
C
|
D
|
E
| |
A
|
-
|
7
|
5
| ||
B
|
7
|
-
|
2
|
1
| |
C
|
5
|
2
|
-
|
9
| |
D
|
9
|
-
|
12
| ||
E
|
1
|
12
|
-
|
Матрица смежности.
При решении задач требуется уметь: строить матрицу смежности по графу, и граф по матрице смежности, находить соответствие между матрицей и графом, находить расстояние между вершинами графа, находить наиболее удаленные вершины графа.
Расстояние между вершинами графа - это кратчайший из всех возможных путей, соединяющих эти вершины. Для нахождения длины пути во взвешенном графу требуется сложить вес всех ребер, по которым этот путь пролегает.
На рис.4 расстояние CB=9 (то есть сумма длин ребер CA и FB, а не вес ребра CB)
Наиболее удаленными вершинами в данном графе будут является вершины D и E. DE = 12
Задания по теме “Моделирование на графах”
Часть A. Для следующих графов построить матрицу смежности и найти расстояния между всеми парами вершин и указать пару наиболее удаленных вершин
Часть B. По матрице смежности изобразить граф, найти расстояния между всеми парами вершин и указать пару наиболее удаленных вершин.
A
|
B
|
C
|
D
|
E
| |
A
|
3
|
3
| |||
B
|
3
|
2
|
1
|
4
| |
C
|
3
|
2
|
5
| ||
D
|
1
|
5
| |||
E
|
4
|
Задание 1
A
|
B
|
C
|
D
|
E
| |
A
|
9
|
8
|
6
| ||
B
|
9
|
11
|
7
| ||
C
|
8
|
11
| |||
D
|
6
|
7
| |||
E
|
Задание 2
A
|
B
|
C
|
D
| |
A
|
9
|
7
|
8
| |
B
|
9
|
7
| ||
C
|
7
|
10
| ||
D
|
8
|
7
|
10
|
Задание 3
A
|
B
|
C
|
D
|
E
| |
A
|
5
|
9
| |||
B
|
5
|
9
| |||
C
|
7
|
8
| |||
D
|
9
|
7
|
6
| ||
E
|
9
|
8
|
6
|
Задание 4
Комментариев нет:
Отправить комментарий