Ответы к тесту/контрольной: Введение в теорию графов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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