Дискретная математика (курс 2). Часть 1

Некоторая стратегия игрока А правильно указана на дереве

Остов данного графа образуют ребра

• {a, b, f, d}
• {a, b, g, e}
• {b, c, d, g}
• {a, b, c, d, e}

Для полного графа K7 число ребер р и цикломатическое число равны: А. р = 42 В. = 15

• A – да, B – да
• A – нет, B – да
• A – да, B – нет
• A – нет, B – нет

Число ребер в полном двудольном графе К6,6 равно

• 12
• 24
• 36
• 15

Граф G с заданными длинами ребер — .Его диаметр d (G) равен

• 12
• 6
• 11
• 10

Граф состоит из двух связных компонент: в каждой 8 вершин и 13 ребер. Минимальное число ребер, после удаления которых граф не будет содержать циклов, равно

• 10
• 15
• 16
• 12

Хроматическое число полного двудольного графа К6,7 равно

• 3
• 13
• 2
• 6

Некоторая стратегия игрока А правильно указана на дереве

Граф G — цикл длины 15. Его хроматическое число χ(G) равно

• 2
• 3
• 5
• 15

Максимальный поток через сеть S1 равен 12, а через сеть S2 – 5. Тогда максимальный поток через сеть S = S1•S2 равен

• 5
• 12
• 60
• 17

Максимальный поток через сеть S1 равен 6, через сеть S2 – 10, через сеть S3 – 8. Тогда максимальный поток через сеть S равен

• 24
• 10
• 8
• 14

Кратчайший путь [AB] в ориентированном графе с заданными длинами ребер проходит через вершины

• А α β γ В
• А α γ В
• А β γ В
• А β α В

Цикломатическое число графа равно

• 10
• 8
• 6
• 12

Кодирование по Кэли дерева с занумерованными вершинами

• 2 2 3
• 1 3 2
• 3 2 2
• 3 2 1

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

• 10
• 7
• 8
• 6

Кратчайшим путем [a, b] в сети является путь

• [a, A, D, b]
• [a, A, B, b]
• [a, C, D, b]
• [a, C, B, b]

При правильной раскраске полного двудольного графа К6,9 минимальное число красок равно

• 6
• 5
• 11
• 2

Остов данного графа образуют ребра

• {a, b, e}
• {a, b, c, d}
• {a, d, c}
• {a, d}

Pасстояние между вершинами А и В в графе с заданными длинами ребер равно

• 23
• 17
• 19
• 25

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

Радиус корневого дерева равен

• 3
• 8
• 4
• 7

Число ребер в полном графе K10 равно

• 81
• 45
• 90
• 100

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

• 5
• 7
• 8
• 6

Матрица представляет собой матрицу соседства вершин ориентированного графа

Для полного K8 число вершин b и цикломатическое число равны: А. b = 8 В. = 20

• A – нет, B – да
• A – нет, B – нет
• A – да, B – да
• A – да, B – нет

Для полного двудольного графа K7,4 число вершин b и цикломатическое число равны: А. b = 28 В. = 18

• A – нет, B – да
• A – да, B – да
• A – нет, B – нет
• A – да, B – нет

Матрица представляет собой матрицу соседства вершин неориентированного графа

Для 4-мерного единичного куба Е4 число ребер р и цикломатическое число равны: А. р = 32 В. = 17

• A – нет, B – да
• A – да, B – да
• A – да, B – нет
• A – нет, B – нет

Кодирование по Кэли дерева с занумерованными вершинами

• 3 4
• 2 2
• 1 4
• 1 3

Цикломатическое число графа равно

• 0
• 25
• 24
• 7

Максимальный поток через сеть S1 равен 8, а через сеть S2 – 6. Тогда максимальный поток через сеть S = S1V S2 равен

• 48
• 6
• 14
• 8

Цикломатическое число графа равно

• 8
• 0
• 7
• 2

Граф G с заданными длинами ребер — .Его радиус r(G) и диаметр d(G) равны: А. r(G) = 6 В. d(G) = 7

• A – да, B – да
• A – нет, B – да
• A – да, B – нет
• A – нет, B – нет

Сумма степеней всех вершин графа равна

• числу вершин
• числу ребер
• удвоенному числу ребер
• удвоенному числу вершин

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

• b
• e
• d
• c

Диаметр корневого дерева равен

• 5
• 7
• 4
• 8

Цикломатическое число графа равно

• 9
• 1
• 8
• 0

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

• d
• a
• b
• f

Матрица представляет собой матрицу соседства вершин неориентированного графа

Хроматическое число графа равно

• 4
• 3
• 2
• 1

Для 5-мерного единичного куба Е5 число вершин b и цикломатическое число равны: А. b = 64 В. = 49

• A – нет, B – да
• A – нет, B – нет
• A – да, B – нет
• A – да, B – да

Граф G с заданными длинами ребер — .Его радиус r(G) равен

• 6
• 12
• 11
• 10

Расстояние между вершинами 9-мерного единичного куба E9 011010001 и 001100100 равно

• 5
• 4
• 3
• 7

При правильной раскраске графа (т. е. соседние вершины – разного цвета) минимальное число красок

• 6
• 4
• 3
• 2

Эйлерова цепь в графе начинается в вершине

• 4
• 5
• 2
• 3

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

• 7
• 6
• 9
• 8

Диаметр корневого дерева равен

• 3
• 7
• 8
• 4

В данном графе несмежными являются ребра

• (2, 5) и (1, 2)
• (2, 3) и (4, 5)
• (4, 5) и (3, 5)
• (4, 1) и (5, 4)

Граф G с заданными длинами ребер — .Его диаметр d (G) равен

• 12
• 16
• 20
• 15

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

• полным
• четным
• деревом
• циклическим