Лабораторная работа: Графы. Основные понятия
Лабораторная работа: Графы. Основные понятия
Министерство образования и науки Российской Федерации
Курский государственный технический университет
Кафедра ПО ВТ и АС
Лабораторная работа № 1
Графы. Основные понятия
Выполнил: студент гр. ПО 62 Шиляков И.А.
Проверил: доцентТомакова Р.А.
Курск 2007
Задание:
1. По заданным матрицам смежности вершин восстановить графы.
2. Построить для каждого графа матрицу смежности ребер, инцидентности, достижимости, контрдостижимости.
3. Найти и построить объединение, пересечение, кольцевую сумму заданных графов.
4.
Найти композицию
графов 
.
5. Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф.
6. Определить локальные степени вершин графа, проверить существует ли в данном графе эйлерова цепь, эйлеров цикл.
7. Определить хроматические и цикломатические числа данных графов.
8. Найти все базы графа.
9. Определить в каждом графе сильные компоненты связности, построить конденсацию графа.
Выполнение:
1. По заданным матрицам смежности вершин восстановить графы.
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
|
x1 |
0 | 1 | 0 | 0 | 0 | 0 | 1 |
|
x2 |
0 | 0 | 1 | 0 | 0 | 1 | 0 |
|
x3 |
0 | 1 | 0 | 1 | 0 | 0 | 0 |
|
x4 |
1 | 0 | 0 | 0 | 1 | 0 | 0 |
|
x5 |
1 | 0 | 0 | 0 | 0 | 0 | 1 |
|
x6 |
0 | 0 | 1 | 1 | 0 | 0 | 0 |
|
x7 |
0 | 0 | 0 | 0 | 1 | 1 | 0 |
A1
|
G1(X1,A1)
|
x1 |
x2 |
x3 |
x4 |
x5 |
x6 |
x7 |
|
|
x1 |
0 | 1 | 1 | 0 | 0 | 0 | 0 |
|
x2 |
0 | 0 | 0 | 1 | 1 | 0 | 0 |
|
x3 |
0 | 1 | 0 | 0 | 0 | 0 | 1 |
|
x4 |
1 | 0 | 0 | 0 | 1 | 0 | 0 |
|
x5 |
0 | 0 | 0 | 0 | 0 | 1 | 1 |
|
x6 |
1 | 0 | 0 | 1 | 0 | 0 | 0 |
|
x7 |
0 | 0 | 1 | 0 | 0 | 1 | 0 |
