|
Графы. Основные понятия
Министерство образования и науки Российской Федерации Курский государственный технический университет Кафедра ПО ВТ и АС Лабораторная работа № 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), (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'') 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
|
|
|