Практика Графы. Практика 3.1. Основные понятия теории графов. Решение 0 1 0 0 0 0 0 0 1 1 1 1 0 1 0 1 0 0 0 1 0 0 1 0 0 a

• Название: Решение 0 1 0 0 0 0 0 0 1 1 1 1 0 1 0 1 0 0 0 1 0 0 1 0 0 a
• Анкор: Практика Графы
• Дата: 14.03.2023
• Размер: 107.83 Kb.
• Имя файла: Практика 3.1. Основные понятия теории графов.pdf
• Тип: Решение; #988689

Тема 3.1. Основные понятия теории графов
План: Основные понятия теории графов. Ориентированные и неориентированные графы.
Элементы графа: вершины, ребра, дуги. Геометрические графы. Матрицы смежности и инцидентности.
Задачи с решением
Пример 1: Для графа, изображенного на рисунке посторить матрицу смежности
Решение:
0 1
0 0
0 0
0 0 1 1 1
1 0
1 0
1 0
0 0
1 0
0 1
0 0
A








=








Пример 2: Для графа G, изображенного на рисунке построить матрицу инцидентности
Решение:
1 2
3 4
5 2
3 4
5 6

1 1
0 0
0 0
1 1
1 1 1 1 .
0 0
0 1 1 1
B
−
−




=
−




−
−


Пример 3: для графа построить матрицу весов.
Решение:
0 12 0
17 7
0 11 0
15 8
18 0
W
∞ ∞ ∞




∞
∞




= ∞ ∞
∞


∞ ∞ ∞




∞
∞


Задачи для самостоятельного решения
1.
Для неориентированного графа, изображенного на рисунке, постройте матрицу смежности и матрицу инцидентности. Укажите степени вершин графа. Выделите в графе циклы, содержащие 4 ребра, 6 ребер, 10 ребер.
2.
Записать матрицы смежности и инцидентности для графов.
а б в
b
a
d
e
c
12 17 7
18 8
11 15