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


Методом Мальгранжа разбить граф, представленный матрицей смежности, на максимальные сильно связные подграфы
| X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 |
---|
X1 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 1 |
---|
X2 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
---|
X3 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
---|
X4 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
---|
X5 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
---|
X6 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
---|
X7 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 |
---|
X8 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
---|
Для графа, представленного на рисунке построить гамильтоновы и эйлеровы циклы.
Какие из приведенных на рисунке графов являются полными?
Для графа, представленного на рисунке, данаматрица смежности. Верно ли представлен граф?
матрица смежности | X1 | X2 | X3 | X4 |
---|
X1 | 1 | 1 | 0 | 0 |
---|
X2 | 0 | 0 | 1 | 1 |
---|
X3 | 0 | 0 | 0 | 0 |
---|
X4 | 1 | 1 | 1 | 0 |
---|
Метод разбиения графа по матрицам R и Q рассмотреть на примере графа, изображенного на рисунке
Найдите полустепени исхода и захода для вершины х3 графа
Является ли граф на рисунке двудольным
Обновление пометок происходит по формуле:
Для графа, данного на рисунке найти между какими вершинами наибольшее число путей длиной 3.
Для графа, приведенного на рисунке 1, найти матрицу контрдостижимости.
а | | X1 | X2 | X3 | X4 | X5 |
---|
| X1 | 1 | 0 | 0 | 0 | 0 |
---|
Q= | X2 | 1 | 1 | 0 | 0 | 0 |
---|
| X3 | 1 | 1 | 1 | 0 | 0 |
---|
| X4 | 1 | 0 | 1 | 1 | 1 |
---|
| X5 | 1 | 1 | 0 | 0 | 1 |
---|
| б | | X1 | X2 | X3 | X4 | X5 |
---|
| X1 | 1 | 0 | 0 | 0 | 0 |
---|
Q= | X2 | 1 | 1 | 0 | 0 | 0 |
---|
| X3 | 1 | 1 | 1 | 0 | 0 |
---|
| X4 | 1 | 1 | 1 | 1 | 1 |
---|
| X5 | 1 | 1 | 0 | 0 | 1 |
---|
| в | | X1 | X2 | X3 | X4 | X5 |
---|
| X1 | 1 | 0 | 0 | 0 | 0 |
---|
Q= | X2 | 1 | 1 | 0 | 0 | 0 |
---|
| X3 | 1 | 1 | 1 | 0 | 0 |
---|
| X4 | 1 | 1 | 1 | 1 | 0 |
---|
| X5 | 1 | 1 | 0 | 0 | 1 |
---|
|
Найти максимальный сильно связанный подграф, включающий вершину C, для графа, матрица смежности которого представлена ниже
| A | B | C | D | E | F | G | K |
---|
A | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
---|
B | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
---|
C | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
---|
D | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
---|
E | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
---|
F | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
---|
G | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
---|
K | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
---|
Дан граф на рисунке 1. Какие из приведенных на рисунке 2 графов являются его подграфами?

Для графа, изображенного на рисунке найти обратные транзитивные замыкания для вершин х5и х6,
В графе G6 , показанном на рис. 1 удалить вершину х1. Результат представлен ниже в матричном виде
Какие из приведенных на рисунке графов являются слабо связными?
Методом Мальгранжа разбить граф, представленный ниже матрицей смежности, на подграфы
| X1 | X2 | X3 | X4 | X5 | X6 | X7 |
---|
X1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 |
---|
X2 | 1 | 0 | 1 | 0 | 0 | 1 | 0 |
---|
X3 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
---|
X4 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
---|
X5 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
---|
X6 | 0 | 1 | 0 | 0 | 0 | 0 | 1 |
---|
X7 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
---|
Найти кратчайший путь от вершины x1 к вершине x10 графа, представленного на рисунке А, матрица расстояний между вершинами дана на рис. Б 
Построить орцепи максимальной длины из вершин A и B графа, изображенного на рисунке 
Построить простые орцепи максимальной длины из вершин A и B графа, изображенного на рисунке 
По матрице инциденций найти полустепени захода для Х2
| a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 | a9 | a10 |
---|
X1 | 2 | -1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
---|
X2 | 0 | 1 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
---|
X3 | 0 | 0 | 0 | -1 | -1 | 1 | 0 | 1 | 0 | 0 |
---|
X4 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 | 1 | 0 |
---|
X5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 |
---|
X6 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 1 |
---|
Для графа, представленного на рисунке 1а, построить базу относительно вершины х7.

