игра брюс 2048
Главная / Алгоритмы и дискретные структуры / Введение в теорию графов / Тест 7

Введение в теорию графов - тест 7

Упражнение 1:
Номер 1
Методом Мальгранжа разбить граф, представленный ниже матрицей смежности, на подграфы
 
X1X2X3X4X5X6X7X8
X111010000
X210100010
X300001000
X400100000
X500010000
X600000000
X701000101
X810000000

Ответ:

 (1) G1={x1, x2 , х7, х8 }, G2 = { х3, х4, х5 }, G3 ={х6}  

 (2) G1={x1, x2 , х7, х8 }, G2 = { х3, х4 }, G3 ={ х56} 

 (3) G1={x1, x2 }, G2 = { х3, х4, х5 }, G3 ={х6, х7, х8 }  


Номер 2
Методом Мальгранжа разбить граф, представленный ниже матрицей смежности, на подграфы
X1X2X3X4X5X6X7
X11101000
X21010010
X30000100
X40010000
X50001000
X60100001
X71000000

Ответ:

 (1) G1={x1, x2 , х7}, G2 = { х3, х4 }, G3 ={ х56}  

 (2) G1={x1, x2 , х7, х6 }, G2 = { х3, х4, х5 }  

 (3) G1={x1, x2 }, G2 = { х3, х4, х5 }, G3 ={х6, х7 } 


Номер 3
Методом Мальгранжа разбить граф, представленный на рисунке, на подграфыfiles

Ответ:

 (1) G1={x1, x2 , х7, х8 }, G2 = { х3, х4, х5 }, G3 ={х6}  

 (2) G1={x1, x2 , х7, х8 }, G2 = { х3, х4, х6 }, G3 ={х5}  

 (3) G1={x1, x2 }, G2 = { х3, х4, х5 }, G3 ={х6, х7, х8 }  


Упражнение 2:
Номер 1
Методом Мальгранжа разбить граф, представленный на рисунке, на максимальные сильно связные подграфыfiles

Ответ:

 (1) G1={x1, x2 }, G2 = { х3, х4, х5 }, G3 ={х6, х4, х7, х8 }  

 (2) G1={x1, x2 , х8 }, G2 = { х3, , х7, х5 }, G3 ={х6 , х4}  

 (3) G1={x1, x2 , х3, х5 , х7, х8 }, G2 ={ х4 , х6}  


Номер 2
Методом Мальгранжа разбить граф, представленный матрицей смежности, на максимальные сильно связные подграфы
X1X2X3X4X5X6X7X8
X101000001
X210101000
X300011000
X400000100
X500100010
X600010000
X710001100
X800000010

Ответ:

 (1) G1={x1, x2 , х7, х8 }, G2 = { х3, х4 }, G3 ={ х56}  

 (2) G1={x1, x2 , х3, х5, х7, х8 }, G2 = { х4, х6}  

 (3) G1={x1, x2 }, G2 = { х3, х4, х5 }, G3 ={х6, х7, х8 }  


Номер 3
Методом Мальгранжа разбить граф, представленный на рисунке, на максимальные сильно связные подграфыfiles

Ответ:

 (1) G1={x1, x2 }, G2 = { х3, х4, х5 }, G3 ={х6, х4, х7, х8 }  

 (2) G1={x1, x2 , х3, х5 , х7, х8 }, G2 ={ х4 , х6}  

 (3) G1={x1, x2 , х8 }, G2 = { х3, , х7, х5 }, G3 ={х6 , х4}  


Упражнение 3:
Номер 1
Метод разбиения графа по матрицам  R  и  Q  рассмотреть на примере графа, изображенного на рисункеfiles

Ответ:

 (1) G1={x1, x2 }, G2 = { х3, х4, х5 }, G3 ={х6, х4, х7, х8 }  

 (2) G1={x1, x2 , х8 }, G2 = { х3, , х7, х5 }, G3 ={х6 , х4} 

 (3) G1={x1, x2 , х7, х8 }, G2 ={ х4, х3, х5} G3 ={ х6}  


Номер 2
Метод разбиения графа по матрицам R и Q рассмотреть на примере графа, изображенного матрицей смежности
X1X2X3X4X5X6X7X8
X111100000
X210100010
X300001000
X400110000
X500011000
X600000100
X701000101
X810101000

Ответ:

 (1) G1={x1, x2 , х7, х8 }, G2 = { х3, х4, х5 }, G3 ={х6} 

 (2) G1={x1, x2 , х7, х8 }, G2 = { х3, х4 }, G3 ={ х56}  

 (3) G1={x1, x2 }, G2 = { х3, х4, х5 }, G3 ={х6, х7, х8 }  


Номер 3
Метод разбиения графа по матрицам  R  и  Q  рассмотреть на примере графа, изображенного матрицей смежности
X1X2X3X4X5X6X7X8
X111010000
X210101010
X300001000
X400110000
X500011000
X600000100
X701100101
X810000001

Ответ:

 (1) G1={x1, x2 , х7, х8 }, G2 = { х3, х4 }, G3 ={ х56}  

 (2) G1={x1, x2 , х7, х8 }, G2 = { х3, х4, х5 }, G3 ={х6}  

 (3) G1={x1, x2 }, G2 = { х3, х4, х5 }, G3 ={х6, х7, х8 } 




Главная / Алгоритмы и дискретные структуры / Введение в теорию графов / Тест 7