Ответы на вопросы из коллекции "Введение в теорию графов" на СтудИзбе

Найти максимальный сильно связанный подграф, включающий вершину Е, для графа, матрица смежности которого представлена ниже ABCDEFGKA11001000B00101100C00101000D00000001E00000100F10000010G00000001K00010000

• Gмсс={ B, C, E, F}
• Gмсс={A, B, C, E, F}
• Gмсс={A, B, E, F}

По матрицам смежности определить какие из графов являются полными.а1111001010001100001011110b0101000011110000010110100c1101111101011111011111111d0000010000110001110011110

• b, d
• d
• а, b, d

Методом Мальгранжа разбить граф, представленный ниже матрицей смежности, на подграфы X1X2X3X4X5X6X7X8X111010000X210100010X300001000X400100000X500010000X600000000X701000101X810000000

• 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 }

Выполнить операцию пересечения G1 ∩ G2 для графов, представленных матрицами смежности в таблице 1Матрица смежности G1X1X2X3X4X5X100001X210010X300000X400100X501010Матрица смежности G2X1X2X3X4X5X100001X210101X300000X401101X500000aX1X2X3X4X5X100001X210000X300000X400100X500000бX1X2X3X4X5X100000X200111X300000X401001X501010вX1X2X3X4X5X100001X210111X300000X401101X501010

• граф представлен б
• граф представлен а
• граф представлен в

Найти максимальный сильно связанный подграф, включающий вершину F, для графа, матрица смежности которого представлена нижеABCDEFGKA11001000B00101100C00101000D00000001E00000100F10000010G00000001K00010000

• Gмсс={ B, C, E, F}
• Gмсс={A, B, C, E, F}
• Gмсс={A, B, E, F}

По матрице смежности, данной ниже подсчитать количество петель графа. 101100010101000101001001100000010001

• 2
• петель нет
• 3

Значение постоянной метки показывает

• значение кратчайшего пути
• число итераций
• значение среднего пути

Метод разбиения графа по матрицам R и Q рассмотреть на примере графа, изображенного матрицей смежностиX1X2X3X4X5X6X7X8X111010000X210101010X300001000X400110000X500011000X600000100X701100101X810000001

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

Выполнить операцию нахождения кольцевой суммы G1 ⊕ G2 для графов, представленных матрицами смежности в таблице 1Матрица смежности G1X1X2X3X4X5X100001X210010X300000X400100X501010Матрица смежности G2X1X2X3X4X5X100001X210101X300000X401101X500000aX1X2X3X4X5X100001X210000X300000X400100X500000бX1X2X3X4X5X100000X200111X300000X401001X501010вX1X2X3X4X5X100001X210111X300000X401101X501010

• граф представлен б
• граф представлен в
• граф представлен а

Для нахождения кратчайшего пути от s к хi, предшествующую вершину xi* можно найти как одну из вершин, для которой

• L(xi*)-c(xi*)=L(xi)
• L(xi*) c(xi*)=L(xi)
• L(xi*) + c(xi*)=L(xi* xi)

Для чего использую алгоритм Дейкстра?

• для построения матрицы смежности
• для поиска кратчайших путей
• для поиска максимального сильного подграфа
• для поиска вершин графа, имеющих нечетную степень

По матрице инциденций найти полустепени исхода для Х2 a1a2a3a4a5a6a7a8a9a10X11-110101000X201-11000000X3000-1-110100X4000000-1-110X500000000-1-1X600000-10001

• d0(х2)=2
• d0(х2)=3
• d0(х2)=1

По матрицам смежности, приведенным ниже определить какие из графов являются полными.а1111001100011111b0101000100101010c1011110101111111d0000100011001110

• а, c, d
• a, с
• d

По матрице смежности, данной ниже подсчитать полустепень захода второй вершины dt(х2) 101100010101000101001001100000010001

• dt(х2)=3
• dt(х2)=2
• dt(х2)=-2

Метод разбиения графа по матрицам R и Q рассмотреть на примере графа, изображенного матрицей смежностиX1X2X3X4X5X6X7X8X111100000X210100010X300001000X400110000X500011000X600000100X701000101X810101000

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

Если с помощью алгоритма Дейкстры требуется найти кратчайшие пути от вершины x3 до других вершин графа, то в первой итерации ей присваивается пометка со значением ...

• равным количеству вершин графа
• 0
• 3
• равным количеству ребер графа

Обновление пометок на каждой итерации алгоритма Дейкстры происходит

• для вершин графа, имеющих временные метки
• для вершин графа, имеющих временные метки и входящих в прямое отображение для рассматриваемой вершины
• для всех вершин графа

По матрицам смежности определить какие из графов являются полными.а1111001100010000b0101000100101010c1010110101110111d1010110001101010

• а, c, d
• a, с
• a

Выполнить операцию объединения G1 ∪ G2 для графов, представленных матрицами смежности в таблице 1Матрица смежности G1X1X2X3X4X5X100001X210010X300000X400100X501010Матрица смежности G2X1X2X3X4X5X100001X210101X300000X401101X500000aX1X2X3X4X5X100001X210000X300000X400100X500000бX1X2X3X4X5X100000X200111X300000X401001X501010вX1X2X3X4X5X100001X210111X300000X401101X501010

• граф представлен в
• граф представлен а
• граф представлен б

Соответствует ли матрица инциденций матрице смежности (обе матрицы представлены ниже): матрица инциденций a1a2a3a4a5a6a7a8a9a10X11-110101000X201-11000000X3000-1-110100X4000000-1-110X500000000-1-1X600000-10001матрица смежностиX1X2X3X4X5X6X1111100X2101000X3000101X4000010X5000000X6000010

• не соответствует
• соответсвует
• соответсвует только для неориентированного графа

По матрице смежности, данной ниже подсчитать полустепень исхода второй вершины do(х2) 101100010101000101001001100000010001

• d0(х2)=-2
• d0(х2)=2
• d0(х2)=3

По матрице инциденций найти полустепени захода для Х2 a1a2a3a4a5a6a7a8a9a10X12-110101000X201-11000000X3000-1-110100X4000000-1-110X500000000-1-1X600000-10001

• dt(х2)=3
• dt(х2)=2
• dt(х2)=1

Методом Мальгранжа разбить граф, представленный ниже матрицей смежности, на подграфыX1X2X3X4X5X6X7X11101000X21010010X30000100X40010000X50001000X60100001X71000000

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

Найти максимальный сильно связанный подграф, включающий вершину C, для графа, матрица смежности которого представлена ниже ABCDEFGKA11001000B00101100C00101000D00000001E00000100F10000010G00000001K00010000

• Gмсс={ B, C, E, F}
• Gмсс={A, B, C, E, F}
• Gмсс={A, B, C, F}

Обновление пометок происходит по формуле:

• L(хi) = min [ L(хi), C(p, хi) ]
• L(хi) = min [ L(хi), L(p) + C(p, хi) ]
• L(хi) = min [ L(хi), L(p) - C(p, хi) ]

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

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