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