Рефлексивное, симметричное и транзитивное бинарное отношение на множестве A называется отношением
Если ты читаешь это, тебе повезло - ты жив. Продолжай отвечать на вопросы.
С головоломкой о кёнигсбергских мостах связано понятие
+а) эйлерова графа
б) полного графа
в) регулярного графа
г) звёздного графа
д) связного графа
2.Матрица смежностей вершин простого графа
+а) симметричная
б) единичная
в) вырожденная
г) нулевая
д) диагональная
Утверждение «Для любой сети с одним источником и одним стоком величина максимального потока в сети от источника к стоку равна величине минимального разреза» называется теоремой
+а) Форда - Фалкерсона
б) Эйлера
в) Понтрягина
г) о рукопожатиях
д) Кёнига
Для нахождения кратчайшего пути между двумя заданными вершинами в ориентированной сети используется алгоритм
+а) Дейкстры
б) Кнута
в) Прима
г) Евклида
д) Маркова
5.Если P ( G ) - матрица смежностей вершин простого графа G , имеющего порядок n , B = E + P + P 2 + P 3 + …+ P n , то матрица C = ( sign b i , j ) называется матрицей
+а) связности
б) достижимости
в) смежности
г) инцидентности
д) Кирхгофа
6.Если P ( G ) - матрица смежностей вершин орграфа G , имеющего порядок n , B = E + P + P 2 + P 3 + …+ P n , то матрица C = ( sign b i , j ) называется матрицей
+а) достижимости
б) связности
в) смежности
г) инцидентности
д) Кирхгофа
7.Если P ( G ) - матрица смежностей вершин графа G , b ( i , j ) – элемент матрицы B = P k , то количество маршрутов длины k , соединяющих i - ю и j - ю вершины в графе G , равно
|
|
|
+а) b (i, j)
б) 2b (i, j)
в) b(1, 1)
г) b ( n , n )
д) 1
Ранг матрицы смежностей вершин графа называется
+а) рангом графа
б) порядком связности
в) порядком смежности
г) степенью графа
д) циклическим рангом
Ранг графа G обозначается
+а) rank G
б) sign G
в) deg G
г) in deg G
д) out deg G
С головоломкой о трёх домах и трёх колодцах связано понятие
+а) планарного графа
б) полного графа
в) регулярного графа
г) звёздного графа
д) связного графа
Граф, изоморфный некоторому плоскому графу, называется
+а) планарным
б) полным
в) пустым
г) циклическим
д) звёздным
Не является планарным граф
+а) K3,3
б) K3
в) K2,2
г) K2,3
д) K4
Граф, не являющийся планарным, суть
+а) K5
б) K3
в) K2,2
г) K2,3
д) K4
Теорема Понтрягина - Куратовского: граф планарный тогда и тогда, когда он не имеет подграфов, гомеоморфных
+а) K3,3 или K5
б) K3
в) K2,2
г) K2,3
д) K2
Минимальное количество цветов, требующееся для правильной раскраски вершин графа, называется
|
|
|
+а) хроматическим числом
б) цикломатическим числом
в) циклическим рангом
г) порядком графа
д) степенью графа
Минимальное количество цветов, требующееся для правильной раскраски вершин графа G , называется хроматическим числом, которое обозначается
+а) 
б) v(G)
в) deg G
г) d (G)
д) r(G)
Если хроматическое число равно k , то граф называется
+а) k - хроматическим
б) бихроматическим
в) регулярным
г) звёздным
д) эйлеровым
Теорема Кёнига: непустой граф является бихроматическим тогда и только тогда, когда он
+а) не имеет циклов нечётной длины
б) имеет циклы нечётной длины
в) имеет один цикл нечётной длины
г) имеет 2 цикла нечётной длины
д) имеет 4 цикла нечётной длины
Пусть p - максимальная степень вершины графа. Тогда хроматическое число
+а) не превосходит p + 1
б) равно p + 1
в) не меньше p + 1
г) равно p
д) не меньше p
Теорема Брукса: пусть p - максимальная степень вершины связного неполного графа и p не меньше 3. Тогда хроматическое число
+а) не превосходит p
б) равно p + 1
в) не меньше p + 1
г) больше p
д) не меньше p
|
|
|
Теорема (проблема) о пяти красках: хроматическое число всякого планарного графа не превосходит-...
ОТВЕТ:5
Гипотеза четырёх красок: всякий планарный граф можно правильно раскрасить
+а) 4 красками
б) 3 красками
в) 2 красками
г) 1 краской
д) любым количеством
Хроматическое число любого дерева равно-...
ОТВЕТ:2
Хроматическое число полного графа 7 порядка равно-...
ОТВЕТ:7
Хроматическое число любого двудольного графа равно-...
ОТВЕТ:2
Рефлексивное, симметричное и транзитивное бинарное отношение на множестве A называется отношением
+а) эквивалентности
б) частичного порядка
в) строгого порядка
г) линейного порядка
д) не строгого порядка
Дата добавления: 2018-09-23; просмотров: 233; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!