На рисунке дан граф со взвешенными дугами, который представляет сеть допустимых маршрутов для некоторого судна. Каждая дуга имеет пометку(a, b), причем а равно выгоде, получаемой при обслуживании этого маршрута, а b – времени обслуживания маршрута. Найти, какой из перечисленных путей наиболее выгодный (в терминах скорости оборота капитала) путь судна.
vn=∑ ai / ∑ bi
Для графа, данного на рисунке найти между какими вершинами наибольшее число путей длиной 4.
Построить все возможные пути длиной 2 в графе, изображенном на рисунке для вершин E и B
Какого типа граф изображен на рисунке?
Является ли граф, представленный на рисунке, планарным? 
Для графа, изображенного на рисунке найти прямые транзитивные замыкания для вершин х1и х2,
Найти прямые отображения для вершин х5 и х6графа, показанного на рисунке 
Является ли граф, изображенный на рисунке орграфом?
Какие вершины инцидентны дуге d в графе на рисунке?
Какие дуги инцидентны вершине 1 в графе на рисунке?
Найдите полустепени исхода и захода для вершины х1 (вершина обзначена на рисунке цифрой 1) графа
Для графа, изображенного на рисунке, дать описание с помощью отображений
Для графа, представленного на рисунке, данаматрица инциденций. Верно ли представлен граф?
матрица инциденций | a1 | a2 | a3 | a4 | a5 | a6 | a7 |
---|
X1 | 0 | 1 | 1 | 0 | 0 | 0 | -1 |
---|
X2 | 0 | -1 | 0 | -1 | 1 | 0 | 0 |
---|
X3 | 0 | 0 | 0 | 0 | -1 | -1 | 0 |
---|
X4 | 0 | 0 | -1 | 1 | 0 | 1 | 1 |
---|
По матрице смежности, данной ниже подсчитать полустепень исхода второй вершины do(х2)
1 | 0 | 1 | 1 | 0 | 0 |
0 | 1 | 0 | 1 | 0 | 1 |
0 | 0 | 0 | 1 | 0 | 1 |
0 | 0 | 1 | 0 | 0 | 1 |
1 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 0 | 0 | 0 | 1 |
Соответствует ли матрица инциденций матрице смежности (обе матрицы представлены ниже):
матрица инциденций | a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 | a9 | a10 |
---|
X1 | 1 | -1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
---|
X2 | 0 | 1 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
---|
X3 | 0 | 0 | 0 | -1 | -1 | 1 | 0 | 1 | 0 | 0 |
---|
X4 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 | 1 | 0 |
---|
X5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 |
---|
X6 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 1 |
---|
матрица смежности | X1 | X2 | X3 | X4 | X5 | X6 |
---|
X1 | 1 | 1 | 1 | 1 | 0 | 0 |
---|
X2 | 1 | 0 | 1 | 0 | 0 | 0 |
---|
X3 | 0 | 0 | 0 | 1 | 0 | 1 |
---|
X4 | 0 | 0 | 0 | 0 | 1 | 0 |
---|
X5 | 0 | 0 | 0 | 0 | 0 | 0 |
---|
X6 | 0 | 0 | 0 | 0 | 1 | 0 |
---|
Выполнить операцию нахождения кольцевой суммы G1 G2 для графов, показанных на рисунке 1


Выполнить операцию объединения G1 ∪ G2 для графов, представленных матрицами смежности в таблице 1
Матрица смежности G1 | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 0 | 0 | 0 | 1 |
---|
X2 | 1 | 0 | 0 | 1 | 0 |
---|
X3 | 0 | 0 | 0 | 0 | 0 |
---|
X4 | 0 | 0 | 1 | 0 | 0 |
---|
X5 | 0 | 1 | 0 | 1 | 0 |
---|
| Матрица смежности G2 | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 0 | 0 | 0 | 1 |
---|
X2 | 1 | 0 | 1 | 0 | 1 |
---|
X3 | 0 | 0 | 0 | 0 | 0 |
---|
X4 | 0 | 1 | 1 | 0 | 1 |
---|
X5 | 0 | 0 | 0 | 0 | 0 |
---|
|
a | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 0 | 0 | 0 | 1 |
---|
X2 | 1 | 0 | 0 | 0 | 0 |
---|
X3 | 0 | 0 | 0 | 0 | 0 |
---|
X4 | 0 | 0 | 1 | 0 | 0 |
---|
X5 | 0 | 0 | 0 | 0 | 0 |
---|
| б | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 0 | 0 | 0 | 0 |
---|
X2 | 0 | 0 | 1 | 1 | 1 |
---|
X3 | 0 | 0 | 0 | 0 | 0 |
---|
X4 | 0 | 1 | 0 | 0 | 1 |
---|
X5 | 0 | 1 | 0 | 1 | 0 |
---|
| в | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 0 | 0 | 0 | 1 |
---|
X2 | 1 | 0 | 1 | 1 | 1 |
---|
X3 | 0 | 0 | 0 | 0 | 0 |
---|
X4 | 0 | 1 | 1 | 0 | 1 |
---|
X5 | 0 | 1 | 0 | 1 | 0 |
---|
|
Для графа G1, показанном на рисунке 1, выполнить операцию отождествления двух вершин (х3,х4). Верно ли результат представлен на рис. 2а?

