Министерство образования и науки Российской Федерации
Курский государственный технический университет
Кафедра ПО ВТ и АС
Лабораторная работа № 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 |
|
A2
G2(X2,A2)
2. Построить для каждого графа матрицу смежности ребер, инцидентности, достижимости, контрдостижимости.
|
а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 |
|
Q1 Q2
3. Найти и построить объединение, пересечение, кольцевую сумму заданных графов.
Объединение графов
G3(X3,A3)=G1(X1,A1) YG2(X2,A2); X3= X1YX2, A3= A1YA2
Пересечение графов
G3(X3,A3)=G1(X1,A1) ?G2(X2,A2); X3= X1?X2, A3= A1?A2
Кольцевая сумма графов
G3(X3,A3)=G1(X1,A1)G2(X2,A2)
4. Найти и построить композицию графов .
|
G1(Х) |
G2(Х) |
G1(G2(Х)) |
G2(G1(Х)) |
|||||||||||||||
|
x1 |
(x1,x2), (x1,x7) |
(x1,x2), (x1,x3) |
(x1,x3), (x1,x6), (x1,x2), (x1,x4), |
(x1,x4), (x1,x5), (x1,x3), (x1,x6), |
||||||||||||||
|
x2 |
(x2,x3), (x2,x6) |
(x2,x4), (x2,x5) |
(x2,x1), (x2,x5), (x2,x7), |
(x2,x2), (x2,x7), (x2,x1), (x2,x4), |
||||||||||||||
|
x3 |
(x3,x2), (x3,x4) |
(x3,x2), (x3,x7) |
(x3,x3), (x3,x6), (x3,x5), |
(x3,x4), (x3,x5), (x3,x1), |
||||||||||||||
|
x4 |
(x4,x1), (x4,x5) |
(x4,x1), (x4,x5) |
(x4,x2), (x4,x7), (x4,x1), |
(x4,x2), (x4,x3), (x4,x6), (x4,x7), |
||||||||||||||
|
x5 |
(x5,x1), (x5,x7) |
(x5,x6), (x5,x7) |
(x5,x3), (x5,x4),</ p> (x5,x5), (x5,x6),
G1(G2(Х)) G2(G1(Х)) 5. Для каждого графа найти и построить остовный подграф, произвольный подграф, порожденный подграф. Остовные подграфы G1(X1,A1) G2(X2,A2) Произвольные подграфы G1 (X1,A1) G2 (X2,A2) Порожденные подграфы G1P(X1P,A1P) G2P(X2P,A2P) 6. Определить локальные степени вершин графа, проверить существует ли в данном графе эйлерова цепь, эйлеров цикл. Локальные степени графа G1 1 (х1)=2 ; 2 (х1)=2 ; (х1)=4 ; 1 (х2)=2 ; 2 (х2)=2 ; (х2)=4 ; 1 (х3)=2 ; 2 (х3)=2 ; (х3)=4 ; 1 (х4)=2 ; 2 (х4)=2 ; (х4)=4 ; 1 (х5)=2 ; 2 (х5)=2 ; (х5)=4 ; 1 (х6)=2 ; 2 (х6)=2 ; (х6)=4 ; 1 (х7)=2 ; 2 (х7)=2 ; (х7)=4 ; Локальные степени графа G2 1 (х1)=2 ; 2 (х1)=2 ; (х1)=4 ; 1 (х2)=2 ; 2 (х2)=2 ; (х2)=4 ; 1 (х3)=3 ; 2 (х3)=2 ; (х3)=4 ; 1 (х4)=2 ; 2 (х4)=2 ; (х4)=4 ; 1 (х5)=2 ; 2 (х5)=2 ; (х5)=4 ; 1 (х6)=2 ; 2 (х6)=2 ; (х6)=4 ; 1 (х7)=2 ; 2 (х7)=2 ; (х7)=4 ; Эйлерова цепь существует в двух графах, т.к. все локальные степени графов четны. Эйлеров цикл существует в двух графах, т.к. все локальные степени графов четны. 7. Определить хроматические и цикломатические числа данных графов. Хроматическое число г для графа G1 = 4 Хроматическое число г для графа G2 = 4 Цикломатические числа графов V(G1)=m-n+r, где m - число рёбер (дуг); n - число вершин; r - число компонент связности. V(G1)=14-7+1=8; V(G2)=14-7+1=8; 8. Найти все базы графа. Базы графа G1 B1={x1} B2={x2} B3={x3} B4={x4} B5={x5} B6={x6} B7={x7} Базы графа G2 B1={x1} B2={x2} B3={x3} B4={x4} B5={x5} B6={x6} B7={x7} 9. Определить в каждом графе сильные компоненты связности, построить конденсацию графа. Сильные компоненты связности G1 СК={x1, x2, x3, x4, x5, x6, x7} Сильные компоненты связности G2 СК={x1, x2, x3, x4, x5, x6, x7} Конденсация графа G1 Конденсация графа G2 |
| Контрольная работа | Концепция информатизации Российской Федерации |
| Контрольная работа | Причины агрессивного поведения. Методы работы с агрессивными детьми |
| Контрольная работа | Алгоритм выбора и реализации предпринимательской идеи |
| Контрольная работа | Современные методы арт-терапии |
| Контрольная работа | Системы управления взаимоотношения с клиентами |
| Контрольная работа | Учет материальных затрат в бухгалтерском учете |
| Контрольная работа | Геополитическое положение России |
| Контрольная работа | Особенности вознаграждения работников в организации |
| Контрольная работа | Виды запасов |
| Контрольная работа | Психоанализ |
| Контрольная работа | Электронно-цифровая подпись |
| Контрольная работа | Закон диалектического противоречия. |
| Контрольная работа | Геодезия в строительстве |
| Контрольная работа | Впровадження інформаційної системи управління на підприємстві |
| Контрольная работа | Генератор случайных чисел |