Введение в теорию графов

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

X1 X2 X3 X4 X5 X6 X7 X8 X1 11010000 X2 10100010 X3 00001000 X4 00100000 X5 00010000 X6 00000000 X7 01000101 X8 10000000

• G1={x1, x2 }, G2 = { х3, х4, х5 }, G3 ={х6, х7, х8 }
• (Правильный ответ) G1={x1, x2 , х7, х8 }, G2 = { х3, х4, х5 }, G3 ={х6}
• G1={x1, x2 , х7, х8 }, G2 = { х3, х4 }, G3 ={ х5 ,х6}

Какого типа граф изображен на рисунке?

• граф
• (Правильный ответ) орграф
• смешанный граф

Для графа, представленного на рисунке, дана матрица смежности. Верно ли представлен граф?

матрица смежности X1 X2 X3 X4 X1 1100 X2 0011 X3 0000 X4 1110

• (Правильный ответ) верно
• не верно

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

а 1111001100010000 b 0101000100101010 c 1010110101110111 d 1010110001101010

• a, с
• (Правильный ответ) a
• а, c, d

Выделить в графе на рисунке b одностороннюю компоненту, содержащую максимальное число элементов.

• < х2, х3, х5 >
• < х1, х2, х5 >
• (Правильный ответ) < х1, х2, х3, х5 >

Для графа G1, показанном на рисунке 1, выполнить операцию отождествления двух вершин (х1,х2). Верно ли результат представлен матрицей смежности ниже?

X(1,2) X3 X4 X5 X(1,2) 1 11 X3   X4 1 X5 1 1

• (Правильный ответ) верно
• неверно

В графе G6 , показанном на рис. 1 удалить вершину х1. Результат представлен ниже в матричном виде

а X2 X3 X2 01 X3 10 б X1 X2 X1 01 X2 10 в X1 X3 X1 01 X3 10

• верно б
• верно в
• (Правильный ответ) верно а

Для графа, представленного на рисунке, найти: вершины, входящие в путь между вершинами х1 и х7.

• {х1, х2, х4, х7}
• {х1, х2, х3, х4 }
• (Правильный ответ) { х1, х2, х3, х4, х7}

Для графа, данного на рисунке определить между какой парой вершин большее количество путей длиной 2: F и C или E и C

• (Правильный ответ) одинаковое количество
• между E и C
• между F и C

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

A B C D E F G K A 11001000 B 00101100 C 00101000 D 00000001 E 00000100 F 10000010 G 00000001 K 00010000

• (Правильный ответ) Gмсс={A, B, C, E, F}
• Gмсс={ B, C, E, F}
• Gмсс={A, B, E, F}

Найти кратчайший путь от вершины x1 к вершине x10 графа, представленного на рисунке А, матрица расстояний между вершинами дана на рис. Б

• 16
• (Правильный ответ) 18
• 15

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

• 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) ]

Для графа G1, показанном на рисунке 1, выполнить операцию отождествления двух вершин (х3,х4). Верно ли результат представлен на рис. 2а?

• (Правильный ответ) верно
• неверно

Какие из приведенных на рисунке графов являются односторонне связными?

• d, e
• (Правильный ответ) e
• a, d

Какие вершины инцидентны дуге f в графе на рисунке?

• 2
• (Правильный ответ) 2, 3
• 1, 2, 3

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

• (Правильный ответ) G1={x1, x2 , х3, х5 , х7, х8 }, G2 ={ х4 , х6}
• G1={x1, x2 }, G2 = { х3, х4, х5 }, G3 ={х6, х4, х7, х8 }
• G1={x1, x2 , х8 }, G2 = { х3, , х7, х5 }, G3 ={х6 , х4}

Для графа на рисунке даны маршруты из вершины A в вершину 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) Найти среди них цепи

• a
• (Правильный ответ) a, b
• a, b, c

Для графа G = (X, A), представленного на рисунке 1, описать матрицей смежности порожденный подграф {х1,х2,х3,х4,х5}

а X1 X2 X3 X4 X5 X1 01000 X2 00101 X3 00001 X4 00100 X5 00100 b X1 X2 X3 X4 X5 X1 01000 X2 00101 X3 00011 X4 00010 X5 00110 c X1 X2 X3 X4 X5 X1 01000 X2 00101 X3 00011 X4 00000 X5 00100

• b
• а
• (Правильный ответ) c

Какие из приведенных на рисунке графов являются полными антисимметрическими?

• все
• (Правильный ответ) а
• a, d

Найти обратные отображения для вершин х5и х6графа, показанного на рисунке

• Г–1 (х5) = { х6, х4}, Г–1 (х6) = { х3 ,х6 }
• (Правильный ответ) Г–1 (х5) = { х6, х4}, Г–1 (х6) = { х3},
• Г–1 (х5) = { х6, х4}, Г–1 (х6) = { х6, х4}