Для графа G2, показанном на рисунке 1, выполнить операцию стягивания двух вершин (х3,х4). Верно ли результат представлен матрицей смежности ниже?
| X1 | X2 | X(3,4) | X5 |
---|
X1 | | | | 1 |
---|
X2 | 1 | | 1 | 1 |
---|
X(3,4) | | 1 | | 1 |
---|
X5 | | | | |
---|
В графе G6 , показанном на рис. 1 удалить дугу (х3,х2). Результат представлен в матричном виде ниже
Найти прямые отображения для вершин х3 и х4 графа, показанного на рисунке 
Найти обратные отображения для вершин х3 и х4 графа, показанного на рисунке 
Найти прямые многозначные отображения 3-го порядка для вершин х5 и х6 графа, показанного на рисунке 
Найти обратные многозначные отображения 4-го порядка для вершин х1 и х2 графа, показанного на рисунке 
Для графа, представленного на рисунке 1 построить матрицу достижимости R
а | | X1 | X2 | X3 | X4 | X5 |
---|
| X1 | 1 | 1 | 1 | 1 | 1 |
---|
R= | X2 | 0 | 0 | 1 | 1 | 1 |
---|
| X3 | 0 | 0 | 1 | 1 | 0 |
---|
| X4 | 0 | 0 | 0 | 1 | 0 |
---|
| X5 | 0 | 0 | 0 | 1 | 1 |
---|
| б | | X1 | X2 | X3 | X4 | X5 |
---|
| X1 | 1 | 1 | 1 | 1 | 1 |
---|
R= | X2 | 0 | 0 | 1 | 1 | 1 |
---|
| X3 | 0 | 0 | 0 | 1 | 0 |
---|
| X4 | 0 | 0 | 0 | 0 | 0 |
---|
| X5 | 0 | 0 | 0 | 1 | 0 |
---|
| в | | X1 | X2 | X3 | X4 | X5 |
---|
| X1 | 1 | 1 | 1 | 1 | 1 |
---|
R= | X2 | 0 | 1 | 1 | 1 | 1 |
---|
| X3 | 0 | 0 | 1 | 1 | 0 |
---|
| X4 | 0 | 0 | 0 | 1 | 0 |
---|
| X5 | 0 | 0 | 0 | 1 | 1 |
---|
|
Какая из представленных матриц контрдостижимости соответствует графу на рис. 1?
а | | X1 | X2 | X3 | X4 | X5 | X6 |
---|
| X1 | 0 | 0 | 0 | 1 | 1 | 1 |
---|
Q= | X2 | 1 | 0 | 1 | 1 | 1 | 1 |
---|
| X3 | 1 | 0 | 0 | 1 | 1 | 1 |
---|
| X4 | 1 | 0 | 0 | 0 | 1 | 1 |
---|
| X5 | 1 | 0 | 0 | 1 | 0 | 1 |
---|
| X6 | 1 | 0 | 0 | 1 | 1 | 0 |
---|
| б | | X1 | X2 | X3 | X4 | X5 | X6 |
---|
| X1 | 1 | 0 | 0 | 1 | 1 | 1 |
---|
Q= | X2 | 1 | 1 | 1 | 1 | 1 | 1 |
---|
| X3 | 1 | 0 | 1 | 1 | 1 | 1 |
---|
| X4 | 1 | 0 | 0 | 1 | 1 | 1 |
---|
| X5 | 1 | 0 | 0 | 1 | 1 | 1 |
---|
| X6 | 1 | 0 | 0 | 1 | 1 | 1 |
---|
| в | | X1 | X2 | X3 | X4 | X5 | X6 |
---|
| X1 | 1 | 1 | 1 | 1 | 1 | 1 |
---|
Q= | X2 | 0 | 1 | 0 | 0 | 0 | 0 |
---|
| X3 | 0 | 1 | 1 | 0 | 0 | 0 |
---|
| X4 | 1 | 1 | 1 | 1 | 1 | 1 |
---|
| X5 | 1 | 1 | 1 | 1 | 1 | 1 |
---|
| X6 | 1 | 1 | 1 | 1 | 1 | 1 |
---|
|
Для графа, представленного на рисунке, найти: вершины, входящие в путь между вершинами х1и х3. 
Для графа, данного на рисунке найти между какими вершинами наибольшее число путей длиной 2. 
Для графа, данного на рисунке определить между какой парой вершин большее количество путей длиной 2: A и C или B и D
Для графа, данного на рисунке найти количество путей длиной 4 между всеми вершинами графа
По матрицам смежности определить какие из графов являются полными.
Какие из приведенных на рисунке графов являются симметрическими?
Какие из приведенных на рисунке графов являются антисимметрическими?
Какие из приведенных на рисунке графов являются антисимметрическими?
Какие из приведенных на рисунке графов являются деревьями?
Дан граф на рисунке 1. Какие из приведенных на рисунке 2 графов являются его остовными подграфами?

