4. Нет правильного ответа
Дан граф G(V,E):
Матрицей смежности вершин является …
4) нет правильного ответа.
Дан граф G(V,E):
Матрицей смежности рёбер является …
4) нет правильного ответа
Дан граф G(V,E):
Матрицей инцидентности является …
4) нет правильного ответа.
Если в графе G(V, E)удаление вершины Vi увеличивает число компонент связности, эту вершину называют …
а) изолированная вершина;
б) точка сочленения;
в) заходящая вершина;
г) исходящая вершина.
Пусть p - число вершин, q - число ребер, k - число компонент связности графов. Тогда справедливы следующие отношения:
а) q
б) p – k
в) q
г) p (p-k)
Если G состоит из одной компоненты связности K(G)= 1, то граф называется:
а) точкой сочленения;
б) мостом;
в) блоком;
г) связным графом.
Ребро, удаление которого увеличивает число компонент связности, называют:
а) мостом;
б) насыщенное ребро;
в) ненасыщенное ребро;
г) нагруженное ребро.
Связный граф, не имеющий точек сочленения, называют:
а) тривиальный;
б) блок;
в) Эйлеров граф;
г) Гамильтонов граф.
Наименьшее число вершин, удаление которых приводит к несвязному или тривиальному графу, называется:
а) реберной связностью;
б) вершинной связностью;
в) точка сочленения;
г) изолированная точка.
Максимальное количество ресурса, которое может пропустить в единицу времени по заданному ребру называется:
а) пропускной способностью;
б) потоком по этому ребру;
в) потоком по сети;
Количество ресурса, проходящее через ребро в единицу времени называется:
а) потоком по этому ребру;
б) насыщенным;
в) ненасыщенным;
г) потоком по сети.
Если граф G несвязный, тогда он имеет следующую характеристику вершинной связности:
а) λ(G) = 1
б) λ(G) = 0
в) λ(G) = -1
г) λ(G) = 2
Если на сети задан поток x ={xij}<cij, то ребро между вершиной i-й и j-й называется …
а) поток по сети;
б) насыщенным;
в) ненасыщенным;
г) поток по этому ребру.
Если на сети задан поток x ={xij} и если поток xij по нему совпадает с пропускной способностью, то ребро называется …
а) насыщенным;
б) потоком по сети;
в) ненасыщенным;
г) разрезом на сети.
Если задан орграф G (V, E), в котором дуги помечены числами, то эти числа называются …
а) длинами;
б) весами;
в) пропускной способностью.
Алгоритм Флойда находит:
а) кратчайший путь между двумя данными вершинами орграфа, если длины дуг отрицательны;
б) кратчайшие пути между всеми парами вершин в орграфе;
в) кратчайший путь между двумя данными вершинами в орграфе, если длины дуг неотрицательны.
Алгоритм Дейкстры находит:
а) кратчайшие пути между всеми парами вершин в орграфе;
б) кратчайший путь между двумя данными вершинами орграфа, если длины дуг неотрицательны;
в) кратчайший путь между двумя данными вершинами орграфа, если длины дуг отрицательны.
Совокупность ребер (i,j), начальные вершины которых принадлежит подмножеству А, а конечные подмножеству В транспортной сети, и обозначается R (A/B) называется …
а) пропускной способностью разреза;
б) разрезом сети;
в) потоком по сети.
Ориентированное дерево, в котором полустепень исхода любой его вершины не больше 2 называют:
1) полным
2) бинарным
3) выровненным
4) сбалансированным
Ордерево называется … , если все узлы, степень которых меньше 2, располагаются на одном или двух последних уровнях.
1) выровненным
2) сбалансированным
3) одноуровненным
4) полным
Каким обязательно должно быть Выровненное дерево?
1) связным
2) симметричным
3) несимметричным
4) многосвязным
Как называют бесконтурный ориентированный граф, у которого полустепень захода любой вершины не больше 1 и существует ровно одна вершина, называемая корнем ориентированного дерева, полустепень захода которой равна 0?
1) неориентированное дерево
2) ориентированное дерево
3) сбалансированное дерево
Какое бинарное дерево называют сбалансированным?
1) если все листья находятся на одном уровне
2) если полустепень исхода любой его вершины не больше 2
3) если для любого узла высота левого и правого поддеревьев отличается не более чем на единицу.
Сбалансированным по высоте деревом называется также:
1) выровненным
2) подровненным
3) АВЛ-деревом
Для сбалансированного по высоте бинарного дерева:
1) h < 2 log2 p.
2) h < log2 p
3) h < 2 lg p
Какие основные структуры данных используются для представления ассоциативной памяти?
1) неупорядоченный массив
2) упорядоченный массив
3) сбалансированные деревья
4) таблица расстановки
Какое дерево оказывается во многих случаях наилучшим вариантом представления дерева сортировки?
1) сбалансированное дерево.
2) выровненное
3) полное
Как еще называется таблица расстановки в ассоциативной памяти?
1) хэш-таблица
2) ассоциативная таблица
3) таблица данных
По какой формуле рассчитывается сумма степеней вершин графа?
А)
Б)
По какой формуле рассчитывается сумма полу степеней вершин орграфа?
А)
Б)
Какой цикл называется гамильтоновым циклом?
1) содержащий все вершины графа (по одному разу);
2) содержащий все вершины графа (по нескольку раз);
3) содержащий все ребра графа (по одному разу);
4) содержащий все ребра графа (по нескольку раз);
Какой цикл называется эйлеровым циклом
1) цикл содержащий все рёбра графа по несколько раз;
2) цикл содержащий все рёбра графа;
3) цикл содержащий ребро графа;
4) цикл, содержащий все рёбра графа по одному разу;
Название «гамильтонов цикл» произошло от задачи…
1) «Овальное путешествие»
2) « Путешествие вокруг земли»
3) «Кругосветное путешествие»
4) «Круговое путешествие»