Какая из представленных матриц достижимости соответствует графу на рисунке 1?

а   X1 X2 X3 X4 X5 X6 X1 000111R= X2 101111 X3 100111 X4 100011 X5 100101 X6 100110 б   X1 X2 X3 X4 X5 X6 X1 100111R= X2 111111 X3 101111 X4 100111 X5 100111 X6 100111 в   X1 X2 X3 X4 X5 X6 X1 111111R= X2 010000 X3 011000 X4 111111 X5 111111 X6 111111

• а
• (Правильный ответ) б
• в

Для графа, данного на рисунке найти количество путей длиной 3 между всеми вершинами графа.

• 13
• 9
• (Правильный ответ) 11

Какие дуги инцидентны вершине 2 в графе на рисунке?

• e, c, f
• c
• (Правильный ответ) b, c, f

Является ли граф, изображенный на рисунке орграфом?

• это смешанный граф
• не является
• (Правильный ответ) является

Для графа, представленного на рисунке построить гамильтоновы и эйлеровы циклы.

• эйлеров цикл –(F, C), (C, A), (A, F), (F, E), (E, D), (D, C), (C, B), (B, D) или (D, C), (C, B), (B, D), (D, E), (E, F), (F, C), (C, A), (A, F)
• гамильтонов цикл отсутствует, эйлеров цикл отсутствует
• (Правильный ответ) гамильтонов цикл :(A, C), (C, B), (B, D), (D, E), (E, F), (F, A); эйлеров цикл отсутствует

Построить орцепи максимальной длины из вершин E и F графа, изображенного на рисунке

• (Правильный ответ) (E, F) ?? (F, D) ?? (D, F) ?? (F, A) ?? (A, B) ?? (B,B) ?? (B, C), (F, D) ?? (D, F) ?? (F, A) ?? (A, B) ?? (B, B) ?? (B, C)
• (E, F) ?? (F, D) ?? (D, F) ?? (F, A) ?? (A, B) ?? (B, C), (F, D) ?? (D, F) ?? (F, A) ?? (A, B) ?? (B, C)
• (E, F) ?? (F, D) ?? (D, F) ?? (F, A) ?? (A, B) ?? (B, C), (F, D) ??

Какие из приведенных на рисунке графов являются антисимметрическими?

• (Правильный ответ) a,b,c
• а, b, d
• a, с

Для графа на рисунке даны маршруты из вершины A в вершину 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, b, c
• a, c
• (Правильный ответ) a, b

В графе G6 , показанном на рис. 1 удалить дугу (х1,х2). Результат представлен ниже в матричном виде

а X1 X2 X3 X1 11 X2 1 1 X3 1 б X1 X2 X3 X1 1 X2 1 1 X3 11 в X1 X2 X3 X1 1 X2 1 1 X3 11

• верно в
• (Правильный ответ) верно б
• верно а

Построить все возможные пути длиной 2 в графе, изображенном на рисунке для вершин A и D.

• A ?? В ?? C, D ?? E ?? F, D ?? F ?? D
• (Правильный ответ) A ?? B ?? B, A ?? В ?? C, D ?? E ?? F, D ?? F ?? D, D ?? F ?? A, D ?? E ?? B
• A ?? В ?? C, D ?? E ?? F

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

X1 X2 X3 X4 X5 X6 X7 X8 X1 11010000 X2 10101010 X3 00001000 X4 00110000 X5 00011000 X6 00000100 X7 01100101 X8 10000001

• (Правильный ответ) 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 }

Найдите полустепени исхода и захода для вершины х1 (вершина обзначена на рисунке цифрой 1) графа

• (Правильный ответ) d0(х1)=3, dt(х1)=2
• d0(х1)=2, dt(х1)=2
• d0(х1)=2, dt(х1)=1

Для графа G2, показанном на рисунке 1, выполнить операцию стягивания двух вершин (х3,х4). Верно ли результат представлен матрицей смежности ниже?

X1 X2 X(3,4) X5 X1 1 X2 1 11 X(3,4) 1 1 X5  

• неверно
• (Правильный ответ) верно

Найти обратные отображения для вершин х3 и х4 графа, показанного на рисунке

• Г–1 (х3) = {х2, х3 }, Г–1 (х4) ={х1, х3 , х4}
• Г-1 (х3) = {х6, х4 }, Г–1 (х4) ={х1, х3 }
• (Правильный ответ) Г–1 (х3) = {х1, х2 }, Г–1 (х4) ={х1, х3 , х4}

Какие из приведенных на рисунке графов являются сильно связными?

• (Правильный ответ) a, d
• d
• a, d, e

Для графа на рисунке найти сильную компоненту, содержащую элемент х4