Для графа G = (X, A), представленного на рисунке 1, описать матрицей смежности порожденный подграф {х1,х2,х3,х4,х5}
а | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 1 | 0 | 0 | 0 |
---|
X2 | 0 | 0 | 1 | 0 | 1 |
---|
X3 | 0 | 0 | 0 | 0 | 1 |
---|
X4 | 0 | 0 | 1 | 0 | 0 |
---|
X5 | 0 | 0 | 1 | 0 | 0 |
---|
| b | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 1 | 0 | 0 | 0 |
---|
X2 | 0 | 0 | 1 | 0 | 1 |
---|
X3 | 0 | 0 | 0 | 1 | 1 |
---|
X4 | 0 | 0 | 0 | 1 | 0 |
---|
X5 | 0 | 0 | 1 | 1 | 0 |
---|
| c | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 1 | 0 | 0 | 0 |
---|
X2 | 0 | 0 | 1 | 0 | 1 |
---|
X3 | 0 | 0 | 0 | 1 | 1 |
---|
X4 | 0 | 0 | 0 | 0 | 0 |
---|
X5 | 0 | 0 | 1 | 0 | 0 |
---|
|
Для графа G = (X, A) , представленного на рисунке, описать явно остовный подграф(X, A’) , где xi,xj ∈ A' тогда и только тогда, когда i+j нечетно 
Выделить в графе на рисунке с сильную компоненту, содержащую максимальное число элементов. 
Выделить в графе на рисунке а одностороннюю компоненту, содержащую максимальное число элементов. 
Для графа на рисунке найти сильную компоненту, содержащую элемент х4
Методом Мальгранжа разбить граф, представленный на рисунке, на максимальные сильно связные подграфы
Построить все возможные пути длиной 2 в графе, изображенном на рисунке для вершин A и E.
Построить орцепи максимальной длины из вершин D и B графа, изображенного на рисунке 
Построить простые орцепи максимальной длины из вершин A и D графа, изображенного на рисунке 
Для графа на рисунке даны маршруты из вершины 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)
Найти среди них цепи
Для графа, представленного на рисунке даны замкнутые пути:
М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)
Какие из этих путей являются гамильтоновыми контурами?
Для графа, представленного на рисунке построить гамильтоновы и эйлеровы циклы. 
Обновление пометок на каждой итерации алгоритма Дейкстры происходит
Если с помощью алгоритма Дейкстры требуется найти кратчайшие пути от вершины x3 до других вершин графа, то в первой итерации ей присваивается пометка со значением ...
Найти кратчайший путь от вершины 1 к вершине 6 графа, представленного на рисунке 
Найти кратчайший путь от вершины x1 к вершине x9 графа, представленного на рисунке А, матрица расстояний между вершинами дана на рис. Б
Для графа, представленного на рисунке 1а, построить базу относительно вершины х1.

