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

Количество вопросов - 173

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

Выполнить операцию пересечения G1 G2 для графов, показанных на рисунке 1

Методом Мальгранжа разбить граф, представленный матрицей смежности, на максимальные сильно связные подграфы
X1X2X3X4X5X6X7X8
X101000001
X210101000
X300011000
X400000100
X500100010
X600010000
X710001100
X800000010

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

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

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

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

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

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

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

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

Для графа, приведенного на рисунке 1, найти матрицу контрдостижимости.
а
X1X2X3X4X5
X110000
Q=X211000
X311100
X410111
X511001
б
X1X2X3X4X5
X110000
Q=X211000
X311100
X411111
X511001
в
X1X2X3X4X5
X110000
Q=X211000
X311100
X411110
X511001

Найти максимальный сильно связанный подграф, включающий вершину C, для графа, матрица смежности которого представлена ниже
ABCDEFGK
A11001000
B00101100
C00101000
D00000001
E00000100
F10000010
G00000001
K00010000

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

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

В графе G6 , показанном на рис. 1 удалить вершину х1. Результат представлен ниже в матричном виде
а
X2X3
X201
X310
б
X1X2
X101
X210
в
X1X3
X101
X310

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

Методом Мальгранжа разбить граф, представленный ниже матрицей смежности, на подграфы
X1X2X3X4X5X6X7
X11101000
X21010010
X30000100
X40010000
X50001000
X60100001
X71000000

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

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

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

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

Для графа, представленного на рисунке 1а, построить базу относительно вершины х7.

На рисунке дан граф со взвешенными дугами, который представляет сеть допустимых маршрутов для некоторого судна. Каждая дуга имеет пометку(a, b), причем а равно выгоде, получаемой при обслуживании этого маршрута, а b – времени обслуживания маршрута. Найти, какой из перечисленных путей наиболее выгодный (в терминах скорости оборота капитала) путь судна. vn=∑ ai / ∑ bi

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

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

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

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

Для графа, изображенного на рисунке найти прямые транзитивные замыкания для вершин х1и х2,

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

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

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

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

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

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

Для графа, представленного на рисунке, данаматрица инциденций. Верно ли представлен граф?
матрица инциденций
a1a2a3a4a5a6a7
X1011000-1
X20-10-1100
X30000-1-10
X400-11011

По матрице смежности, данной ниже подсчитать полустепень исхода второй вершины do2)
101100
010101
000101
001001
100000
010001

Соответствует ли матрица инциденций матрице смежности (обе матрицы представлены ниже):
матрица инциденций
a1a2a3a4a5a6a7a8a9a10
X11-110101000
X201-11000000
X3000-1-110100
X4000000-1-110
X500000000-1-1
X600000-10001
матрица смежности
X1X2X3X4X5X6
X1111100
X2101000
X3000101
X4000010
X5000000
X6000010

Выполнить операцию нахождения кольцевой суммы G1 G2 для графов, показанных на рисунке 1

Выполнить операцию объединения G1 ∪ G2 для графов, представленных матрицами смежности в таблице 1
Матрица смежности G1
X1X2X3X4X5
X100001
X210010
X300000
X400100
X501010
Матрица смежности G2
X1X2X3X4X5
X100001
X210101
X300000
X401101
X500000
a
X1X2X3X4X5
X100001
X210000
X300000
X400100
X500000
б
X1X2X3X4X5
X100000
X200111
X300000
X401001
X501010
в
X1X2X3X4X5
X100001
X210111
X300000
X401101
X501010

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

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

В графе G6 , показанном на рис. 1 удалить дугу 32). Результат представлен в матричном виде ниже
а
X1X2X3
X111
X211
X31
б
X1X2X3
X11
X211
X311
в
X1X2X3
X11
X211
X311

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

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

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

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

Для графа, представленного на рисунке 1 построить матрицу достижимости R
а
X1X2X3X4X5
X111111
R=X200111
X300110
X400010
X500011
б
X1X2X3X4X5
X111111
R=X200111
X300010
X400000
X500010
в
X1X2X3X4X5
X111111
R=X201111
X300110
X400010
X500011

Какая из представленных матриц контрдостижимости соответствует графу на рис. 1?
а
X1X2X3X4X5X6
X1000111
Q=X2101111
X3100111
X4100011
X5100101
X6100110
б
X1X2X3X4X5X6
X1100111
Q=X2111111
X3101111
X4100111
X5100111
X6100111
в
X1X2X3X4X5X6
X1111111
Q=X2010000
X3011000
X4111111
X5111111
X6111111

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

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

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

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

По матрицам смежности определить какие из графов являются полными.
а
1111
0011
0001
0000
b
0101
0001
0010
1010
c
1010
1101
0111
0111
d
1010
1100
0110
1010

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

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

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

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

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

