Число остовных деревьев в связном графе, порядка не меньше двух, равно алгебраическому дополнению любого элемента матрицы
+а) Кирхгофа
б) Паули
в) связности
г) смежности
д) отношения
Количество определяющих свойств отношения эквивалентности равно-...
ОТВЕТ:3
Циклический ранг любого дерева равен-...
ОТВЕТ:0
Если в графе число рёбер превышает число вершин, то граф
+а) имеет цикл
б) без циклов
в) имеет вес
г) эйлеров
д) полный
Граф имеет единственный цикл тогда и только тогда, когда его циклический ранг равен-...
ОТВЕТ:1
Граф является лесом тогда и только тогда, когда его циклический ранг равен-...
ОТВЕТ:0
Цикломатическое число циклического графа равно-...
ОТВЕТ:1
Цикломатическое число дерева равно-...
ОТВЕТ:0
35.Пусть n - число вершин, m - число рёбер и k - число компонент связности простого графа G . Тогда количество рёбер, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно v ( G ) = m – n + k. Это число называется
+а) цикломатическим
б) кардинальным
в) степенью графа
г) факториальным
д) порядком графа
36.Пусть f – функция: A → B , A и B – конечные множества. Теорема « Если мощность A больше мощности B , то по крайней одно значение f встретится более одного раза» называется
+а) принципом Дирихле
б) функцией Дирихле
в) теоремой Кёнига
г) теоремой Эйлера
д) принципом Беллмана
37.Пусть n - число вершин, m - число рёбер и k - число компонент связности простого графа G . Тогда число v ( G ) = m - n + k равно количеству рёбер, которые необходимо удалить для получения остова. Это число называется
|
|
|
+а) цикломатическим
б) кардинальным
в) степенью графа
г) факториальным
д) порядком графа
Пусть n - число вершин, m - число рёбер и k - число компонент связности простого графа G . Тогда количество рёбер, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно
+а) m- n + k
б) m+ n - k
в) m + n + k
г) m - n - k
д) n - k
Верным среди следующих утверждений является утверждение
+а) всякое дерево является лесом
б) всякий лес является деревом
в) не всякое дерево является лесом
г) ни одно дерево не является лесом
д) ходить по лесу лучше, чем по циклу
40. 38.Пусть n =7 - число вершин, m =5 - число рёбер и k =2 - число компонент связности простого графа G . Тогда количество рёбер, которые необходимо удалить для получения остова, не зависит от последовательности их удаления и равно-...
ОТВЕТ:0
Количество различных деревьев, которые можно построить на 4 различных вершинах, равно-...
ОТВЕТ:16
Теорема Кэли: количество различных деревьев, которые можно построить на n различных вершинах, равно
+а) n n - 2
б) (n-2)n
в) n n
г) 2n
д) n2
В приложениях важной является задача о построении остова графа
|
|
|
+а) экстремального веса
б) с равными рёбрами
в) с тремя рёбрами
г) с размеченными вершинами
д) с разными рёбрами
ОТВЕТ:4
44.
Номер регулярного графа на рисунке равен-...
ОТВЕТ:4
Количество различных деревьев, которые можно построить на 3 различных вершинах, равно-...
ОТВЕТ:3
Один из алгоритмов построения экстремального остовного дерева называется алгоритмом
+а) Прима (ближайшего соседа)
б) Беллмана - Мура
в) Форда - Фалкерсона
г) Фалкерсона
д) меток Дейкстры
47. 35.Пусть n - число вершин, m - число рёбер и k - число компонент связности простого графа G . Тогда количество рёбер, входящих в любой остов графа G , равно v * ( G ) = n - k. Это число называется
+а) коциклическим рангом
б) циклическим рангом
в) степенью графа
г) факториальным
д) порядком графа
Пусть n - число вершин, m - число рёбер и k - число компонент связности простого графа G . Тогда количество рёбер, входящих в любой остов графа G , равно
+а) n - k
б) m+ n - k
в) n + k
г) m - n
д) n + k -m
Количество различных деревьев, которые можно построить на 5 различных вершинах, равно-...
ОТВЕТ:125
Граф является деревом тогда и только тогда, когда любые две его вершины связаны единственной (ым)
|
|
|
+а) цепью
б) дугой
в) ребром
г) прямой
д) мостом
51.Пусть граф T является деревом и имеет n вершин. Тогда T
+а) не имеет циклов и имеет n - 1 ребро
б) имеет циклы и имеет n - 1 ребро
в) не имеет циклов и имеет n рёбер
г) не имеет циклов и имеет n - 2 ребра
д) не имеет циклов и моста
Дата добавления: 2018-09-23; просмотров: 242; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!