Метод разбиения графа по матрицам R и Q рассмотреть на примере графа, изображенного матрицей смежности
| X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 |
---|
X1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 |
---|
X2 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
---|
X3 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
---|
X4 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
---|
X5 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
---|
X6 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
---|
X7 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
---|
X8 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
---|
Найти обратные отображения для вершин х1и х2графа, показанного на рисунке 
Какие из приведенных на рисунке графов являются симметрическими? 
Для графа G = (X, A) , представленного на рисунке, описать явно остовный подграф(X, A’) , где xi,xj ∈ A' тогда и только тогда, когда i+j < 10
Для графа G2, показанном на рисунке a, выполнить операцию стягивания двух вершин (х3,х4). Верно ли результат представлен графом на рисунке б?
Какие из приведенных на рисунке графов являются антисимметрическими? 
Для графа на рисунке найти сильную компоненту, содержащую элемент х5
Для графа G1, показанном на рисунке 1, выполнить операцию отождествления двух вершин (х1,х2). Верно ли результат представлен матрицей смежности ниже?
| X(1,2) | X3 | X4 | X5 |
---|
X(1,2) | 1 | | 1 | 1 |
---|
X3 | | | | |
---|
X4 | | 1 | | |
---|
X5 | 1 | | 1 | |
---|
Для графа, представленного на рисунке даны замкнутые пути:
М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)
Какие из этих путей являются контурами?
Какие из приведенных на рисунке графов являются полными?
Для графа, представленного на рисунке построить матрицу контрдостижимости и определить какая из вершин достижима для наибольшего числа вершин графа.
По матрице смежности, данной ниже подсчитать полустепень захода второй вершины dt(х2)
1 | 0 | 1 | 1 | 0 | 0 |
0 | 1 | 0 | 1 | 0 | 1 |
0 | 0 | 0 | 1 | 0 | 1 |
0 | 0 | 1 | 0 | 0 | 1 |
1 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 0 | 0 | 0 | 1 |
Какие вершины инцидентны дуге f в графе на рисунке?
По матрицам смежности, приведенным ниже определить какие из графов являются полными.
Для графа, представленного на рисунке построить гамильтонов цикл и эйлеров путь. 
Какие из приведенных на рисунке графов являются полными симметрическими?
По матрице инциденций найти полустепени исхода для Х2
| a1 | a2 | a3 | a4 | a5 | a6 | a7 | a8 | a9 | a10 |
---|
X1 | 1 | -1 | 1 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
---|
X2 | 0 | 1 | -1 | 1 | 0 | 0 | 0 | 0 | 0 | 0 |
---|
X3 | 0 | 0 | 0 | -1 | -1 | 1 | 0 | 1 | 0 | 0 |
---|
X4 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 | 1 | 0 |
---|
X5 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | -1 | -1 |
---|
X6 | 0 | 0 | 0 | 0 | 0 | -1 | 0 | 0 | 0 | 1 |
---|
Для графа, изображенного на рисунке найти обратные транзитивные замыкания для вершин х1 и х2,
Какие из приведенных на рисунке графов являются односторонне связными?
Для чего использую алгоритм Дейкстра?
Является ли граф, представленный на рисунке, планарным? 
В графе G6 , показанном на рис. 1 удалить дугу (х1,х2). Результат представлен ниже в матричном виде
Для графа, представленного на рисунке, найти: вершины, входящие в путь между вершинами х1 и х7.
Для графа, данного на рисунке найти количество путей длиной 3 между всеми вершинами графа.
Для графа, изображенного на рисунке, дать описание перечислением.
Какая из представленных матриц достижимости соответствует графу на рисунке 1?
а | | X1 | X2 | X3 | X4 | X5 | X6 |
---|
| X1 | 0 | 0 | 0 | 1 | 1 | 1 |
---|
R= | X2 | 1 | 0 | 1 | 1 | 1 | 1 |
---|
| X3 | 1 | 0 | 0 | 1 | 1 | 1 |
---|
| X4 | 1 | 0 | 0 | 0 | 1 | 1 |
---|
| X5 | 1 | 0 | 0 | 1 | 0 | 1 |
---|
| X6 | 1 | 0 | 0 | 1 | 1 | 0 |
---|
| б | | X1 | X2 | X3 | X4 | X5 | X6 |
---|
| X1 | 1 | 0 | 0 | 1 | 1 | 1 |
---|
R= | X2 | 1 | 1 | 1 | 1 | 1 | 1 |
---|
| X3 | 1 | 0 | 1 | 1 | 1 | 1 |
---|
| X4 | 1 | 0 | 0 | 1 | 1 | 1 |
---|
| X5 | 1 | 0 | 0 | 1 | 1 | 1 |
---|
| X6 | 1 | 0 | 0 | 1 | 1 | 1 |
---|
| в | | X1 | X2 | X3 | X4 | X5 | X6 |
---|
| X1 | 1 | 1 | 1 | 1 | 1 | 1 |
---|
R= | X2 | 0 | 1 | 0 | 0 | 0 | 0 |
---|
| X3 | 0 | 1 | 1 | 0 | 0 | 0 |
---|
| X4 | 1 | 1 | 1 | 1 | 1 | 1 |
---|
| X5 | 1 | 1 | 1 | 1 | 1 | 1 |
---|
| X6 | 1 | 1 | 1 | 1 | 1 | 1 |
---|
|
Для нахождения кратчайшего пути от s к хi, предшествующую вершину xi* можно найти как одну из вершин, для которой
Найти кратчайший путь от вершины 1 к вершине 8 графа, представленного на рисунке 
Какие дуги инцидентны вершине 3 в графе на рисунке?
Выполнить операцию нахождения кольцевой суммы G1 ⊕ G2 для графов, представленных матрицами смежности в таблице 1
Матрица смежности G1 | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 0 | 0 | 0 | 1 |
---|
X2 | 1 | 0 | 0 | 1 | 0 |
---|
X3 | 0 | 0 | 0 | 0 | 0 |
---|
X4 | 0 | 0 | 1 | 0 | 0 |
---|
X5 | 0 | 1 | 0 | 1 | 0 |
---|
| Матрица смежности G2 | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 0 | 0 | 0 | 1 |
---|
X2 | 1 | 0 | 1 | 0 | 1 |
---|
X3 | 0 | 0 | 0 | 0 | 0 |
---|
X4 | 0 | 1 | 1 | 0 | 1 |
---|
X5 | 0 | 0 | 0 | 0 | 0 |
---|
|
a | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 0 | 0 | 0 | 1 |
---|
X2 | 1 | 0 | 0 | 0 | 0 |
---|
X3 | 0 | 0 | 0 | 0 | 0 |
---|
X4 | 0 | 0 | 1 | 0 | 0 |
---|
X5 | 0 | 0 | 0 | 0 | 0 |
---|
| б | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 0 | 0 | 0 | 0 |
---|
X2 | 0 | 0 | 1 | 1 | 1 |
---|
X3 | 0 | 0 | 0 | 0 | 0 |
---|
X4 | 0 | 1 | 0 | 0 | 1 |
---|
X5 | 0 | 1 | 0 | 1 | 0 |
---|
| в | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 0 | 0 | 0 | 1 |
---|
X2 | 1 | 0 | 1 | 1 | 1 |
---|
X3 | 0 | 0 | 0 | 0 | 0 |
---|
X4 | 0 | 1 | 1 | 0 | 1 |
---|
X5 | 0 | 1 | 0 | 1 | 0 |
---|
|
Найти прямые многозначные отображения 4-го порядка для вершин х1 и х2 графа, показанного на рисунке 
Найти обратные многозначные отображения 3-го порядка для вершин х3и х4графа, показанного на рисунке 
Для графа, изображенного на рисунке найти прямые транзитивные замыкания для вершин х5и х6,
Для графа, данного на рисунке найти количество путей длиной 2 между всеми вершинами графа.
Для графа, данного на рисунке определить между какой парой вершин большее количество путей длиной 2: F и C или E и C
Какие из приведенных на рисунке графов являются полными? 
Какие из приведенных на рисунке графов являются симметрическими?
Является ли граф на рисунке двудольным? 
Дан граф на риунке 1. Какой из приведенных на рисунке 2 графов является для него порожденным подграфом?