Для графа G = (X, A), представленного на рисунке 1, описать матрицей смежности порожденный подграф 12345}
а
X1X2X3X4X5
X101000
X200101
X300001
X400100
X500100
b
X1X2X3X4X5
X101000
X200101
X300011
X400010
X500110
c
X1X2X3X4X5
X101000
X200101
X300011
X400000
X500100

Перечислите дуги, являющиеся петлями в графе на рисунке?

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

По матрице смежности, данной ниже подсчитать количество петель графа.
101100
010101
000101
001001
100000
010001

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

Для графа, представленного на рисунке 1а, построить базу относительно вершины х3.

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

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

На рисунке дан граф со взвешенными дугами, который представляет сеть допустимых маршрутов для некоторого судна. Каждая дуга имеет пометку(a, b), причем а равно выгоде, получаемой при обслуживании этого маршрута, а b – времени обслуживания маршрута. Найти, какой из перечисленных путей наиболее выгодный (в терминах скорости оборота капитала) путь судна.

Скорость оборота капитала 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.
  • Для графа на рисунке даны маршруты из вершины 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)

    Найти среди них простые цепи

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

    Метод разбиения графа по матрицам R и Q рассмотреть на примере графа, изображенного матрицей смежности
    X1X2X3X4X5X6X7X8
    X111010000
    X210101010
    X300001000
    X400110000
    X500011000
    X600000100
    X701100101
    X810000001

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

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

    Для графа G = (X, A) , представленного на рисунке, описать явно остовный подграф(X, A’) , где xi,xj ∈X тогда и только тогда, когда i+j четно

    Для графа G = (X, A) , представленного на рисунке 1, описать матрицей смежности порожденный подграф 23, х45, х6}
    а
    X2X3X4X5X6
    X201010
    X300110
    X400001
    X501000
    X600100
    b
    X2X3X4X5X6
    X201000
    X300110
    X400100
    X500010
    X610010
    c
    X2X3X4X5X6
    X201000
    X300101
    X400001
    X501001
    X610100

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

    Является ли граф на рисунке двудольным?

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

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

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

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

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

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

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

    Выполнить операцию нахождения кольцевой суммы G1 ⊕ G2 для графов, представленных матрицами смежности в таблице 1
    Матрица смежности G1
    X1X2X3X4X5
    X100001
    X210010
    X300000
    X400100
    X501010
    Матрица смежности G2
    X1X2X3X4X5
    X100001
    X210101
    X300000
    X401101
    X500000
    a
    X1X2X3X4X5
    X100001
    X210000
    X300000
    X400100
    X500000
    б
    X1X2X3X4X5
    X100000
    X200111
    X300000
    X401001
    X501010
    в
    X1X2X3X4X5
    X100001
    X210111
    X300000
    X401101
    X501010

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

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

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

    Какая из представленных матриц достижимости соответствует графу на рисунке 1?
    а
    X1X2X3X4X5X6
    X1000111
    R=X2101111
    X3100111
    X4100011
    X5100101
    X6100110
    б
    X1X2X3X4X5X6
    X1100111
    R=X2111111
    X3101111
    X4100111
    X5100111
    X6100111
    в
    X1X2X3X4X5X6
    X1111111
    R=X2010000
    X3011000
    X4111111
    X5111111
    X6111111

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

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

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

    В графе G6 , показанном на рис. 1 удалить дугу 12). Результат представлен ниже в матричном виде
    а
    X1X2X3
    X111
    X211
    X31
    б
    X1X2X3
    X11
    X211
    X311
    в
    X1X2X3
    X11
    X211
    X311

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

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

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

    Для графа, изображенного на рисунке найти обратные транзитивные замыкания для вершин х1 и х2,

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

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

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

    По матрицам смежности, приведенным ниже определить какие из графов являются полными.
    а
    1111
    0011
    0001
    1111
    b
    0101
    0001
    0010
    1010
    c
    1011
    1101
    0111
    1111
    d
    0000
    1000
    1100
    1110

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

    По матрице смежности, данной ниже подсчитать полустепень захода второй вершины dt2)
    101100
    010101
    000101
    001001
    100000
    010001

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

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

    Для графа, представленного на рисунке даны замкнутые пути:

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

    Какие из этих путей являются контурами?

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

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

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

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

    Для графа G = (X, A) , представленного на рисунке, описать явно остовный подграф(X, A’) , где xi,xj ∈ A' тогда и только тогда, когда i+j < 10

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

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

    Метод разбиения графа по матрицам R и Q рассмотреть на примере графа, изображенного матрицей смежности
    X1X2X3X4X5X6X7X8
    X111100000
    X210100010
    X300001000
    X400110000
    X500011000
    X600000100
    X701000101
    X810101000

    Для графа, представленного на рисунке 1а, построить базу относительно вершины х1.

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

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

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

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

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

    Для графа, представленного на рисунке даны замкнутые пути:

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

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

    Для графа на рисунке даны маршруты из вершины 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 и D графа, изображенного на рисунке

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

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

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

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

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

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

    Для графа G = (X, A) , представленного на рисунке, описать явно остовный подграф(X, A’) , где xi,xj ∈ A' тогда и только тогда, когда i+j нечетно

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

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

    Найти максимальный сильно связанный подграф, включающий вершину F, для графа, матрица смежности которого представлена ниже
    ABCDEFGK
    A11001000
    B00101100
    C00101000
    D00000001
    E00000100
    F10000010
    G00000001
    K00010000

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

    Даны матрицы смежности и матрица инцидентности. Соответствуют ли они графу на рисунке?
    матрица смежности
    X1X2X3X4
    X11100
    X20011
    X30000
    X41110
    матрица инциденций
    a1a2a3a4a5a6a7
    X1011000-1
    X20-10-1100
    X30000-1-10
    X400-11011

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

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

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

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

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

    Выполнить операцию пересечения G1 ∩ G2 для графов, представленных матрицами смежности в таблице 1
    Матрица смежности G1
    X1X2X3X4X5
    X100001
    X210010
    X300000
    X400100
    X501010
    Матрица смежности G2
    X1X2X3X4X5
    X100001
    X210101
    X300000
    X401101
    X500000
    a
    X1X2X3X4X5
    X100001
    X210000
    X300000
    X400100
    X500000
    б
    X1X2X3X4X5
    X100000
    X200111
    X300000
    X401001
    X501010
    в
    X1X2X3X4X5
    X100001
    X210111
    X300000
    X401101
    X501010

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

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

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

    Является ли граф на рисунке двудольным?

    Для графа G = (X, A) , представленного на рисунке 1, описать матрицей смежности порожденный подграф 123, ,х5, х7}
    а
    X1X2X3X5X7
    X101000
    X200101
    X300001
    X500100
    X700100
    b
    X1X2X3X5X7
    X101000
    X200110
    X300010
    X500100
    X710010
    c
    X1X2X3X5X7
    X101000
    X200101
    X300011
    X500001
    X710100

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

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

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

    Методом Мальгранжа разбить граф, представленный ниже матрицей смежности, на подграфы
    X1X2X3X4X5X6X7X8
    X111010000
    X210100010
    X300001000
    X400100000
    X500010000
    X600000000
    X701000101
    X810000000

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

    В графе G6 , показанном на рис. 1 удалить дугу 13). Результат представлен ниже в матричном виде
    а
    X1X2X3
    X111
    X211
    X31
    б
    X1X2X3
    X11
    X211
    X311
    в
    X1X2X3
    X11
    X211
    X311

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

    Найти среди них цепи

    В графе G6 , показанном на рис. 1 удалить вершину х2. Результат представлен в матричном виде ниже
    а
    X2X3
    X201
    X210
    б
    X1X2
    X101
    X210
    в
    X1X3
    X101
    X310

    По матрицам смежности определить какие из графов являются полными.
    а
    11110
    01010
    00110
    00010
    11110
    b
    01010
    00011
    11000
    00101
    10100
    c
    11011
    11101
    01111
    10111
    11111
    d
    00000
    10000
    11000
    11100
    11110

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

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

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

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

    Найдите полустепени исхода и захода для вершины х2 графа

    Выполнить операцию объединения G1 G2 для графов, показанных на рисунке 1

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

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

    На рисунке дан граф со взвешенными дугами, который представляет сеть допустимых маршрутов для некоторого судна. Каждая дуга имеет пометку(a, b), причем а равно выгоде, получаемой при обслуживании этого маршрута, а b – времени обслуживания маршрута. Найти, какой из перечисленных путей наиболее выгодный (в терминах скорости оборота капитала) путь судна. vn=∑ ai/ ∑ bi

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

    В графе G6 , показанном на рис. 1 удалить вершину х3. Результат представлен в матричном виде ниже
    а
    X2X3
    X201
    X210
    б
    X1X2
    X101
    X210
    в
    X1X3
    X101
    X310

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

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

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

    Найти максимальный сильно связанный подграф, включающий вершину Е, для графа, матрица смежности которого представлена ниже
    ABCDEFGK
    A11001000
    B00101100
    C00101000
    D00000001
    E00000100
    F10000010
    G00000001
    K00010000

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

    Для графа, представленного на рисунке даны замкнутые пути:

    М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 к вершине 5 графа, представленного на рисунке