• G2 = { х4,х3}
• (Правильный ответ) G2 = { х4, х6}
• G2 = { х4, х3,х6, х7}

Какие из приведенных на рисунке графов являются антисимметрическими?

• а, b, d
• b
• (Правильный ответ) a, с

Найти кратчайший путь от вершины 1 к вершине 5 графа, представленного на рисунке

• 12
• 16
• (Правильный ответ) 15

Для графа, изображенного на рисунке, дано описание с помощью отображений. G = (X, Г) , где X = {хi}, i = 1, 2, 3, 4 – множество вершин, Г(х1)= , Г(х2) ={ х1, х4 }, Г(х3) = { х1, х3 }, Г(х4) = { х1 } – отображения. Верно ли оно?

• не верно
• (Правильный ответ) верно

Для графа G2, показанном на рисунке 1, выполнить операцию стягивания двух вершин (х1,х2). Верно ли результат представлен матрицей смежности ниже?

X(1,2) X3 X4 X5 X(1,2) 1 1 X3   X4 11 1 X5  

• (Правильный ответ) верно
• неверно

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

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

Для графа на рисунке найти сильную компоненту, содержащую элемент х5

• (Правильный ответ) G2 = { х3, х5}
• G2 = { х3, х4, х5}
• G2 = { х2, х3,х5}

Построить все возможные пути длиной 2 в графе, изображенном на рисунке для вер­шин E и B

• (Правильный ответ) E ?? F ?? A, E ?? B ?? B, E ?? B ?? C, E ?? F ?? D, B ?? В ?? C
• E ?? F ?? A, E ?? B ?? C, E ?? F ?? D
• E ?? F ?? A, E ?? B ?? C, E ?? F ?? D, B ?? В ?? C

В графе G6 , показанном на рис. 1 удалить дугу (х1,х3). Результат представлен ниже в матричном виде

а X1 X2 X3 X1 11 X2 1 1 X3 1 б X1 X2 X3 X1 1 X2 1 1 X3 11 в X1 X2 X3 X1 1 X2 1 1 X3 11

• верно б
• верно а
• (Правильный ответ) верно в

Для графа G1, показанном на рисунке a, выполнить операцию стягивания двух вершин (х1,х2). Верно ли результат представлен графом на рисунке б?

• неверно
• (Правильный ответ) верно

Построить простые орцепи максимальной длины из вершин F и E графа, изображенного на рисунке

• (E, F) ?? (F, A) ?? (A, B) ?? (B, B) ?? (B, C), (F, A) ?? (A, B) ?? (B, C)
• (E, F) ?? (F, A) ?? (A, B) ?? (B, C), (F, A) ?? (A, B) ?? (B, B) ?? (B, C)
• (Правильный ответ) (E, F) ?? (F, A) ?? (A, B) ?? (B, C), (F, A) ?? (A, B) ?? (B, C)

Является ли граф, представленный на рисунке, планарным?

• (Правильный ответ) да
• нет

Какие дуги являются петлями в графе на рисунке?

• c, a, d, e
• (Правильный ответ) f, c
• f
• a, c

В графе G6 , показанном на рис. 1 удалить дугу (х3,х2). Результат представлен в матричном виде ниже

а X1 X2 X3 X1 11 X2 1 1 X3 1 б X1 X2 X3 X1 1 X2 1 1 X3 11 в X1 X2 X3 X1 1 X2 1 1 X3 11

• верно б
• (Правильный ответ) верно а
• верно в

Какие из приведенных на рисунке графов являются антисимметрическими?

• (Правильный ответ) c
• d
• (Правильный ответ) a
• b

Какие из приведенных на рисунке графов являются симметрическими?

• (Правильный ответ) a, с
• а, c, d
• a

Для графа, данного на рисунке найти количество путей длиной 2 между всеми вершинами графа.

• 8
• 13
• (Правильный ответ) 18

Для графа, изображенного на рисунке, дать описание перечислением.

• (Правильный ответ) G=(Х, А) , где Х = { хi }, i = 1, 2, 3,4 – множество вершин; А = { ai }, i = 1, 2, …, 5 множество дуг, причем А = {(х2, х1), (х4, х1), (х3, х1), (х2, х4), (х3, х3) }
• G4=(Х, А) , где Х = { хi }, i = 1, 2, 3,4 – множество вершин; А = { ai }, i = 1, 2, …, 5 множество дуг, причем А = {(х2, х1), (х4, х1), (х3, х1), (х2, х4) }
• G=(Х, А) , где Х = { хi }, i = 1, 2, 3,4 – множество вершин; А = { ai }, i = 1, 2, …, 5 множество дуг, причем А = {(х2, х1), (х4, х1), (х3, х1), (х2, х4) }