Графы
Графы
В этом уроке, мы изучим граф, узнаем краткое определение, научимся зарисовывать графы, строить списки и матрицы смежности. В практическом задании второй части научимся восстанавливать графы по таблицам. Узнаем немного про виды графов. Сможем решить задачи на построение графов.
Граф играет важнейшую роль в области информационных технологий, компьютерных сетей, построении карт местности. На основе графов строятся мобильные и компьютерные сети.
Граф – набор вершин и связей между ними.
Вершины соединяются ребрами.
В данном примере количество вершин равно четырем. Количество ребер – 4. Однако не все вершины между собой взаимосвязаны. Такой граф не является полно связным. В общем случае, для обозначения взаимосвязей составляется матрица смежности. Для обозначения вершин необходимо выполнить нумерацию (буквами, цифрами) слева направо.
А
В
С
D
A
0
1
1
0
B
1
0
1
1
C
1
1
0
0
D
0
1
0
0
Дополнительно, для удобства к графу составляется список смежности.
А(В,С)
В (A, C, D)
С (A, B)
D (B)
Задачи для самостоятельного выполнения.
Составить граф на основе матрицы смежности
А
В
С
D
E
A
0
0
0
0
1
B
1
0
1
1
1
C
1
1
0
0
1
D
0
0
1
0
1
E
1
1
1
0
0
А
В
С
D
E
A
0
0
1
0
1
B
0
0
0
1
1
C
1
1
1
1
1
D
0
0
1
0
0
E
0
1
1
0
0
Автор: Ильюхин Руслан Васильевич