Для графа G = (X, A) , представленного на рисунке 1, описать матрицей смежности порожденный подграф {х2,х3, х4,х5, х6}
а | X2 | X3 | X4 | X5 | X6 |
---|
X2 | 0 | 1 | 0 | 1 | 0 |
---|
X3 | 0 | 0 | 1 | 1 | 0 |
---|
X4 | 0 | 0 | 0 | 0 | 1 |
---|
X5 | 0 | 1 | 0 | 0 | 0 |
---|
X6 | 0 | 0 | 1 | 0 | 0 |
---|
| b | X2 | X3 | X4 | X5 | X6 |
---|
X2 | 0 | 1 | 0 | 0 | 0 |
---|
X3 | 0 | 0 | 1 | 1 | 0 |
---|
X4 | 0 | 0 | 1 | 0 | 0 |
---|
X5 | 0 | 0 | 0 | 1 | 0 |
---|
X6 | 1 | 0 | 0 | 1 | 0 |
---|
| c | X2 | X3 | X4 | X5 | X6 |
---|
X2 | 0 | 1 | 0 | 0 | 0 |
---|
X3 | 0 | 0 | 1 | 0 | 1 |
---|
X4 | 0 | 0 | 0 | 0 | 1 |
---|
X5 | 0 | 1 | 0 | 0 | 1 |
---|
X6 | 1 | 0 | 1 | 0 | 0 |
---|
|
Для графа G = (X, A) , представленного на рисунке, описать явно остовный подграф(X, A’) , где xi,xj ∈X тогда и только тогда, когда i+j четно 
Выделить в графе на рисунке f сильную компоненту, содержащую максимальное число элементов. 
Методом Мальгранжа разбить граф, представленный на рисунке, на подграфы
Метод разбиения графа по матрицам R и Q рассмотреть на примере графа, изображенного матрицей смежности
| X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 |
---|
X1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
---|
X2 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 |
---|
X3 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
---|
X4 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 |
---|
X5 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 |
---|
X6 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
---|
X7 | 0 | 1 | 1 | 0 | 0 | 1 | 0 | 1 |
---|
X8 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
---|
Построить все возможные пути длиной 2 в графе, изображенном на рисунке для вершин A и D.
Для графа на рисунке даны маршруты из вершины 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), причем а равно выгоде, получаемой при обслуживании этого маршрута, а 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.
Значение постоянной метки показывает
Найти кратчайший путь от вершины x1 к вершине x5 графа, представленного на рисунке А, матрица расстояний между вершинами дана на рис.Б 
Для графа, представленного на рисунке 1а, построить базу относительно вершины х3.

