Главная /
Введение в теорию графов /
Методом Мальгранжа разбить граф, представленный ниже матрицей смежности, на подграфы [таблица]
Методом Мальгранжа разбить граф, представленный ниже матрицей смежности, на подграфы
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 |
Правильный ответ:
G1={x1, x2 , х7, х8 }, G2 = { х3, х4, х5 }, G3 ={х6}
G1={x1, x2 , х7, х8 }, G2 = { х3, х4 }, G3 ={ х5 ,х6}
G1={x1, x2 }, G2 = { х3, х4, х5 }, G3 ={х6, х7, х8 }
Сложность вопроса
84
Сложность курса: Введение в теорию графов
78
Оценить вопрос
Комментарии:
Аноним
Зачёт всё. Лечу в бар отмечать 5 за тест интуит
23 авг 2016
Другие ответы на вопросы из темы алгоритмы и дискретные структуры интуит.
- # По матрице смежности, данной ниже подсчитать полустепень захода второй вершины dt(х2) 101100010101000101001001100000010001
- # Какая из представленных матриц контрдостижимости соответствует графу на рис. 1? аX1X2X3X4X5X6X1000111Q=X2101111X3100111X4100011X5100101X6100110 бX1X2X3X4X5X6X1100111Q=X2111111X3101111X4100111X5100111X6100111вX1X2X3X4X5X6X1111111Q=X2010000X3011000X4111111X5111111X6111111 [Большая Картинка]
- # Дан граф на риунке 1. Какой из приведенных на рисунке 2 графов является для него порожденным подграфом? [Большая Картинка] [Большая Картинка]
- # Для графа [Большая Картинка] аX1X2X3X4X5X101000X200101X300001X400100X500100bX1X2X3X4X5X101000X200101X300011X400010X500110 cX1X2X3X4X5X101000X200101X300011X400000X500100
- # [Большая Картинка] Для графа, представленного на рисунке даны замкнутые пути: М1: (х2, х3), (х3, х4), (х4, х7), (х7, х2) М2: (х2, х3), (х3, х4), (х4, х5), (х5, х6), (х6, х2) (х2, х3), (х3, х7), (х7, х2) М3: (х2, х3), (х3, х4), (х4, х5), (х5, х6), (х6, х2) М4: (х3, х4), (х4, х5), (х5, х7), (х7, х3) М5: (х1, х2), (х2, х3), (х3, х4), (х4, х5), (х5, х6), (х6, х1) М6: (х1, х2), (х2, х3), (х3, х4), (х4, х5), (х5, х7), (х7, х6) (х6, х1) М7: (х2, х3), (х3, х4), (х4, х5), (х5, х7), (х7, х6), (х6, х1), (х1, х2) Какие из этих путей являются гамильтоновыми контурами?