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
G2’’ (X2’’,A2’’)