Для графа G2, показанном на рисунке 1, выполнить операцию стягивания двух вершин (х1,х2). Верно ли результат представлен матрицей смежности ниже?
| X(1,2) | X3 | X4 | X5 |
---|
X(1,2) | | 1 | | 1 |
---|
X3 | | | | |
---|
X4 | 1 | 1 | | 1 |
---|
X5 | | | | |
---|
По матрице смежности, данной ниже подсчитать количество петель графа.
1 | 0 | 1 | 1 | 0 | 0 |
0 | 1 | 0 | 1 | 0 | 1 |
0 | 0 | 0 | 1 | 0 | 1 |
0 | 0 | 1 | 0 | 0 | 1 |
1 | 0 | 0 | 0 | 0 | 0 |
0 | 1 | 0 | 0 | 0 | 1 |
Для графа, данного на рисунке определить между какой парой вершин большее количество путей длиной 2: F и C или D и B
Перечислите дуги, являющиеся петлями в графе на рисунке?
Какие дуги инцидентны вершине 2 в графе на рисунке?
Для графа, изображенного на рисунке найти прямые транзитивные замыкания для вершин х3 и х4
Найти максимальный сильно связанный подграф, включающий вершину F, для графа, матрица смежности которого представлена ниже
| A | B | C | D | E | F | G | K |
---|
A | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
---|
B | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
---|
C | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
---|
D | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
---|
E | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
---|
F | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
---|
G | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
---|
K | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
---|
Найти прямые многозначные отображения 2-го порядка для вершин х3 и х4 графа, показанного на рисунке 
Даны матрицы смежности и матрица инцидентности. Соответствуют ли они графу на рисунке?
матрица смежности | X1 | X2 | X3 | X4 |
---|
X1 | 1 | 1 | 0 | 0 |
---|
X2 | 0 | 0 | 1 | 1 |
---|
X3 | 0 | 0 | 0 | 0 |
---|
X4 | 1 | 1 | 1 | 0 |
---|
| матрица инциденций | a1 | a2 | a3 | a4 | a5 | a6 | a7 |
---|
X1 | 0 | 1 | 1 | 0 | 0 | 0 | -1 |
---|
X2 | 0 | -1 | 0 | -1 | 1 | 0 | 0 |
---|
X3 | 0 | 0 | 0 | 0 | -1 | -1 | 0 |
---|
X4 | 0 | 0 | -1 | 1 | 0 | 1 | 1 |
---|
|
Найти обратные отображения для вершин х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 | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 0 | 0 | 0 | 1 |
---|
X2 | 1 | 0 | 0 | 1 | 0 |
---|
X3 | 0 | 0 | 0 | 0 | 0 |
---|
X4 | 0 | 0 | 1 | 0 | 0 |
---|
X5 | 0 | 1 | 0 | 1 | 0 |
---|
| Матрица смежности G2 | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 0 | 0 | 0 | 1 |
---|
X2 | 1 | 0 | 1 | 0 | 1 |
---|
X3 | 0 | 0 | 0 | 0 | 0 |
---|
X4 | 0 | 1 | 1 | 0 | 1 |
---|
X5 | 0 | 0 | 0 | 0 | 0 |
---|
|
a | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 0 | 0 | 0 | 1 |
---|
X2 | 1 | 0 | 0 | 0 | 0 |
---|
X3 | 0 | 0 | 0 | 0 | 0 |
---|
X4 | 0 | 0 | 1 | 0 | 0 |
---|
X5 | 0 | 0 | 0 | 0 | 0 |
---|
| б | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 0 | 0 | 0 | 0 |
---|
X2 | 0 | 0 | 1 | 1 | 1 |
---|
X3 | 0 | 0 | 0 | 0 | 0 |
---|
X4 | 0 | 1 | 0 | 0 | 1 |
---|
X5 | 0 | 1 | 0 | 1 | 0 |
---|
| в | X1 | X2 | X3 | X4 | X5 |
---|
X1 | 0 | 0 | 0 | 0 | 1 |
---|
X2 | 1 | 0 | 1 | 1 | 1 |
---|
X3 | 0 | 0 | 0 | 0 | 0 |
---|
X4 | 0 | 1 | 1 | 0 | 1 |
---|
X5 | 0 | 1 | 0 | 1 | 0 |
---|
|
Для графа G1, показанном на рисунке 1, выполнить операцию отождествления двух вершин (х3,х4). Верно ли результат представлен матрицей смежности ниже? 
| X1 | X2 | X(3,4) | X5 |
---|
X1 | | | | 1 |
---|
X2 | 1 | | | |
---|
X(3,4) | | | 1 | |
---|
X5 | | 1 | 1 | |
---|
Для графа, представленного на рисунке построить матрицу достижимости и определить для какой из вершин графа достижимо наибольшее число вершин.
Какие из приведенных на рисунке графов являются полными симметрическими?
Является ли граф на рисунке двудольным? 
Для графа G = (X, A) , представленного на рисунке 1, описать матрицей смежности порожденный подграф {х1,х2,х3, ,х5, х7}
а | X1 | X2 | X3 | X5 | X7 |
---|
X1 | 0 | 1 | 0 | 0 | 0 |
---|
X2 | 0 | 0 | 1 | 0 | 1 |
---|
X3 | 0 | 0 | 0 | 0 | 1 |
---|
X5 | 0 | 0 | 1 | 0 | 0 |
---|
X7 | 0 | 0 | 1 | 0 | 0 |
---|
| b | X1 | X2 | X3 | X5 | X7 |
---|
X1 | 0 | 1 | 0 | 0 | 0 |
---|
X2 | 0 | 0 | 1 | 1 | 0 |
---|
X3 | 0 | 0 | 0 | 1 | 0 |
---|
X5 | 0 | 0 | 1 | 0 | 0 |
---|
X7 | 1 | 0 | 0 | 1 | 0 |
---|
| c | X1 | X2 | X3 | X5 | X7 |
---|
X1 | 0 | 1 | 0 | 0 | 0 |
---|
X2 | 0 | 0 | 1 | 0 | 1 |
---|
X3 | 0 | 0 | 0 | 1 | 1 |
---|
X5 | 0 | 0 | 0 | 0 | 1 |
---|
X7 | 1 | 0 | 1 | 0 | 0 |
---|
|
Выделить в графе на рисунке e сильную компоненту, содержащую максимальное число элементов. 
Выделить в графе на рисунке b одностороннюю компоненту, содержащую максимальное число элементов. 
Для графа на рисунке найти сильную компоненту, содержащую элемент х1
Методом Мальгранжа разбить граф, представленный ниже матрицей смежности, на подграфы
| X1 | X2 | X3 | X4 | X5 | X6 | X7 | X8 |
---|
X1 | 1 | 1 | 0 | 1 | 0 | 0 | 0 | 0 |
---|
X2 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 0 |
---|
X3 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 |
---|
X4 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 |
---|
X5 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
---|
X6 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
---|
X7 | 0 | 1 | 0 | 0 | 0 | 1 | 0 | 1 |
---|
X8 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
---|
Построить орцепи максимальной длины из вершин E и F графа, изображенного на рисунке 
В графе G6 , показанном на рис. 1 удалить дугу (х1,х3). Результат представлен ниже в матричном виде
Для графа на рисунке даны маршруты из вершины 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. Результат представлен в матричном виде ниже
По матрицам смежности определить какие из графов являются полными.
а1 | 1 | 1 | 1 | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | | b0 | 1 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 | 0 | 0 | | c1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 0 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | | d0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 1 | 1 | 0 | 0 | 0 | 1 | 1 | 1 | 0 | 0 | 1 | 1 | 1 | 1 | 0 | |
Какие из приведенных на рисунке графов являются полными антисимметрическими?
Является ли граф, представленный на рисунке, планарным? 
Выделить в графе на рисунке f одностороннюю компоненту, содержащую максимальное число элементов. 
Для графа, представленного на рисунке, найти: вершины, входящие в путь между вершинами х1 и х6. 
Найдите полустепени исхода и захода для вершины х2 графа
Выполнить операцию объединения G1 G2 для графов, показанных на рисунке 1


