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



Авторы специализируются на тестах по любым дисциплинам! Средний балл по тестам 4,6.
 
Любые вопросы по дистанционному обучению. Тесты, письменные работы, сессия под ключ.
 
Известный интернет сайт, помощь по любым учебным вопросам - от теста до дипломной работы. Личный менеджер.
 
Крупная биржа студенческих работ. Закажи напрямую у преподавателя. Низкие цены, стена заказов.
 
Биржа студенческих работ. Потребуется самостоятельная выгрузка работ.
 

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

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