85567 (Графы. Основные понятия)
Описание файла
Документ из архива "Графы. Основные понятия", который расположен в категории "". Всё это находится в предмете "математика" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "лабораторные работы", в предмете "математика" в общих файлах.
Онлайн просмотр документа "85567"
Текст из документа "85567"
Министерство образования и науки Российской Федерации
Курский государственный технический университет
Кафедра ПО ВТ и АС
Лабораторная работа № 1
Графы. Основные понятия
Выполнил: студент гр. ПО 62 Шиляков И.А.
Проверил: доцентТомакова Р.А.
Курск 2007
Задание:
-
По заданным матрицам смежности вершин восстановить графы.
-
Построить для каждого графа матрицу смежности ребер, инцидентности, достижимости, контрдостижимости.
-
Найти и построить объединение, пересечение, кольцевую сумму заданных графов.
-
Найти композицию графов .
-
Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф.
-
Определить локальные степени вершин графа, проверить существует ли в данном графе эйлерова цепь, эйлеров цикл.
-
Определить хроматические и цикломатические числа данных графов.
-
Найти все базы графа.
-
Определить в каждом графе сильные компоненты связности, построить конденсацию графа.
Выполнение:
-
По заданным матрицам смежности вершин восстановить графы.
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
X2
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 |
A2
X2
G2(X2,A2)
-
Построить для каждого графа матрицу смежности ребер, инцидентности, достижимости, контрдостижимости.
а1 | а2 | а3 | а4 | а5 | а6 | а7 | а8 | а9 | а10 | а11 | а12 | а13 | а14 | |
а1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
а2 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
а3 | 1 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
а4 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
а5 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
а6 | 0 | 0 | 1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 0 |
а7 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 0 |
а8 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 1 | 0 | 1 | 1 | 0 |
а9 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
а10 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 |
а11 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 |
а12 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 1 |
а13 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 1 |
а14 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 |
B1
а1 | а2 | а3 | а4 | а5 | а6 | а7 | а8 | а9 | а10 | а11 | а12 | а13 | а14 | |
а1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
а2 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
а3 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 0 |
а4 | 1 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
а5 | 1 | 1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
а6 | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
а7 | 1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 1 | 1 | 0 |
а8 | 0 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 |
а9 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 1 |
а10 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
а11 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 1 | 1 |
а12 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 | 1 | 1 |
а13 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 1 | 1 | 0 | 1 |
а14 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 0 |
B2
а1 | а2 | а3 | а4 | а5 | а6 | а7 | а8 | а9 | а10 | а11 | а12 | а13 | а14 | |
x1 | 1 | 1 | 0 | 0 | 0 | 0 | -1 | 0 | -1 | 0 | 0 | 0 | 0 | 0 |
x2 | -1 | 0 | 1 | 1 | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
x3 | 0 | 0 | -1 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 0 |
x4 | 0 | 0 | 0 | 0 | 0 | -1 | 1 | 1 | 0 | 0 | 0 | -1 | 0 | 0 |
x5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 1 | 1 | 0 | 0 | -1 | 0 |
x6 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | -1 |
x7 | 0 | -1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 1 | 1 |
S1
а1 | а2 | а3 | а4 | а5 | а6 | а7 | а8 | а9 | а10 | а11 | а12 | а13 | а14 | |
x1 | 1 | 0 | 0 | 1 | 0 | 0 | -1 | 0 | -1 | 0 | 0 | 0 | 0 | 0 |
x2 | 0 | -1 | 1 | -1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
x3 | -1 | 1 | 0 | 0 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
x4 | 0 | 0 | -1 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | -1 | 1 | 0 |
x5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 1 | 0 | -1 | 1 |
x6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | -1 | 0 | 1 | 0 | -1 |
x7 | 0 | 0 | 0 | 0 | 1 | -1 | 0 | 0 | 0 | 1 | -1 | 0 | 0 | 0 |
S2
x1 | x2 | x3 | x4 | x5 | x6 | x7 | |
x1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x3 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x5 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x6 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x7 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x1 | x2 | x3 | x4 | x5 | x6 | x7 | |
x1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x3 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x5 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x6 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x7 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
R1 R2
x1 | x2 | x3 | x4 | x5 | x6 | x7 | |
x1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x3 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x5 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x6 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x7 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x1 | x2 | x3 | x4 | x5 | x6 | x7 | |
x1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x2 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x3 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x4 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x5 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x6 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |
x7 | 1 | 1 | 1 | 1 | 1 | 1 | 1 |