Главная / Алгоритмы и дискретные структуры /
Введение в теорию графов / Тест 7
Введение в теорию графов - тест 7
Упражнение 1:
Номер 1
Методом Мальгранжа разбить граф, представленный ниже матрицей смежности, на подграфы
| X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 |
---|
X1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
---|
X2 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
---|
X3 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
---|
X4 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
---|
X5 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
---|
X6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
---|
X7 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
---|
X8 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
---|
Ответ:
 (1) G1={x1, x2 , х7, х8 }, G2 = { х3, х4, х5 }, G3 ={х6}
 
 (2) G1={x1, x2 , х7, х8 }, G2 = { х3, х4 }, G3 ={ х5 ,х6}
 
 (3) G1={x1, x2 }, G2 = { х3, х4, х5 }, G3 ={х6, х7, х8 }
 
Номер 2
Методом Мальгранжа разбить граф, представленный ниже матрицей смежности, на подграфы
| X1 | X2 | X3 | X4 | X5 | X6 | X7 |
---|
X1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
---|
X2 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
---|
X3 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
---|
X4 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
---|
X5 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
---|
X6 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
---|
X7 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
---|
Ответ:
 (1) G1={x1, x2 , х7}, G2 = { х3, х4 }, G3 ={ х5 ,х6}
 
 (2) G1={x1, x2 , х7, х6 }, G2 = { х3, х4, х5 }
 
 (3) G1={x1, x2 }, G2 = { х3, х4, х5 }, G3 ={х6, х7 }
 
Номер 3
Методом Мальгранжа разбить граф, представленный на рисунке, на подграфы
Ответ:
 (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
Методом Мальгранжа разбить граф, представленный на рисунке, на максимальные сильно связные подграфы
Ответ:
 (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
Методом Мальгранжа разбить граф, представленный матрицей смежности, на максимальные сильно связные подграфы
| X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 |
---|
X1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 |
---|
X2 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
---|
X3 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
---|
X4 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
---|
X5 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
---|
X6 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
---|
X7 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
---|
X8 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
---|
Ответ:
 (1) G1={x1, x2 , х7, х8 }, G2 = { х3, х4 }, G3 ={ х5 ,х6}
 
 (2) G1={x1, x2 , х3, х5, х7, х8 }, G2 = { х4, х6}
 
 (3) G1={x1, x2 }, G2 = { х3, х4, х5 }, G3 ={х6, х7, х8 }
 
Номер 3
Методом Мальгранжа разбить граф, представленный на рисунке, на максимальные сильно связные подграфы
Ответ:
 (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
рассмотреть на примере графа, изображенного на рисунке
Ответ:
 (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
рассмотреть на примере графа, изображенного матрицей смежности
| X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 |
---|
X1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
---|
X2 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
---|
X3 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
---|
X4 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
---|
X5 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
---|
X6 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
---|
X7 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
---|
X8 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
---|
Ответ:
 (1) G1={x1, x2 , х7, х8 }, G2 = { х3, х4, х5 }, G3 ={х6}
 
 (2) G1={x1, x2 , х7, х8 }, G2 = { х3, х4 }, G3 ={ х5 ,х6}
 
 (3) G1={x1, x2 }, G2 = { х3, х4, х5 }, G3 ={х6, х7, х8 }
 
Номер 3
Метод разбиения графа по матрицам R
и Q
рассмотреть на примере графа, изображенного матрицей смежности
| X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 |
---|
X1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
---|
X2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
---|
X3 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
---|
X4 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
---|
X5 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
---|
X6 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
---|
X7 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
---|
X8 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
---|
Ответ:
 (1) G1={x1, x2 , х7, х8 }, G2 = { х3, х4 }, G3 ={ х5 ,х6}
 
 (2) G1={x1, x2 , х7, х8 }, G2 = { х3, х4, х5 }, G3 ={х6}
 
 (3) G1={x1, x2 }, G2 = { х3, х4, х5 }, G3 ={х6, х7, х8 }