Главная /
Введение в теорию графов
Введение в теорию графов - ответы на тесты Интуит
Приводятся начальные сведения о графах, основные понятия и определения, способы представления графов. Рассматриваются основные операции над графами, такие как - объединение, пересечение, кольцевая сумма, удаление вершины, удаление ребра, замыкание и стягивание.
Список вопросов:
- # Какого типа граф изображен на рисунке? [Большая Картинка]
- # Является ли граф, изображенный на рисунке орграфом? [Большая Картинка]
- # Является ли граф, изображенный на рисунке смешанным графом? [Большая Картинка]
- # Какие вершины инцидентны дуге [Большая Картинка]
- # Какие вершины инцидентны дуге [Большая Картинка]
- # Какие вершины инцидентны дуге [Большая Картинка]
- # Какие дуги инцидентны вершине [Большая Картинка]
- # Какие дуги инцидентны вершине [Большая Картинка]
- # Какие дуги инцидентны вершине [Большая Картинка]
- # Перечислите дуги, являющиеся петлями в графе на рисунке? [Большая Картинка]
- # Какие дуги являются петлями в графе на рисунке? [Большая Картинка]
- # Какие дуги являются петлями в графе на рисунке ? [Большая Картинка]
- # Найдите полустепени исхода и захода для вершины [Большая Картинка]
- # Найдите полустепени исхода и захода для вершины [Большая Картинка]
- # Найдите полустепени исхода и захода для вершины [Большая Картинка]
- # Для графа, изображенного на рисунке, дать описание перечислением. [Большая Картинка]
- # Для графа, изображенного на рисунке, дать описание с помощью отображений [Большая Картинка]
- # Для [Большая Картинка] графа, изображенного на рисунке, дано описание с помощью отображений. G = (X, Г) , где X = {хi}, i = 1, 2, 3, 4 – множество вершин, Г(х1)= , Г(х2) ={ х1, х4 }, Г(х3) = { х1, х3 }, Г(х4) = { х1 } – отображения. Верно ли оно?
- # Для графа, представленного на рисунке, дана матрица смежности. Верно ли представлен граф? [Большая Картинка] матрица смежностиX1X2X3X4X11100X20011X30000X41110
- # Для графа, представленного на рисунке, дана матрица инциденций. Верно ли представлен граф? [Большая Картинка] матрица инциденцийa1a2a3a4a5a6a7X1011000-1X20-10-1100X30000-1-10X400-11011
- # Даны матрицы смежности и матрица инцидентности. Соответствуют ли они графу на рисунке? [Большая Картинка] матрица смежностиX1X2X3X4X11100X20011X30000X41110 матрица инциденцийa1a2a3a4a5a6a7X1011000-1X20-10-1100X30000-1-10X400-11011
- # По матрице смежности, данной ниже подсчитать количество петель графа. 101100010101000101001001100000010001
- # По матрице смежности, данной ниже подсчитать полустепень исхода второй вершины do(х2) 101100010101000101001001100000010001
- # По матрице смежности, данной ниже подсчитать полустепень захода второй вершины dt(х2) 101100010101000101001001100000010001
- # По матрице инциденций найти полустепени исхода для Х2 a1a2a3a4a5a6a7a8a9a10X11-110101000X201-11000000X3000-1-110100X4000000-1-110X500000000-1-1X600000-10001
- # По матрице инциденций найти полустепени захода для Х2 a1a2a3a4a5a6a7a8a9a10X12-110101000X201-11000000X3000-1-110100X4000000-1-110X500000000-1-1X600000-10001
- # Соответствует ли матрица инциденций матрице смежности (обе матрицы представлены ниже): матрица инциденций a1a2a3a4a5a6a7a8a9a10X11-110101000X201-11000000X3000-1-110100X4000000-1-110X500000000-1-1X600000-10001 матрица смежностиX1X2X3X4X5X6X1111100X2101000X3000101X4000010X5000000X6000010
- # Выполнить операцию объединения [Большая Картинка] [Большая Картинка] [Большая Картинка]
- # Выполнить операцию пересечения [Большая Картинка] [Большая Картинка] [Большая Картинка]
- # Выполнить операцию нахождения кольцевой суммы [Большая Картинка] [Большая Картинка] [Большая Картинка]
- # Выполнить операцию объединения G1 ∪ G2 для графов, представленных матрицами смежности в таблице 1Матрица смежности G1X1X2X3X4X5X100001X210010X300000X400100X501010 Матрица смежности G2X1X2X3X4X5X100001X210101X300000X401101X500000 aX1X2X3X4X5X100001X210000X300000X400100X500000бX1X2X3X4X5X100000X200111X300000X401001X501010вX1X2X3X4X5X100001X210111X300000X401101X501010
- # Выполнить операцию пересечения G1 ∩ G2 для графов, представленных матрицами смежности в таблице 1 Матрица смежности G1X1X2X3X4X5X100001X210010X300000X400100X501010 Матрица смежности G2X1X2X3X4X5X100001X210101X300000X401101X500000 aX1X2X3X4X5X100001X210000X300000X400100X500000бX1X2X3X4X5X100000X200111X300000X401001X501010вX1X2X3X4X5X100001X210111X300000X401101X501010
- # Выполнить операцию нахождения кольцевой суммы G1 ⊕ G2 для графов, представленных матрицами смежности в таблице 1 Матрица смежности G1X1X2X3X4X5X100001X210010X300000X400100X501010 Матрица смежности G2X1X2X3X4X5X100001X210101X300000X401101X500000 aX1X2X3X4X5X100001X210000X300000X400100X500000бX1X2X3X4X5X100000X200111X300000X401001X501010вX1X2X3X4X5X100001X210111X300000X401101X501010
- # Для графа [Большая Картинка] X(1,2)X3X4X5X(1,2)111X3X41X511
- # Для графа [Большая Картинка] X1X2X(3,4)X5X11X21X(3,4)1X511
- # Для графа [Большая Картинка] [Большая Картинка]
- # Для графа [Большая Картинка] X(1,2)X3X4X5X(1,2)11X3X4111X5
- # Для графа [Большая Картинка] X1X2X(3,4)X5X11X2111X(3,4)11X5
- # Для графа [Большая Картинка]
- # Для графа [Большая Картинка]
- # В графе [Большая Картинка] аX2X3X201X310бX1X2X101X210вX1X3X101X310
- # В графе [Большая Картинка] аX2X3X201X210бX1X2X101X210вX1X3X101X310
- # В графе [Большая Картинка] аX2X3X201X210бX1X2X101X210вX1X3X101X310
- # В графе [Большая Картинка] аX1X2X3X111X211X31бX1X2X3X11X211X311вX1X2X3X11X211X311
- # В графе [Большая Картинка] аX1X2X3X111X211X31бX1X2X3X11X211X311вX1X2X3X11X211X311
- # В графе [Большая Картинка] аX1X2X3X111X211X31бX1X2X3X11X211X311вX1X2X3X11X211X311
- # Найти прямые отображения для вершин [Большая Картинка]
- # Найти прямые отображения для вершин [Большая Картинка]
- # Найти прямые отображения для вершин х5 и х6графа, показанного на рисунке [Большая Картинка]
- # Найти обратные отображения для вершин [Большая Картинка]
- # Найти обратные отображения для вершин [Большая Картинка]
- # Найти обратные отображения для вершин [Большая Картинка]
- # Найти прямые многозначные отображения 4-го порядка для вершин [Большая Картинка]
- # Найти прямые многозначные отображения 2-го порядка для вершин [Большая Картинка]
- # Найти прямые многозначные отображения 3-го порядка для вершин [Большая Картинка]
- # Найти обратные многозначные отображения 3-го порядка для вершин [Большая Картинка]
- # Найти обратные многозначные отображения 4-го порядка для вершин [Большая Картинка]
- # Найти обратные многозначные отображения 4-го порядка для вершин [Большая Картинка]
- # Для графа, изображенного на рисунке найти прямые транзитивные замыкания для вершин [Большая Картинка]
- # Для графа, изображенного на рисунке найти прямые транзитивные замыкания для вершин х3 и х4 [Большая Картинка]
- # Для графа, изображенного на рисунке найти прямые транзитивные замыкания для вершин [Большая Картинка]
- # Для графа, изображенного на рисунке найти обратные транзитивные замыкания для вершин [Большая Картинка]
- # Для графа, изображенного на рисунке найти обратные транзитивные замыкания для вершин [Большая Картинка]
- # Для графа, изображенного на рисунке найти обратные транзитивные замыкания для вершин [Большая Картинка]
- # Для графа, представленного на рисунке 1 построить матрицу достижимости [Большая Картинка] аX1X2X3X4X5X111111R=X200111X300110X400010X500011 бX1X2X3X4X5X111111R=X200111X300010X400000X500010вX1X2X3X4X5X111111R=X201111X300110X400010X500011
- # Какая из представленных матриц достижимости соответствует графу на рисунке 1? аX1X2X3X4X5X6X1000111R=X2101111X3100111X4100011X5100101X6100110 бX1X2X3X4X5X6X1100111R=X2111111X3101111X4100111X5100111X6100111вX1X2X3X4X5X6X1111111R=X2010000X3011000X4111111X5111111X6111111 [Большая Картинка]
- # Для графа, представленного на рисунке построить матрицу достижимости и определить для какой из вершин графа достижимо наибольшее число вершин. [Большая Картинка]
- # Для графа, приведенного на рисунке 1, найти матрицу контрдостижимости. [Большая Картинка] аX1X2X3X4X5X110000Q=X211000X311100X410111X511001 бX1X2X3X4X5X110000Q=X211000X311100X411111X511001вX1X2X3X4X5X110000Q=X211000X311100X411110X511001
- # Какая из представленных матриц контрдостижимости соответствует графу на рис. 1? аX1X2X3X4X5X6X1000111Q=X2101111X3100111X4100011X5100101X6100110 бX1X2X3X4X5X6X1100111Q=X2111111X3101111X4100111X5100111X6100111вX1X2X3X4X5X6X1111111Q=X2010000X3011000X4111111X5111111X6111111 [Большая Картинка]
- # Для графа, представленного на рисунке построить матрицу контрдостижимости и определить какая из вершин достижима для наибольшего числа вершин графа. [Большая Картинка]
- # Для графа, представленного на рисунке, найти: вершины, входящие в путь между вершинами [Большая Картинка]
- # Для графа, представленного на рисунке, найти: вершины, входящие в путь между вершинами [Большая Картинка]
- # Для графа, представленного на рисунке, найти: вершины, входящие в путь между вершинами [Большая Картинка]
- # Для графа, данного на рисунке найти между какими вершинами наибольшее число путей длиной 2. [Большая Картинка]
- # Для графа, данного на рисунке найти количество путей длиной 2 между всеми вершинами графа. [Большая Картинка]
- # Для графа, данного на рисунке определить между какой парой вершин большее количество путей длиной 2: [Большая Картинка]
- # Для графа, данного на рисунке найти между какими вершинами наибольшее число путей длиной 3. [Большая Картинка]
- # Для графа, данного на рисунке найти количество путей длиной 3 между всеми вершинами графа. [Большая Картинка]
- # Для графа, данного на рисунке определить между какой парой вершин большее количество путей длиной 2: [Большая Картинка]
- # Для графа, данного на рисунке найти количество путей длиной 4 между всеми вершинами графа [Большая Картинка]
- # Для графа, данного на рисунке найти между какими вершинами наибольшее число путей длиной 4. [Большая Картинка]
- # Для графа, данного на рисунке определить между какой парой вершин большее количество путей длиной 2: [Большая Картинка]
- # Какие из приведенных на рисунке графов являются полными? [Большая Картинка]
- # Какие из приведенных на рисунке графов являются полными? [Большая Картинка]
- # Какие из приведенных на рисунке графов являются полными? [Большая Картинка]
- # По матрицам смежности, приведенным ниже определить какие из графов являются полными. а1111001100011111b0101000100101010c1011110101111111d0000100011001110
- # По матрицам смежности определить какие из графов являются полными. а1111001010001100001011110b0101000011110000010110100c1101111101011111011111111d0000010000110001110011110
- # По матрицам смежности определить какие из графов являются полными. а1111001100010000b0101000100101010c1010110101110111d1010110001101010
- # Какие из приведенных на рисунке графов являются симметрическими? [Большая Картинка]
- # Какие из приведенных на рисунке графов являются симметрическими? [Большая Картинка]
- # Какие из приведенных на рисунке графов являются симметрическими? [Большая Картинка]
- # Какие из приведенных на рисунке графов являются антисимметрическими? [Большая Картинка]
- # Какие из приведенных на рисунке графов являются полными симметрическими? [Большая Картинка]
- # Какие из приведенных на рисунке графов являются антисимметрическими? [Большая Картинка]
- # Какие из приведенных на рисунке графов являются антисимметрическими? [Большая Картинка]
- # Какие из приведенных на рисунке графов являются полными симметрическими? [Большая Картинка]
- # Какие из приведенных на рисунке графов являются полными антисимметрическими? [Большая Картинка]
- # Является ли граф на рисунке двудольным [Большая Картинка]
- # Является ли граф на рисунке двудольным? [Большая Картинка]
- # Является ли граф на рисунке двудольным? [Большая Картинка]
- # Является ли граф, представленный на рисунке, планарным? [Большая Картинка]
- # Является ли граф, представленный на рисунке, планарным? [Большая Картинка]
- # Является ли граф, представленный на рисунке, планарным? [Большая Картинка]
- # Какие из приведенных на рисунке графов являются деревьями? [Большая Картинка]
- # Дан граф на рисунке 1. Какие из приведенных на рисунке 2 графов являются его подграфами? [Большая Картинка] [Большая Картинка]
- # Дан граф на рисунке 1. Какие из приведенных на рисунке 2 графов являются его остовными подграфами? [Большая Картинка] [Большая Картинка]
- # Дан граф на риунке 1. Какой из приведенных на рисунке 2 графов является для него порожденным подграфом? [Большая Картинка] [Большая Картинка]
- # Для графа [Большая Картинка] аX1X2X3X4X5X101000X200101X300001X400100X500100bX1X2X3X4X5X101000X200101X300011X400010X500110 cX1X2X3X4X5X101000X200101X300011X400000X500100
- # Для графа G = (X, A) , представленного на рисунке 1, описать матрицей смежности порожденный подграф {х1,х2,х3, ,х5, х7} [Большая Картинка] аX1X2X3X5X7X101000X200101X300001X500100X700100bX1X2X3X5X7X101000X200110X300010X500100X710010 cX1X2X3X5X7X101000X200101X300011X500001X710100
- # Для графа G = (X, A) , представленного на рисунке 1, описать матрицей смежности порожденный подграф {х2,х3, х4,х5, х6} [Большая Картинка] аX2X3X4X5X6X201010X300110X400001X501000X600100bX2X3X4X5X6X201000X300110X400100X500010X610010 cX2X3X4X5X6X201000X300101X400001X501001X610100
- # Для графа [Большая Картинка]
- # Для графа [Большая Картинка]
- # Для графа [Большая Картинка]
- # Найти максимальный сильно связанный подграф, включающий вершину C, для графа, матрица смежности которого представлена ниже ABCDEFGKA11001000B00101100C00101000D00000001E00000100F10000010G00000001K00010000
- # Найти максимальный сильно связанный подграф, включающий вершину Е, для графа, матрица смежности которого представлена ниже ABCDEFGKA11001000B00101100C00101000D00000001E00000100F10000010G00000001K00010000
- # Найти максимальный сильно связанный подграф, включающий вершину F, для графа, матрица смежности которого представлена ниже ABCDEFGKA11001000B00101100C00101000D00000001E00000100F10000010G00000001K00010000
- # Какие из приведенных на рисунке графов являются сильно связными? [Большая Картинка]
- # Какие из приведенных на рисунке графов являются односторонне связными? [Большая Картинка]
- # Какие из приведенных на рисунке графов являются слабо связными? [Большая Картинка]
- # Выделить в графе на рисунке с сильную компоненту, содержащую максимальное число элементов. [Большая Картинка]
- # Выделить в графе на рисунке e сильную компоненту, содержащую максимальное число элементов. [Большая Картинка]
- # Выделить в графе на рисунке f сильную компоненту, содержащую максимальное число элементов. [Большая Картинка]
- # Выделить в графе на рисунке b одностороннюю компоненту, содержащую максимальное число элементов. [Большая Картинка]
- # Выделить в графе на рисунке а одностороннюю компоненту, содержащую максимальное число элементов. [Большая Картинка]
- # Выделить в графе на рисунке f одностороннюю компоненту, содержащую максимальное число элементов. [Большая Картинка]
- # Для графа на рисунке найти сильную компоненту, содержащую элемент [Большая Картинка]
- # Для графа на рисунке найти сильную компоненту, содержащую элемент [Большая Картинка]
- # Для графа на рисунке найти сильную компоненту, содержащую элемент [Большая Картинка]
- # Методом Мальгранжа разбить граф, представленный ниже матрицей смежности, на подграфы X1X2X3X4X5X6X7X8X111010000X210100010X300001000X400100000X500010000X600000000X701000101X810000000
- # Методом Мальгранжа разбить граф, представленный ниже матрицей смежности, на подграфы X1X2X3X4X5X6X7X11101000X21010010X30000100X40010000X50001000X60100001X71000000
- # Методом Мальгранжа разбить граф, представленный на рисунке, на подграфы [Большая Картинка]
- # Методом Мальгранжа разбить граф, представленный на рисунке, на максимальные сильно связные подграфы [Большая Картинка]
- # Методом Мальгранжа разбить граф, представленный матрицей смежности, на максимальные сильно связные подграфыX1X2X3X4X5X6X7X8X101000001X210101000X300011000X400000100X500100010X600010000X710001100X800000010
- # Методом Мальгранжа разбить граф, представленный на рисунке, на максимальные сильно связные подграфы [Большая Картинка]
- # Метод разбиения графа по матрицам [Большая Картинка]
- # Метод разбиения графа по матрицам R и Q рассмотреть на примере графа, изображенного матрицей смежностиX1X2X3X4X5X6X7X8X111100000X210100010X300001000X400110000X500011000X600000100X701000101X810101000
- # Метод разбиения графа по матрицам R и Q рассмотреть на примере графа, изображенного матрицей смежностиX1X2X3X4X5X6X7X8X111010000X210101010X300001000X400110000X500011000X600000100X701100101X810000001
- # Построить все возможные пути длиной 2 в графе, изображенном на рисунке для вершин [Большая Картинка]
- # Построить все возможные пути длиной 2 в графе, изображенном на рисунке для вершин [Большая Картинка]
- # Построить все возможные пути длиной 2 в графе, изображенном на рисунке для вершин [Большая Картинка]
- # Построить орцепи максимальной длины из вершин [Большая Картинка]
- # Построить орцепи максимальной длины из вершин [Большая Картинка]
- # Построить орцепи максимальной длины из вершин [Большая Картинка]
- # Построить простые орцепи максимальной длины из вершин [Большая Картинка]
- # Построить простые орцепи максимальной длины из вершин [Большая Картинка]
- # Построить простые орцепи максимальной длины из вершин [Большая Картинка]
- # [Большая Картинка] a) (A, B), (B, C), (C, G), (G, F) b) (A, K), (K, H), (H, F) c) (A, C), (C, E), (E, D), (D, C), (C, H), (H, F) d) (A, K), (K, H), (H, C), (C, K), (K, H), (H, F) Найти среди них цепи
- # [Большая Картинка] a) (A, B), (B, C), (C, G), (G, F) b) (A, K), (K, H), (H, F) c) (A, C), (C, E), (E, D), (D, C), (C, H), (H, F) d) (A, K), (K, H), (H, C), (C, K), (K, H), (H, F) Найти среди них простые цепи
- # [Большая Картинка] a) (A, B), (B, C), (C, F) b) (A, K), (K, H), (H, F) c) (A, K), (K, H), (H, C), (C, K), (K, H), (H, F) Найти среди них цепи
- # [Большая Картинка] Скорость оборота капитала n -го пути судна найдем как суммарную выгоду пути, деленную на суммарное время, т. е. vn=∑ ai/ ∑ bi A → B → C → D → E → A A → B → C → E → D → A. A → D → B → C → E → A. A → C → E → D → B → A.
- # [Большая Картинка]vn=∑ ai / ∑ bi
- # На рисунке дан граф со взвешенными дугами, который представляет сеть допустимых маршрутов для некоторого судна. Каждая дуга имеет пометку [Большая Картинка]vn=∑ ai/ ∑ bi
- # [Большая Картинка] Для графа, представленного на рисунке даны замкнутые пути: М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) Какие из этих путей являются контурами?
- # [Большая Картинка] Для графа, представленного на рисунке даны замкнутые пути: М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) Какие из этих путей являются гамильтоновыми контурами?
- # [Большая Картинка] Для графа, представленного на рисунке даны замкнутые пути: М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) Какие из этих путей являются эйлеровыми контурами?
- # Для графа, представленного на рисунке построить гамильтоновы и эйлеровы циклы. [Большая Картинка]
- # Для графа, представленного на рисунке построить гамильтоновы и эйлеровы циклы. [Большая Картинка]
- # Для графа, представленного на рисунке построить гамильтонов цикл и эйлеров путь. [Большая Картинка]
- # Обновление пометок происходит по формуле:
- # Для чего использую алгоритм Дейкстра?
- # Обновление пометок на каждой итерации алгоритма Дейкстры происходит
- # Для нахождения кратчайшего пути от s к хi, предшествующую вершину xi* можно найти как одну из вершин, для которой
- # Если с помощью алгоритма Дейкстры требуется найти кратчайшие пути от вершины x3 до других вершин графа, то в первой итерации ей присваивается пометка со значением ...
- # Значение постоянной метки показывает
- # Найти кратчайший путь от вершины 1 к вершине 5 графа, представленного на рисунке [Большая Картинка]
- # Найти кратчайший путь от вершины 1 к вершине 6 графа, представленного на рисунке [Большая Картинка]
- # Найти кратчайший путь от вершины 1 к вершине 8 графа, представленного на рисунке [Большая Картинка]
- # Найти кратчайший путь от вершины [Большая Картинка]
- # Найти кратчайший путь от вершины [Большая Картинка]
- # Найти кратчайший путь от вершины [Большая Картинка]
- # Для графа, представленного на рисунке 1а, построить базу относительно вершины [Большая Картинка] [Большая Картинка]
- # Для графа, представленного на рисунке 1а, построить базу относительно вершины [Большая Картинка] [Большая Картинка]
- # Для графа, представленного на рисунке 1а, построить базу относительно вершины [Большая Картинка] [Большая Картинка]