Для графа G1, показанном на рисунке a, выполнить операцию стягивания двух вершин (х1,х2). Верно ли результат представлен графом на рисунке б?
Найти прямые отображения для вершин х1 и х2 графа, показанного на рисунке 
На рисунке дан граф со взвешенными дугами, который представляет сеть допустимых маршрутов для некоторого судна. Каждая дуга имеет пометку(a, b), причем а равно выгоде, получаемой при обслуживании этого маршрута, а b – времени обслуживания маршрута. Найти, какой из перечисленных путей наиболее выгодный (в терминах скорости оборота капитала) путь судна.
vn=∑ ai/ ∑ bi
Для графа, изображенного на рисунке найти обратные транзитивные замыкания для вершин х3 и х4
В графе G6 , показанном на рис. 1 удалить вершину х3. Результат представлен в матричном виде ниже
Построить простые орцепи максимальной длины из вершин F и E графа, изображенного на рисунке 
Какие из приведенных на рисунке графов являются сильно связными?
Найти обратные многозначные отображения 4-го порядка для вершин х5 и х3графа, показанного на рисунке 
Найти максимальный сильно связанный подграф, включающий вершину Е, для графа, матрица смежности которого представлена ниже
| A | B | C | D | E | F | G | K |
---|
A | 1 | 1 | 0 | 0 | 1 | 0 | 0 | 0 |
---|
B | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |
---|
C | 0 | 0 | 1 | 0 | 1 | 0 | 0 | 0 |
---|
D | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
---|
E | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 |
---|
F | 1 | 0 | 0 | 0 | 0 | 0 | 1 | 0 |
---|
G | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 |
---|
K | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 |
---|
Методом Мальгранжа разбить граф, представленный на рисунке, на максимальные сильно связные подграфы
Для графа, представленного на рисунке даны замкнутые пути:
М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 графа, представленного на рисунке 