Главная /
Алгоритмы и дискретные структуры /
Графы и их применение
Графы и их применение - ответы на тесты Интуит
Правильные ответы выделены зелёным цветом.
Все ответы: В курсе излагаются основные понятия теории графов. Описаны методы решения задач.
Все ответы: В курсе излагаются основные понятия теории графов. Описаны методы решения задач.
Что называется графом?
(1) графом
G называется пара V(G), E(G), где V(G) - непустое конечное множество элементов, называемых, вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых ребрами
(2) графом
G называется V(G) - непустое конечное множество элементов, называемых вершинами
(3) графом
G называется E(G) - конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых ребрами
(4) граф представляет собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек
Какая вершина в ориентированном графе
D называется изолированной?
(1) вершина, у которой и степень входа и степень выхода равны 0
(2) вершина, степень выхода которой положительна, а степень входа равна 0
(3) вершина, степень входа которой положительна, а степень выхода равна 0
(4) вершина, степень выхода и степень входа которой положительны и равны
Что называется представлением дерева?
(1) способ записи информации о нем, однозначно и полностью восстанавливающий структуру дерева и позволяющий вычислить его характеристики
(2) способ раскраски дерева
(3) выбор направления обхода дерева
(4) подсчет листьев и корневых вершин дерева
Какие деревья называются изоморфными?
(1) два плоских дерева называются изоморфными, если существует гомеоморфное отображение плоскости на себя, сохраняющее ориентацию, и такое, что оно отображает одно из этих деревьев в другое
(2) два плоских дерева называются изоморфными, если не существует гомеоморфное отображение плоскости на себя, сохраняющее ориентацию, и такое, что оно отображает одно из этих деревьев в другое
(3) два плоских дерева называются изоморфными, если существует гомеоморфное отображение плоскости на себя, сохраняющее ориентацию, и такое, что оно не отображает одно из этих деревьев в другое
(4) два плоских дерева называются изоморфными, если существует взаимно однозначное отображение плоскости на себя, сохраняющее ориентацию, и такое, что оно отображает одно из этих деревьев в другое
Пусть граф имеет
n вершин. Когда граф T является деревом?
(1) граф
T является деревом, если он не содержит циклов и имеет n-1 ребер
(2) граф
T является деревом, если он связан и имеет n-1 ребер
(3) граф
T является деревом, если он связан и каждое его дерево является мостом
(4) граф
T является деревом, если вершины его соединены ровно одной цепью Что называется проектом?
(1) всякий намеченный комплекс работ, необходимых для достижения некоторой цели
(2) всякий граф
(3) всякий направленный граф
(4) всякий ориентированный граф
Что называется совершенным паросочетанием в двудольном графе
G(V1V2)?
(1) совершенным паросочетанием из
V1 в V2 в двудольном графе G(V1,V2) называется взаимно однозначное соответствие между вершинами из V1 и подмножеством вершин из V2, обладающее тем свойством, что соответствующие вершины соединены ребром
(2) совершенным паросочетанием из
V1 в V2 в двудольном графе G(V1V2) называется (V(G),E(G), где V(G) - непустое конечное множество элементов, называемых вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых ребрами. Употребление слова "семейство" говорит о том, что допускаются кратные ребра. Будем называть V(G) множеством вершин, а E(G) - семейством ребер графа G. О каждом ребре вида {v,w} говорят, что оно соединяет вершины v и w. Каждая петля {v,v} соединяет вершину v саму с собой
(3) совершенным паросочетанием из
V1 в V2 в двудольном графе G(V1,V2) называется D(V(D),A(D), где V(D) непустое конечное множество элементов, называемых вершинами, а A(D) - конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами). Дуга, у которой вершина v является первым элементом, а вершина v в w. Заметим, что дуги {v,w} и {w,v} различны. Хотя графы и орграфы – различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположно ориентированные дуги
(4) допустим, что множество вершин графа можно разбить на два непересекающихся подмножества
V1 и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-либо вершиной из V2 графа G, тогда совершенным паросочетанием из в называется взаимно однозначное соответствие между вершинами из V1 и подмножеством вершин из V2 Если
Е - непустое конечное множество и ϕ=(S1,...,Sm) - семейство непустых его подмножеств, то что называется трансверсалью для ϕ?
(1) если
Е - непустое конечное множество и ϕ=(S1,...,Sm) - семейство непустых его подмножеств, трансверсалью для ϕ называется подмножество множества Е, состоящее из m элементов: по одному из каждого множества Si
(2) если
Е - непустое конечное множество и ϕ=(S1,...,Sm) - семейство обязательно различных непустых его подмножеств, трансверсалью для ϕ называется подмножество множества Е, состоящее из m элементов: по одному из каждого множества Si
(3) если
Е - непустое конечное множество и ϕ=(S1,...,Sm) - семейство не обязательно пустых его подмножеств, трансверсалью для ϕ называется подмножество множества Е, состоящее из m элементов: по одному из каждого множества Si
(4) если
Е - непустое конечное множество и ϕ=(S1,...,Sm) - семейство обязательно пустых его подмножеств, трансверсалью для ϕ называется подмножество множества Е, состоящее из m элементов: по одному из каждого множества Si Что такое сеть?
(1) cеть
N - это орграф, каждой дуге α которого приписано неотрицательное действительное число ψ(α), называемое ее пропускной способностью
(2) cеть представляет собой пару
D(ψ) где D - орграф, а ψ - функция, отображающая множество дуг орграфа D в множество неотрицательных действительных чисел
(3) cеть представляет собой пару
D(ψ) где D - орграф, а ψ - функция, отображающая множество дуг орграфа D в множество отрицательных действительных чисел
(4) допустим, что множество вершин графа можно разбить на два непересекающихся подмножества
V1 и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-либо вершиной из V2, тогда граф G называется сетью Можно получить несколько различных матриц смежности данного графа?
(1) да
(2) нет
(3) только для ориентированного графа
(4) только для графа, степени вершин которого равны 1
Какой граф называют плоским?
(1) изображенный на плоскости так, что никакие два его ребра (или, вернее, представляющие их кривые) геометрически не пересекаются нигде, кроме инцидентной им обоим вершины
(2) если его можно нарисовать на плоскости так, чтобы никакие два его ребра не имели других общих точек, кроме их общих вершин
(3) только ориентированные графы
(4) только граф, степени вершин которого равны 1
Что называется эйлеровым путем в графе?
(1) путь, содержащий все ребра графа
(2) путь, который можно нарисовать на плоскости так, чтобы никакие два его ребра не имели других общих точек, кроме общей вершины
(3) только ребра ориентированного графа
(4) путь, содержащий все ребра графа, степени смежных вершин которых равны 1
Что называется гамильтоновым путем в графе?
(1) путь, содержащий все ребра графа
(2) если граф можно нарисовать на плоскости так, чтобы никакие два его ребра не имели других общих точек, кроме их общей вершины, то это называют гамильтоновым путем в графе
(3) только ребра ориентированного графа
(4) замкнутая цепь, проходящая ровно один раз через каждую вершину графа
Какой граф называется бесконечным?
(1) бесконечным графом называется пара
V(G),E(G), где V(G) - бесконечное множество элементов, называемое вершинами, а E(G) - бесконечное семейство неупорядоченных пар элементов из V(G), называемых ребрами
(2) графом
G называется пара V(G),E(G), где V(G) - непустое конечное множество элементов, называемых вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых ребрами. Употребление слова "семейство" говорит о том, что допускаются кратные ребра. Будем называть V(G) множеством вершин, а E(G) - семейством ребер графа G. О каждом ребре вида {v,w} говорят, что оно соединяет вершины v и w. Каждая петля {v,v} соединяет вершину v саму с собой
(3) бесконечным графом
D называется пара V(D),A(D), где V(D) непустое конечное множество элементов, называемых вершинами, а A(D) - конечное семейство упорядоченных пар элементов из V(D) , называемых дугами (или ориентированными ребрами). Дуга, у которой вершина v является первым элементом, а вершина w - вторым, называется дугой из v в w(v,w). Заметим, что дуги (v,w) и (w,v) различны. Хотя графы и орграфы – существенно различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположно ориентированные дуги
(4) допустим, что множество вершин графа можно разбить на два непересекающихся подмножества
V1 и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-либо вершиной из V2, тогда G называем бесконечным графом Какой граф
G называется реберно k-раскрашиваемым?
(1) граф
G называется реберно k-раскрашиваемым, если его ребра можно раскрасить k-красками таким образом, что никакие два смежных ребра не окажутся одного цвета
(2) граф
G называется реберно k-раскрашиваемым, если его можно задать парой V(G),E(G) , где V(G) - непустое конечное множество элементов, называемых вершинами, а - E(G) конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых ребрами. Употребление слова "семейство" говорит о том, что допускаются кратные ребра. Будем называть V(G) множеством вершин, а V(G) - семейством ребер графа G. О каждом ребре вида {v,w} говорят, что оно соединяет вершины v и w. Каждая петля {v,v} соединяет вершину v саму с собой
(3) граф
G называется реберно k- раскрашиваемым, если его можно задать бесконечным D(V(D),A(D)) графом D, где V(D), непустое конечное множество элементов, называемых вершинами, а A(D) - конечное семейство упорядоченных пар элементов из V(D) , называемых дугами (или ориентированными ребрами). Дуга, у которой вершина v является первым элементом, а вершина w - вторым, называется дугой из v в w(v,w). Заметим, что дуги (v,w) и (w,v) различны. Хотя графы и орграфы – существенно различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположно ориентированные дуги
(4) допустим, что множество вершин графа можно разбить на два непересекающихся подмножества
V1 и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-либо вершиной из V2, тогда граф G называется реберно k-раскрашиваемым Какой граф
G называется k-раскрашиваемым?
(1) если его ребра можно раскрасить
k красками таким образом, что никакие два смежных ребра не окажутся одного цвета
(2) если его можно задать парой
(V(G), E(G)), где V(G) - непустое конечное множество элементов, называемых вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V(G) (необязательно различных), называемых ребрами. Употребление слова "семейство" говорит о том, что допускаются кратные ребра. Будем называть V(G) множеством вершин, а E(G) - семейством ребер графа G. О каждом ребре вида {v,w} говорят, что оно соединяет вершины v и w. Каждая петля (v,v) соединяет вершину v саму с собой
(3) если его можно задать бесконечным графом
D(V(D),A(D)), где V(D) непустое конечное множество элементов, называемых вершинами, а A(D) - конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами). Дуга, у которой вершина v является первым элементом, а вершина w - вторым, называется дугой из v в w(v,w). Заметим, что дуги (v,w) и (w,v) различны. Хотя графы и орграфы – различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположно ориентированные дуги
(4) пусть граф
G не имеет петель; тогда G называется k-раскрашиваемым, если каждой его вершине можно приписать один из k цветов таким образом, чтобы никакие две смежные вершины не оказались одного цвета Какие орграфы называются простыми?
(1) орграфы, не содержащие петель и кратных ребер, называются простыми
(2) орграф называется простым, если он реберно
k-раскрашиваем
(3) орграф называется простым, если его можно задать бесконечным графом
D(V(D),A(D)), где V(D) непустое конечное множество элементов, называемых вершинами, а A(D) - конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами). Дуга, у которой вершина v является первым элементом, а вершина w - вторым, называется дугой из v в w (v,w). Заметим, что дуги (v,w) и (w,v) различны. Хотя графы и орграфы – различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположно ориентированные дуги
(4) орграф называется простым, если множество его вершин можно разбить на два непересекающихся подмножества
V1 и V2 так, что каждое ребро в орграфе соединяет какую-нибудь вершину из V1 с какой-либо вершиной из V1 Какой граф называется двудольным?
(1) если множество вершин графа можно разбить на два непересекающихся подмножества
V1 и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-либо вершиной из V2, тогда G называется двудольным графом
(2) в терминах раскраски вершин графа двумя цветами, скажем красным и синим, граф называется двудольным, если каждую его вершину можно окрасить красным или синим цветом так, чтобы любое ребро имело один конец красный, а другой - синий
(3) простой граф
G(V,G) называется двудольным, если он несвязный
(4) простой граф
G(V,G) называется двудольным, если он связный Что называется матрицей перехода?
(1) матрица перехода определяется как квадратная матрица, в которой каждая строка является вектором вероятностей
(2) матрица перехода определяется как прямоугольная матрица, в которой каждая строка является вектором вероятностей
(3) матрица перехода определяется как единичная матрица, в которой каждая строка является вектором вероятностей
(4) матрица перехода определяется как квадратная матрица, в которой каждая строка содержит только простые числа
Что нужно сделать, чтобы произвольный граф
G преобразовать в дерево?
(1) убрать циклы
(2) убрать мосты
(3) добавить циклы
(4) добавить мосты
Чему равна сумма чисел, стоящих в любой из строк матрицы инциденций графа
G?
(1) сумма чисел в каждой строке матрицы инциденций равна степени вершины, которую она характеризует
(2) сумма чисел в каждой строке матрицы инциденций равна рангу матрицы
(3) сумма чисел в каждой строке матрицы инциденций равна числу петель в графе
(4) сумма чисел в каждой строке матрицы инциденций равна числу компонент графа
Граф
G состоит из k компонент. Что нужно сделать, чтобы из заданного графа получить остовной лес?
(1) чтобы из такого графа получить остовной лес, нужно к каждой компоненте графа применить такую процедуру: в каждой компоненте графа удаление одного ребра, принадлежащего некоторому выбранному циклу, не нарушает связности оставшейся компоненты . Применим эту процедуру ко всем циклам. В результате получим дерево, связывающее все вершины компоненты, оно называется остовным деревом. А так как у нас было
k компонент, то получим остовной лес, состоящий из k остовных деревьев
(2) чтобы из такого графа получить остовной лес, нужно к каждой компоненте графа применить такую процедуру: в каждой компоненте графа удалить все циклы, не нарушая связности оставшейся компоненты. Применим эту процедуру ко всем циклам. В результате получим дерево, связывающее все вершины компоненты, оно называется остовным деревом. А так как у нас было
k компонент, то получим остовной лес, состоящий из k остовных деревьев
(3) чтобы из такого графа получить остовной лес, нужно к каждой компоненте графа применить такую процедуру: нужно получить из каждой компоненты графа
G остовное дерево, удаляя все мосты в каждой компоненте графа. В результате получим дерево, связывающие все вершины компоненты, оно называется остовным деревом. А так как у нас было k компонент, то получим остовной лес, состоящий из k остовных деревьев
(4) чтобы из такого графа получить остовной лес, нужно к каждой компоненте графа применить такую процедуру: получить из каждой компоненты графа
G остовное дерево, соединив все его компоненты мостами. В результате получим дерево, связывающее все вершины компоненты, оно называется остовным деревом. А так как у нас было k компонент, то получим остовной лес, состоящий из k остовных деревьев Какая работа называется фиктивной?
(1) работа, отражающая только зависимость одного мероприятия от другого, называется фиктивной. Такая работа имеет нулевую продолжительность (или нулевой расход ресурсов) и обозначается пунктирной стрелкой
(2) работа, отражающая только зависимость от истока орграфа
(3) работа, отражающая только зависимость одного стока орграфа
(4) это такая работа, которая имеет нулевую продолжительность (или нулевой расход ресурсов) и обозначается пунктирной стрелкой
Что называется латинским прямоугольником?
(1) латинским
(m×n)- прямоугольником называется (m×n) - матрица M=(mij), элементами которой являются целые числа, удовлетворяющие условиям (1) 1≤mij≤n, (2) все элементы в каждой строке и в каждом столбце различны. Заметим, что из условий (1) и (2) следует, что m≤n
(2) прямоугольная матрица, состоящая из реберно-хроматических чисел графа
G, называется латинским прямоугольником
(3) прямоугольная матрица, состоящая из степеней вершин графа
G, называется латинским прямоугольником
(4) прямоугольная матрица, состоящая из весов графа
G, называется латинским прямоугольником Что называется разрезом в сети?
(1) такое множество
A дуг орграфа D, которое обладает тем свойством, что любая простая орцепь из v в w проходит через дугу, принадлежащую A
(2) разрезом в сети является не что иное, как
vw - разделяющее множество соответствующего орграфа D
(3) разрезом в сети является не что иное, как функция, составляющая каждой дуге
α из D неотрицательное действительное число ϕ(α) (называемое потоком через α) таким образом , что ϕ(α)≤ψ(α) для любой дуги α
(4) разрезом в сети является
N=(D,ψ) Какой граф называется регулярным?
(1) если множество его вершин можно разбить на два непересекающихся подмножества
V1 и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-либо вершиной из V2, тогда G называем двудольным графом
(2) граф, у которого все вершины имеют одну и ту же степень, называется регулярным графом
(3) простой граф называется регулярным, если он несвязный
(4) простой граф
G(V,G) называется регулярным, если он связный Что называется перегородками в графе?
(1) ребра, соединяющие циклы
(2) мосты, соединяющие циклы
(3) бесконечная грань
(4) диаметр графа
Какой граф является эйлеровым или гамильтоновым графом?![files]()
(1)
G1 - эйлеров граф
(2)
G4 - гамильтонов граф
(3)
G2 - гамильтонов граф
(4)
G3 - эйлеров граф G - связный счетный граф, являющийся эйлеровым. Какими свойствами он обладает?
(1) в графе
G нет вершин нечетной степени
(2) для каждого конечного подграфа
H графа G бесконечный граф H G ребер графа H) имеет не более двух бесконечных связных компонент
(3) если, кроме того, степень любой вершины из
H четна, то H
(4) в графе
G нет вершин четной степени Что называется реберно-хроматическим числом графа
G?
(1) число висячих вершин
(2) число петель в графе
(3) максимальная степень в графе
(4) если граф
G реберно k-раскрашиваем, но не является реберно (k-1)-раскрашиваемым, то k называется хроматическим числом графа G Если наибольшая степень графа равна
(ρ+1)G, скольки-раскрашиваемым является граф?
(1) если наибольшая из степеней вершин графа
G равна (ρ+1), то этот граф ρ-раскрашиваем
(2) если наибольшая из степеней вершин графа
G равна (ρ+1), то этот граф (ρ+3)-раскрашиваем
(3) если наибольшая из степеней вершин графа
G равна (ρ+1), то этот граф (ρ-2)-раскрашиваем
(4) если наибольшая из степеней вершин графа
G равна (ρ+1), то этот граф (ρ+2)-раскрашиваем Какой орграф
D называется гамильтоновым?
(1) орграф
D называется гамильтоновым, если в нем существует орцикл, включающий каждую его вершину
(2) связный орграф называется гамильтоновым, если в нем существует замкнутая орцепь, содержащая каждое его ребро
(3) орграф называется гамильтоновым, если в нем существует орцикл, включающий каждое его ребро
Что называется орграфом?
(1) орграфом
D называется пара V(D),A(D), где V(D) непустое конечное множество элементов, называемых вершинами, а A(D) - конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами)
(2) орграфом
G называется пара V(G),E(G), где V(G) - непустое конечное множество элементов, называемых вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V(G),E(G) V(G) (не обязательно различных), называемых ребрами
(3) орграфом называется такая пара, что
E⊆V×V. Элементы множества E для орграфа называются дугами. Дуга в орграфе изображается линией со стрелкой, указывающей ориентацию дуги, т.е. направление от начала к концу
(4) полный ориентированный граф
Что называется дискретной стационарной цепью Маркова?
(1) если каждый элемент
pij из P рассматривать как вероятность перехода из позиции Ei в позицию Ej, а x - как начальный вектор вероятностей, то придем к классическому понятию дискретной стационарной цепи Маркова
(2) если каждый элемент
pij из P рассматривать как вероятность перехода из позиции Ei в позицию Ej, а x - как конечный вектор вероятностей, то придем к классическому понятию дискретной стационарной цепи Маркова
(3) если каждый элемент
pij из P рассматривать как вероятность перехода из позиции Ei в позицию Ej, а x - как нулевой вектор вероятностей, то придем к классическому понятию дискретной стационарной цепи Маркова
(4) если каждый элемент
pij из P рассматривать как вероятность перехода из позиции Ei в позицию Ej, а x - как вектор с отрицательными компонентами, то придем к классическому понятию дискретной стационарной цепи Маркова Из чего состоит остовной лес?
(1) из остовных деревьев
(2) из компонент, в которых нет циклов
(3) из компонент, в которых нет мостов
(4) остовной лес - это частный случай остовного дерева
Граф, который может быть изображен проволочной моделью куба, =
(1) плоский
(2) эйлеров
(3) не плоский
Пусть ген
G p, а ген g - с вероятностью q. Чему равна вероятность унаследованных генов?
(1)
p+q=1
(2)
p-q=1
(3)
p-q=0
(4)
p*q=1 Что называют исходным событием в сетевом графике?
(1) событие, обозначающее начала процесса, получило название исходного события, которому присваивается нулевой номер
(2) событие, обозначающее конец процесса, получило название исходного события, которому присваивается нулевой номер
(3) событие, обозначающее текущее значение процесса, получило название исходного события, которому присваивается нулевой номер
(4) событие, обозначающее повторение процесса, получило название исходного события, которому присваивается нулевой номер
Можно ли получить двудольный граф соединением двух графов
Km,n=Nm+Nn?
(1) да, можно
(2) нет, нельзя
(3) нельзя, если
m≥n
(4) нельзя, если
m=n Чему равен словарный ранг матрицы?
(1) словарный ранг (0,1)-матрицы А равен минимальному числу
μ строк и столбцов, которые в совокупности содержат все единицы из А
(2) cловарный ранг (0,1)-матрицы А равен максимальному числу
μ строк и столбцов, которые в совокупности содержат все единицы из А
(3) cловарный ранг (0,1)-матрицы А равен минимальному числу
μ строк, которые в совокупности содержат все единицы из А
(4) cловарный ранг (0,1)-матрицы А равен минимальному числу
μ столбцов, которые в совокупности содержат все единицы из А Что называют величиной потока?
(1) cумма потоков через дуги, инцидентные
v, равна сумме потоков через дуги, инцидентные w
(2) cумма потоков через дуги, инцидентные
v, равна сумме потоков через дуги, инцидентные w, увеличенная на число вершин сети
(3) cумма потоков через дуги, инцидентные
v,
равна сумме потоков через дуги, инцидентные w, уменьшенная на число вершин сети
(4) cумма потоков через дуги, инцидентные
v,
равна сумме потоков через дуги, инцидентные w, поделенная на число вершин Что называется мостом графа?
(1) все ребра графа
(2) в графе
G называется мостом пара V(G),E(G) , где V(G) - непустое конечное множество элементов, называемых вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых V(G),E(G) ребрами
(3) такая пара, что
E⊆V×V. Элементы множества E для графа называются дугами
(4) ребро
{a,b} называется мостом графа G, если в графе, полученном после удаления из G ребра {a,b}, вершины a и b оказываются несвязными Какое выражение является формулой Эйлера (здесь
V - число вершин в графе, E - число ребер, а R - число граней)?
(1)
V-E+R=2
(2)
V-E+R=2+2E
(3)
3R≤2E
(4)
2E=20 Какой граф называется мультиграфом?
(1) граф, в котором не допускаются петли, но пары вершин могут соединяться более чем одним ребром. Эти ребра называются кратными, а граф – мультиграфом
(2) граф, в котором нет петель, но есть кратные ребра
(3) граф, в котором все вершины имеют четную степень
(4) граф, в котором все вершины имеют нечетную степень
Если в простом графе с
n(≥3) вершинами ρ(v)≥n/2 для любой вершины v, то каким является граф G?
(1) если в простом графе с
n(≥3) вершинами ρ(v)≥n/2 для любой вершины v, то граф G является гамильтоновым
(2) граф, в котором нет петель, но есть кратные ребра
(3) граф, в котором все вершины имеют четную степень
(4) граф, в котором все вершины имеют нечетную степень
Что называется бесконечным в одну сторону маршрутом в графе
G?
(1) бесконечным в одну сторону маршрутом в
G, с начальной вершиной v0, называется бесконечная последовательность ребер вида {v0,v1},{v1,v2}...
(2) бесконечным в одну сторону маршрутом в графе
G называют последовательность четных вершин
(3) бесконечным в одну сторону маршрутом в графе
G называют маршрут, в котором все вершины имеют четную степень
(4) бесконечным в одну сторону маршрутом в графе
G называют маршрут, в котором все вершины имеют нечетную степень Как можно изобразить полный граф с пятью вершинами и ребрами двух цветов, если в нем не найдется треугольника с одноцветными сторонами?
(1) если в полном графе с пятью вершинами и ребрами двух цветов не найдется треугольника с одноцветными сторонами, то граф можно изобразить в виде "пятиугольника" с красными сторонами и синими диагоналями
(2) если в полном графе с пятью вершинами и ребрами двух цветов не найдется треугольника с одноцветными сторонами, то граф можно изобразить в виде "пятиугольника" с синими сторонами и красными диагоналями
(3) если в полном графе с пятью вершинами и ребрами двух цветов не найдется треугольника с одноцветными сторонами, то граф можно изобразить в виде "пятиугольника" с зелеными сторонами и красными диагоналями
(4) если в полном графе с пятью вершинами и ребрами двух цветов не найдется треугольника с одноцветными сторонами, то граф можно изобразить в виде "пятиугольника" с красными сторонами и зелеными диагоналями
Когда карта
G является 2-раскрашиваемой?
(1) карта
G является 2-раскрашиваемой тогда и только тогда, когда G представляет собой эйлеров граф
(2) карта
G является 2-раскрашиваемой тогда и только тогда, когда G представляет собой гамильтонов граф
(3) карта
G является 2-раскрашиваемой тогда и только тогда, когда G представляет собой планарный граф
(4) карта
G является 2-раскрашиваемой тогда и только тогда, когда G представляет собой орграф Какой орграф называется турниром?
(1) турниром называется орграф, в котором любые две вершины соединены ровно одной дугой
(2) турниром называется орграф, в котором есть петли
(3) если в полном орграфе есть мосты
(4) турниром называется орграф, в котором все вершины являются источниками
Что называется вершинами графа?
(1) граф представляет собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек. Точки иначе называются вершинами
(2) граф представляет собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек. Отрезки иначе называются вершинами
(3) если граф представлен парой
V(G), E(G), где V(G) - непустое конечное множество элементов, называемых вершинами, а Е(G) - конечное семейство неупорядоченных пар элементов из V(G), называемых ребрами
(4) вершины представляют собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек. Точки и отрезки иначе называются вершинами
Что называется путем в ориентированном графе
D?
(1) путем в ориентированном графе
D от v1 до vn называется последовательность ориентированных дуг (ребер) (v1,v2),(v2,v3),...,(vn-1,vn), такая, что конец каждой предыдущей дуги (ребра) совпадает с началом следующей и ни одна дуга (ребро) не встречается более одного раза
(2) если существует замкнутая цепь, проходящая через каждую вершину орграфа, то такая цепь называется путем в орграфе
(3) если существует разомкнутая цепь, проходящая через все вершины орграфа степени единица, то такая цепь называется путем
(4) путем в ориентированном графе
D от v1 до vn называется последовательность ориентированных дуг (ребер) Какие представления деревьев правильны?
(1) представление с помощью матрицы смежности
(2) представление с помощью списков смежности
(3) представление с помощью списка ребер и кода Прюфера
(4) дерево задается перечислением пар
(vi,vj) или троек (vi,vj,uk), если дополнительно нужна нумерация ребер. Здесь vi,vj - вершины дерева Какие помеченные деревья называются изоморфными?
(1) два помеченных дерева называются изоморфными, если существует взаимно однозначная функция, отображающая множество вершин одного дерева на множество вершин другого, которая не только сохраняет смежность, но и переводит вершину с меткой в вершину с той же меткой
(2) два помеченных дерева называются изоморфными, если не существует взаимно однозначная функция, отображающая множество вершин одного дерева на множество вершин другого, которая не только сохраняет смежность, но и переводит вершину с меткой в вершину с той же меткой
(3) если существует разомкнутая цепь, проходящая через все вершины графов степени единица, то такие графы называются изоморфными
(4) два помеченных дерева называются изоморфными, если существует многозначная функция, отображающая множество вершин одного дерева на множество вершин другого, которая не только сохраняет смежность, но и переводит вершину с меткой в вершину с той же меткой
Как из связного графа получить остовное дерево?
(1) известно, что в связном графе
G удаление одного ребра, принадлежащего некоторому выбранному циклу, не нарушает связности оставшегося графа. Применим эту процедуру к одному из оставшихся циклов, и так до тех пор, пока не останется ни одного цикла. В результате получим дерево, связывающие все вершины графа, оно называется остовным деревом
(2) в связном графе
G удаление одного ребра, принадлежащего некоторому выбранному циклу, не нарушает связности оставшегося графа. Применим эту процедуру ко всем циклам. В результате получим дерево, связывающее все вершины графа, оно называется остовным деревом
(3) чтобы получить из графа
G остовное дерево, нужно удалить все мосты
(4) чтобы получить из графа
G остовное дерево, нужно соединить все его компоненты мостами С какими параметрами связана работа?
(1) работа, как элемент сетевого графика, связана с затратой времени и расходом ресурсов
(2) работа - это физический процесс
(3) работа - это вершина сетевого графика
(4) работа - это начало сетевого графика
Какой граф называется двудольным?
(1) бесконечный граф, все вершины которого имеют конечные степени
(2) если существует замкнутая цепь, проходящая через каждую вершину графа, то такой граф называется двудольным
(3) если существует разомкнутая цепь, проходящая через все вершины графа степени 1, то такой граф называется двудольным
(4) допустим, что множество вершин графа можно разбить на два непересекающихся подмножества
V1 и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-либо вершиной из V2, тогда G называем двудольным графом Что называется полустепенью исхода вершины
x?
(1) полустепень исхода вершины
x определяется как разность пропускных способностей дуг вида (x,z)
(2) полустепенью исхода
x называется число дуг из D вида (w,x)
(3) если
x вершина орграфа D, то полустепенью исхода x называют число дуг орграфа D, имеющих вид (x,w)
(4) полустепень исхода вершины
x определяется как сумма пропускных способностей дуг вида (x,z) Чему равна сумма чисел в любой строке или столбце матрицы смежности?
(1) степени соответствующей вершины
(2) не имеет никакого отношения к степеням вершин графа
(3) степени соответствующей вершины пустого графа
(4) степени соответствующей вершины регулярного графа
Какой граф называется планарным?
(1) граф, изоморфный плоскому графу
(2) граф, изображенный на плоскости так, что никакие два его ребра (или, вернее, представляющие их кривые) геометрически не пересекаются нигде, кроме инцидентной им обоим вершины
(3) если его можно нарисовать на плоскости так, чтобы никакие два его ребра не имели других общих точек, кроме их общей вершины
(4) если у него любые две вершины смежны
Что называется эйлеровой цепью?
(1) цепь, проходящая через каждое ребро графа
(2) цепь, проходящая через каждую вершину графа
(3) разомкнутая цепь, проходящая через все вершины графа степени 1
(4) разомкнутая цепь, проходящая через каждое ребро графа
Что называется гамильтоновой цепью?
(1) замкнутая цепь, проходящая через каждое ребро графа
(2) замкнутая цепь, проходящая через каждую вершину графа
(3) разомкнутая цепь, проходящая через все вершины графа степени 1
(4) разомкнутая цепь, проходящая через каждое ребро графа
Какой граф называется локально конечным?
(1) бесконечный граф, все вершины которого имеют конечные степени
(2) если существует замкнутая цепь, проходящая через каждую вершину графа, то такой граф называется локально конечным
(3) если существует разомкнутая цепь, проходящая через все вершины графа степени 1, то такой граф называется локально конечным
(4) если существует разомкнутая цепь, проходящая через каждое ребро графа, то такой граф называется локально конечным
Что называется хроматическим классом?
(1) бесконечный граф, все вершины которого имеют конечные степени
(2) если существует замкнутая цепь, проходящая через каждую вершину графа, то такая цепь называется хроматическим классом
(3) если существует разомкнутая цепь, проходящая через все вершины графа степени 1, то такая цепь называется хроматическим классом
(4) если граф
G реберно k-раскрашиваем, но не является реберно (k-1)-раскрашиваемым, то k называется хроматическим классом Какой граф
G называется k-хроматическим?
(1) бесконечный граф, все вершины которого имеют конечные степени
(2) если существует замкнутая цепь, проходящая через каждую вершину графа, то такая цепь называется хроматическим классом
(3) если существует разомкнутая цепь, проходящая через все вершины графа степени 1, то такая цепь называется хроматическим графом
(4) если граф
G k-раскрашиваем, но не является (k-1)-раскрашиваемым, то граф G называется k-хроматическим Какой орграф является связным, или слабо связным?
(1) орграф
D связен, или слабо связен, если он не может быть представлен в виде объединения двух различных орграфов (определенных обычным образом)
(2) если существует замкнутая орцепь, проходящая через каждую вершину орграфа, то такой орграф является связным или слабо связным
(3) если существует разомкнутая орцепь, проходящая через все вершины орграфа степени 1, то такой орграф является связным или слабо связным
(4) если граф
G реберно k-раскрашиваем, но не является реберно k-1-раскрашиваемым, то такой орграф является связным или слабо связным Что называется маршрутом в данном графе
G(V,Е)?
(1) маршрутом в данном графе
G называется конечная последовательность ребер вида {v0,v1},{v1,v2},...,{vm-1,vm} (обозначаемая также через v0→v1→v2→...→vm)
(2) маршрутом в графе
G(V,Е) называется цепь, если все ее ребра различны
(3) маршрутом в графе
G(V,Е) называется простая цепь, если все ее вершины висячие
(4) маршрутом в графе
G(V,Е) называется вершина с петлей Когда цепь Маркова неприводима?
(1) тогда и только тогда, когда ее ассоциированный орграф сильно связан
(2) тогда и только тогда, когда ее ассоциированный орграф слабо связан
(3) тогда и только тогда, когда ее ассоциированный орграф не связан
(4) тогда и только тогда, когда у нее нет ассоциированного орграфа
Сколько корневых вершин может быть у дерева?
(1) одна
(2) две
(3) нет корневых вершин
(4) столько, сколько вершин, для которых максимальное из расстояний до других вершин равно радиусу графа
Из какого графа нельзя выделить дерево, содержащее все вершины графа?
(1) из любого несвязного графа
(2) из графа, состоящего из четного числа компонент
(3) из пустого графа
Что называется циклическим рангом?
(1) число удаленных ребер при получении остовного дерева называется циклическим рангом
(2) число присоединенных ребер при получении остовного дерева называется циклическим рангом
(3) число присоединенных мостов при получении остовного дерева называется циклическим рангом
(4) число удаленных петель при получении остовного дерева называется циклическим рангом
Какая работа имеет нулевой расход ресурсов?
(1) фиктивная работа имеет нулевой расход ресурсов
(2) работа, отражающая только зависимость от истока орграфа, имеет нулевой расход ресурсов
(3) работа, отражающая только зависимость одного стока орграфа, имеет нулевой расход ресурсов
(4) такая работа, которая имеет нулевую продолжительность
Что называется латинским квадратом?
(1) если два графа имеют общую вершину или ребро, то их называют латинским квадратом
(2) квадратная матрица, образованная ребрами бесконечного
графа
G называется латинским квадратом
(3) квадратная матрица, образованная компонентами связного графа
G, называется латинским квадратом
(4) латинским
(m×n) - квадратом называется (m×n) - матрица M=(mij), элементами которой являются целые числа, удовлетворяющие условиям (1) 1≤mij≤n, (2) все элементы в каждой строке и в каждом столбце различны, если m=n Что называется матрицей инциденций?
(1) другой подход к изучению трансверсалей семейства
ϕ=(S1,...,Sm) непустых подмножеств множества E={e1,...,en} состоит в исследовании (m×n) - матрицы A=((aij), в которой aij=1 если ej∈Si и aij=0 в противном случае. Любую такую матрицу, все элементы которой равны 0 или 1, называют матрицей инциденций этого семейства
(2) другой подход к изучению трансверсалей семейства
ϕ=(S1,...,Sm) пустых подмножеств множества E={e1,...,en} состоит в исследовании (m×n)- матрицы A=((aij), в которой aij=1 если ej∈Si и aij=0 в противном случае. (Любую такую матрицу, все элементы которой равны 0 или 1, называют матрицей инциденций этого семейства)
(3) другой подход к изучению трансверсалей семейства
ϕ=(S1,...,Sm) непустых подмножеств множества E={e1,...,en} состоит в исследовании (m×m)- матрицы A=((aij), в которой aij=1 если ej∈Si и aij=0 в противном случае. Любую такую матрицу, все элементы которой равны 0 или 1, называют матрицей инциденций этого семейства
(4) другой подход к изучению трансверсалей семейства
ϕ=(S1,...,Sm) непустых подмножеств множества E={e1,...,en} состоит в исследовании (n×n)- матрицы A=((aij), в которой aij=1 если ej∈Si и aij=0 в противном случае. Любую такую матрицу, все элементы которой равны 0 или 1, называют матрицей инциденций этого семейства Что называется потоком через сеть
N?
(1) для данной сети
N=(D,ψ) поток определяется через N как функцию ϕ, составляющую каждой дуге α из D неотрицательное действительное число ϕ(α) (называемое потоком через α) таким образом , что ϕ(α)≤ψ(α) для любой дуги α; по отношению к сети (D,ϕ) полустепень исхода и полустепень захода любой вершины (отличной от v и w) равны между собой
(2) для данной сети
N=(D,ψ) поток определяется через N как функцию ϕ, составляющую каждой дуге α из D неотрицательное действительное число ϕ(α) (называемое потоком через α) таким образом , что ϕ(α)≤ψ(α) для любой дуги α; по отношению к сети (D,ϕ) полустепень исхода и полустепень захода любой вершины (отличной от v и w) неравны между собой
(3) для данной сети
N=(D,ψ) поток определяется через N как функцию ϕ, составляющую каждой дуге α из D неотрицательное действительное число ϕ(α) (называемое потоком через α) таким образом , что ϕ(α)≤ψ(α) для любой дуги α; по отношению к сети (D,ϕ) полустепень исхода больше полустепени захода
(4) для данной сети
N=(D,ψ) поток определяется через N как функция ϕ, составляющая каждой дуге α из D неотрицательное действительное число ϕ(α) (называемое потоком через α) таким образом , что ϕ(α)≤ψ(α) для любой дуги α; по отношению к сети (D,ϕ) полустепень исхода меньше полустепени захода любой вершины (отличной от v и w) Что называется каркасом графа
G?
(1) остов дерева
(2) остов
(3) простая цепь, если все ее вершины висячие
(4) вершина с петлей
Какие графы называются гомеоморфными?
(1) два графа гомеоморфны (или тождественны с точностью до вершин степени 2), если они оба могут быть получены из одного и того же графа "включением" в его ребра новых вершин степени 2
(2) два графа гомеоморфны, если они планарны
(3) два графа гомеоморфны, если они плоские
(4) два графа гомеоморфны, если они простые и плоские
Какой граф называется полуэйлеровым?
(1) если снять ограничение на замкнутость цепи, то граф называется полуэйлеровым, при этом каждый эйлеров граф будет полуэйлеровым
(2) связный граф
G будет полуэйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро
(3) связный граф
G называется полуэйлеровым, если существует замкнутая цепь, проходящая через каждую его вершину
(4) эйлеровым графом
G называется граф, ограниченный простым циклом и не содержащий других циклов Какой граф называется полугамильтоновым?
(1) если снять ограничение на замкнутость цепи, то граф называется полугамильтоновым, при этом каждый гамильтонов граф будет полугамильтоновым
(2) связный граф
G будет полугамильтоновым, если существует замкнутая цепь, проходящая через каждую его вершину
(3) связный граф
G называется полугамильтоновым, если существует замкнутая цепь, проходящая через каждое его ребро
(4) гамильтоновым графом
G называется граф, ограниченный простым циклом и не содержащий внутри других циклов Какими свойствами обладает
G - связный счетный граф, являющийся полуэйлеровым, но не эйлеровым?
(1)
G содержит либо не более одной вершины нечетной степени, либо не менее одной вершины бесконечной степени
(2) для каждого конечного подграфа
H графа G бесконечный граф G
(3) связный граф
G содержит столько компонент, сколько он имеет вершин
(4) связный граф
G ограничен простым циклом и не содержащим внутри других циклов Какие треугольники называются сцепленными?
(1) если два треугольника имеют общую вершину или ребро
(2) треугольники, образованные ребрами бесконечного
графа
G
(3) треугольники, образованные компонентами связного графа
G
(4) треугольники, образованные мостами связного графа
G Как определяем географическую карту?
(1) удобно определить карту, как связный плоский граф, не содержащий мостов. Заметим, что при таком определении карты не исключаем петель или кратных ребер
(2) удобно определить карту, как полный граф, не содержащий мостов. Заметим, что при таком определении карты не исключаем петель или кратных ребер
(3) удобно определить карту, как полный граф четной степени, не содержащий мостов. Заметим, что при таком определении карты не исключаем петель или кратных ребер
(4) удобно определить карту, как полный граф нечетной степени, не содержащий мостов. Заметим, что при таком определении карты не исключаем петель или кратных ребер
Что называют источником орграфа
D?
(1) вершину, у которой полустепень захода равна нулю
(2) называют вершину, у которой полустепень исхода равна нулю
(3) компоненты связного орграфа
(4) вершины с максимальной степенью
Что называется ориентированным полным графом?
(1) полным ориентированным графом называется граф, каждая пара вершин которого соединена в точности одним ориентированным ребром
(2) полным ориентированным графом называется граф с неориентированными ребрами
(3) полным ориентированным графом называется граф, у которого число вершин строго равно числу ребер
(4) полным ориентированным графом называется граф, во всех вершинах которого имеются петли
Что называется источником в орграфе?
(1) вершина, степень выхода которой положительна, а степень входа равна 0
(2) вершина, степень входа которой положительна, а степень выхода равна 0
(3) вершина, степень входа которой положительна, а степень выхода отрицательна
(4) вершина, у которой и степень входа и степень выхода равны 0
Расстоянием
d(vx,vy) между вершинами графа G называем длину кратчайшего пути, их соединяющего. Наибольшее из таких d(vx,vy) называем диаметром G, наименьшее – радиусом. Может ли у какой – то вершины дерева максимальное из расстояний до других вершин равняться радиусу?
(1) да
(2) нет
(3) для корневых вершин
(4) для листьев дерева
Сколько получится кусков бумаги, если первоначально имелось
m кусков, некоторые из кусков разрезали на n частей, а всего было разрезано k кусков?
(1)
m+(n-1)k
(2)
m+(n+1)k
(3)
m-(n-1)k
(4)
m+(n-1)/k Какой граф описывает ситуацию случая кровного родства ?
(1) граф является деревом
(2) граф не является деревом, так как его вершины слипаются
(3) граф является остовом
(4) граф является каркасом
Что называется событиями первого ранга?
(1) события, которые не имеют входящих в них работ
(2) события, которые не имеют четного количества входящих в них работ
(3) события, которые имеют нечетное количество входящих в них работ
(4) события, которые имеют входящую в них работу-петлю
Можно ли операции объединения и соединения распространить на любое конечное число графов?
(1) да
(2) нет
(3) да, только на четное число графов
(4) да, только на нечетное число графов
Когда два семейства непустых подмножеств имеют общую трансверсаль?
(1) пусть ![files]()
Е - непустое конечное множество , а ϕ=(S1,...,Sm) и τ=(T1,...,Tm) - два семейства его непустых подмножеств. Тогда ϕ и τ имеют общую трансверсаль в том и только в том случае , если для всех подмножеств A и B множества {1,...,m}
(2) пусть ![files]()
Е - непустое конечное множество , а ϕ=(S1,...,Sm) и τ=(T1,...,Tm) - два семейства его непустых подмножеств. Тогда ϕ и τ имеют общую трансверсаль в том и только в том случае , если для всех подмножеств A и B множества {1,...,m}
(3) пусть ![files]()
Е - непустое конечное множество , а ϕ=(S1,...,Sm) и τ=(T1,...,Tm) - два семейства его непустых подмножеств. Тогда ϕ и τ имеют общую трансверсаль в том и только в том случае , если для всех подмножеств A и B множества {1,...,m}
(4) пусть ![files]()
Е - непустое конечное множество , а ϕ=(S1,...,Sm) и τ=(T1,...,Tm) - два семейства его непустых подмножеств. Тогда ϕ и τ имеют общую трансверсаль в том и только в том случае , если для всех подмножеств A и B множества {1,...,m}
Что называется пропускной способностью разреза?
(1) сумма пропускных способностей, принадлежащих ему дуг
(2) сумма пропускных способностей, не принадлежащих ему дуг
(3) сумма степеней вершин данной сети
(4) сумма всех ребер, принадлежащих этому разрезу
Что называется лесом?
(1) полный ориентированный граф, каждая пара вершин которого соединена в точности одним ориентированным ребром
(2) полный ориентированный граф с неориентированными ребрами
(3) ориентированный граф, у которого число вершин строго равно числу ребер
(4) несвязный граф, представляющий объединение деревьев
Какие грани в графе называются соседними?
(1) две грани в графе, если они имеют одну общую вершину
(2) две грани, если они ограничены неориентированными ребрами
(3) две грани, если число их вершин строго равно числу ребер
(4) две грани, если их границы имеют хотя бы одно общее ребро
Может ли связный граф обладать эйлеровым путем, если
va и vb - единственные нечетные его вершины?
(1) если граф
G связный и va и vb единственные нечетные вершины его, то граф G обладает эйлеровым путем с концами va и vb
(2) граф обладает эйлеровым путем, если его грани ограничены неориентированными ребрами
(3) граф обладает эйлеровым путем, если у него число вершин строго равно числу ребер
(4) граф обладает эйлеровым путем, если он имеет бесконечную грань
Каким является граф
N1?
(1) вырожденным гамильтоновым
(2) мультиграфом
(3) Эйлеровым
(4) полуэйлеровым
Что называется бесконечным в обе стороны маршрутом в графе
G?
(1) бесконечная последовательность ребер вида
...,{v-2,v-1},{v-1,v0},{v0,v-1},{v1,v2},...
(2) все маршруты мультиграфа
(3) все маршруты эйлерова графа
(4) все маршруты полуэйлерова графа
Сколько одноцветных ребер имеет каждая вершина минимально у полного графа с шестью или более вершинами и ребрами двух цветов?
(1) любая вершина полного графа с шестью или более вершинами и ребрами двух цветов принадлежит, по меньшей мере, трем ребрам одного цвета
(2) имеет минимум два одноцветных ребра
(3) имеет минимум одно ребро
(4) не имеет ребер вообще
Что называют жордановой кривой?
(1) жордановой кривой на плоскости называется непрерывная кривая, не имеющая самопересечений
(2) жордановой кривой называют жорданову дугу
(3) жордановой кривой называют замкнутую кривую на плоскости
(4) жордановой кривой называют самопересекающуюся кривую на плоскости
Может ли быть турнир полугамильтонов?
(1) всякий турнир полугамильтонов
(2) турниры не могут быть полугамильтоновыми
(3) если турнир имеет меньше четырех вершин, то утверждение, очевидно, верно
(4) если турнир является мостом
Что называется степенью вершины графа?
(1) степенью вершины называется число ребер графа, которым принадлежит эта вершина
(2) степенью вершины называется число вершин в графе
(3) степенью вершины называется число ребер и вершин графа
(4) степенью или валентностью вершины
v графа G называется число ребер, инцидентных v Что называется вектором вероятностей?
(1) вектор-строка, все компоненты вектора неотрицательны и дают в сумме единицу
(2) вектор-строка, все компоненты вектора отрицательны и дают в сумме минус единицу
(3) вектор-строка, все компоненты вектора неотрицательны и дают в сумме нуль
(4) вектор-строка, все компоненты вектора отрицательны и дают в сумме нуль
Пусть задано дерево с пронумерованными вершинами. Спрашивается: сколько существует таких разных деревьев?
(1) деревьев с
n пронумерованными вершинами ровно столько, сколько можно образовать последовательностей вида (v1,v2,...,vn-2) длины n-2, элементы которых выбираются из элементов множества M={1,2,3,...,n-1,n}
(2) деревьев с
n пронумерованными вершинами ровно столько, сколько можно образовать последовательностей вида (v1,v2,...,vn-2) длины n-2, элементы которых выбираются из элементов множества vi∈M
(3) деревьев с
n пронумерованными вершинами ровно столько, сколько можно образовать последовательностей вида (v1,v2,...,vn-2) длины 10
(4) деревьев с
n пронумерованными вершинами ровно столько, сколько можно образовать последовательностей вида (v1,v2,...,vn-2) длины n-2, элементы которых выбираются из элементов множества vi∈5 Чему равна сумма чисел, стоящих в любом из столбцов матрицы инциденций?
(1) сумма чисел в каждом столбце матрицы инциденций равна степени вершины, которую он характеризует
(2) сумма чисел в каждом столбце матрицы инциденций равна рангу матрицы
(3) сумма чисел в каждом столбце матрицы инциденций равна числу петель в графе
(4) сумма чисел в каждом столбце матрицы инциденций равна числу компонент графа
Как из связного графа получить каркас?
(1) известно, что в связном графе
G удаление одного ребра, принадлежащего некоторому выбранному циклу, не нарушает связности оставшегося графа. Применим эту процедуру к одному из оставшихся циклов, и так до тех пор, пока не останется ни одного цикла. В результате получим дерево, связывающее все вершины графа, оно называется каркасом
(2) в связном графе
G удаление одного ребра, принадлежащего некоторому выбранному циклу, не нарушает связности оставшегося графа. Применим эту процедуру ко всем циклам. В результате получим дерево, связывающее все вершины графа, оно называется каркасом
(3) чтобы получить из графа
G каркас, нужно удалить все мосты
(4) чтобы получить из графа
G каркас, нужно соединить все его компоненты мостами Как изображается работа на сетевом графике?
(1) на сетевом графике работа изображается стрелкой, над которой проставляется ее продолжительность или затрачиваемые ресурсы или то и другое одновременно
(2) на сетевом графике работа изображается вершиной
(3) на сетевом графике работа изображается висячей вершиной
(4) на сетевом графике работа изображается петлей
Какой граф называется полным двудольным графом?
(1) если в графе все вершины имеют счетную степень, то такой граф называется двудольным
(2) если граф имеет четное число циклов, то такой граф называется полным двудольным графом
(3) если граф имеет четное число мостов, то такой граф называется полным двудольным графом
(4) следует подчеркнуть, что в двудольном графе совсем не обязательно каждая вершина из
V1 соединена с каждой вершиной из V2; если же это так и если при этом граф G простой, то он называется полным двудольным графом и обычно обозначается Km,n, где m,n - число вершин, соответственно, в V1 и V2 Что называется частичной трансверсалью для
ϕ?
(1) трансверсаль произвольного подсемейства семейства
ϕ будем называть частичной трансверсалью для ϕ
(2) трансверсаль произвольного подсемейства семейства
Е будем называть частичной трансверсалью для ϕ
(3) трансверсаль произвольного подсемейства семейства
ϕ∩E будем называть частичной трансверсалью для ϕ
(4) трансверсаль произвольного подсемейства семейства
ϕ∪E будем называть частичной трансверсалью для ϕ Что называется полустепенью захода вершины
x?
(1) если в графе все вершины имеют счетную степень, то эта степень называется полустепенью захода
(2) если
x вершина орграфа D, то полустепенью захода x называют число дуг орграфа D, имеющих вид (x,w)
(3) полустепень захода вершины
x определяется как сумма пропускных способностей дуг вида (x,z)
(4) полустепенью захода
x называется число дуг из D вида (w,x) Что называется обхватом графа?
(1) длина его кратчайшего цикла
(2) число вершин в графе
(3) число ребер и вершин графа
(4) его радиус
Что называют гранью в плоском представлении графа?
(1) обхват графа
(2) часть плоскости, ограниченная простым циклом и не содержащая внутри других циклов
(3) его дополнение
(4) его радиус
Какой граф называется эйлеровым графом?
(1) связный граф
G, если существует замкнутая цепь, проходящая через каждое его ребро
(2) граф, ограниченный простым циклом и не содержащий других циклов
(3) граф
G, содержащий его дополнение
(4) связный граф
G, если существует замкнутая цепь, проходящая через каждую его вершину Какой граф называется гамильтоновым графом?
(1) связный граф
G, если существует замкнутая цепь, проходящая через каждую вершину ровно один раз
(2) граф, ограниченный простым циклом и не содержащий внутри других цикло
(3) граф, содержащий его дополнение
(4) связный граф
G, если существует замкнутая цепь, проходящая через каждую его четную вершину Какой граф называется локально счетным бесконечным графом?
(1) граф, все вершины которого имеют счетную степень. Под счетным множеством здесь и в дальнейшем понимается бесконечное множество, допускающее взаимно однозначное отображение на множество натуральных чисел
(2) граф, ограниченный простым циклом и не содержащим внутри других циклов
(3) граф, содержащий его дополнение
(4) связный граф
G называется локально счетным бесконечным, если существует замкнутая цепь, проходящая через каждую его четную вершину Что называется хроматическим индексом?
(1) если в графе все вершины имеют счетную степень, то эта степень называется хроматическим индексом
(2) число циклов графа
(3) число мостов графа
(4) если граф
G реберно k-раскрашиваем, но не является реберно (k-1)-раскрашиваемым, то k называется хроматическим индексом Что называется хроматическим числом графа?
(1) если в графе все вершины имеют счетную степень, то эта степень называется хроматическим числом графа
(2) число циклов графа
(3) число мостов графа
(4) если граф
G является k-раскрашиваемым, но не является (k-1)-раскрашиваемым, назовем его k-хроматическим, а число k назовем хроматическим числом графа G и обозначим через χ(G) Какой орграф называется эйлеровым?
(1) связный орграф
D называется эйлеровым, если в нем существует замкнутая орцепь, содержащая каждую его дугу
(2) орграф
D называется эйлеровым, если в нем существует орцикл, включающий каждую его вершину
(3) орграф, содержащий простую орцепь, проходящую через каждую вершину, называется эйлеровым
(4) пусть
D - сильно связный орграф, имеющий n вершин. Если и для любой его вершины v, то D является эйлеровым орграфом Какой граф называется регулярным?
(1) граф, у которого все вершины имеют одну и ту же степень
(2) граф называется регулярным, если у него число вершин равно числу ребер
(3) граф называется регулярным, если он имеет только висячие вершины
(4) граф называется регулярным, если он не имеет петель
Что называют цепью Маркова (или просто цепью)?
(1) пару
(P,x), где P есть (n×n) - матрица перехода, а x есть (1×n) - вектор-строка
(2) пару
(P,x), где P есть (n×n) - матрица возврата, а x есть (1×n) - вектор-строка
(3) пару
(P,x), где P есть прямоугольная - матрица возврата, а x есть (1×n) - вектор-строка
(4) пару
(P,x), где P есть прямоугольная - матрица перехода, а x есть (1×n) - вектор-строка Можно ли построить дерево, используя множество целых чисел в качестве вершин графа?
(1) можно построить дерево, вершины которого взяты из множества целых чисел
(2) можно построить дерево, вершины которого взяты из множества простых чисел
(3) можно построить столько деревьев с
n вершинами, сколько последовательностей вида (v1,v2,...,vn-2) длины n-2 , элементы которых выбираются из элементов множества M={1,2,3,...,n-1,n}
(4) можно построить столько деревьев с вершинами сколько последовательностей вида
(v1,v2,...,vn-2) длины n-2 , элементы которых выбираются из элементов множества простых чисел мощностью n Сколько матчей необходимо провести для того, чтобы выявить по олимпийской системе обладателя кубка среди 147 команд?
(1) 146
(2) 145
(3) 100
(4) 172
Что называется цикломатическим числом?
(1) число удаленных ребер при получении остовного дерева
(2) циклический ранг
(3) число присоединенных ребер при получении остовного дерева
(4) число удаленных петель при получении остовного дерева
Что в сетевом графике называется событием?
(1) начальная и конечная точки работы, то есть начало и окончание некоторого мероприятия
(2) все вершины сетевого графика
(3) все вершины четной степени сетевого графика
(4) все вершины нечетной степени сетевого графика
Можно ли латинский прямоугольник расширить до латинского квадрата?
(1) да, если взять
m=n и выполнить условие 1≤mij≤n
(2) нет
(3) да, если взять
m≥n и выполнить условие 1≤mij≤n
(4) да, если взять
m≥n и выполнить условие 1≥mij≥n Какая дуга в сети называется насыщенной?
(1) дуга
α, для которой ϕ(α)=ψ(α), в сети N=(D,ψ)
(2) дуга
α, для которой ϕ(α)≠ψ(α), в сети N=(D,ψ)
(3) дуга
α, для которой ϕ(α)≤ψ(α), в сети N=(D,ψ)
(4) дуга
α, для которой ϕ(α)≥ψ(α), в сети N=(D,ψ) Какой граф называется регулярным степени
r?
(1) граф, у которого все вершины имеют одну и ту же степень
r
(2) если у него число вершин равно числу ребер
(3) если он имеет только висячие вершины
(4) если он не имеет петель
Какой граф называется максимально плоским?
(1) если невозможно добавить к нему ни одного ребра так, чтобы полученный граф был плоским
(2) триангулированный граф
(3) если он имеет только висячие вершины
(4) если он не имеет петель
Какой граф обладает эйлеровым циклом?
(1) эйлеров граф
(2) триангулированный граф
(3) если граф
G связный и все его вершины четные, то он обладает эйлеровым циклом
(4) если в графе существует замкнутая цепь, проходящая через каждое его ребро, он называется эйлеровым циклом
Какой граф обладает гамильтоновым циклом?
(1) гамильтонов граф
(2) триангулированный граф
(3) если граф
G связный и все его вершины четные, то он обладает гамильтоновым циклом
(4) если в графе существует замкнутая цепь, проходящая через каждое его ребро, то она называется гамильтоновым циклом
При каких условиях счетный граф планарен?
(1)
G - счетный граф, каждый конечный подграф которого планарен, тогда и G планарен
(2) триангулированный граф планарен
(3) если граф
G связный и все его вершины четные, то он планарен
(4) если в графе существует замкнутая цепь, проходящая через каждое его ребро, то граф планарен
Сколько несцепленных треугольников с одноцветными сторонами найдется в полном графе с восемью вершинами, ребра которого окрашены в два цвета?
(1) в полном графе с восемью вершинами, ребра которого окрашены в два цвета, обязательно найдутся два треугольника с одноцветными сторонами, которые не являются сцепленными
(2) в полном графе с восемью вершинами, ребра которого окрашены в два цвета, обязательно найдутся три треугольника с одноцветными сторонами, которые не являются сцепленными
(3) в полном графе с восемью вершинами, ребра которого окрашены в два цвета, обязательно найдутся четыре треугольника с одноцветными сторонами, которые не являются сцепленными
(4) в полном графе с восемью вершинами, ребра которого окрашены в два цвета, обязательно найдутся пять треугольников с одноцветными сторонами, которые не являются сцепленными
Какую карту называют
k-раскрашиваемой?
(1) назовем карту
k-раскрашиваемой, если ее грани можно раскрасить k красками так, чтобы никакие две смежные грани, то есть грани, границы которых имеют общее ребро, не были одного цвета
(2) назовем карту
k-раскрашиваемой, если ее грани можно раскрасить k красками так, чтобы никакие два смежных ребра не были одного цвета
(3) назовем карту
k-раскрашиваемой, если ее грани можно раскрасить k красками так, чтобы ее смежные ребра были одного цвета
(4) назовем карту
k-раскрашиваемой, если она имеет k граней Что называют стоком орграфа?
(1) стоком орграфа
D называют вершину, у которой полустепень исхода равна нулю
(2) стоком орграфа
D называют вершину, у которой полустепень захода равна нулю
(3) стоком орграфа
D называют вершины, которые не являются сцепленными
(4) стоком орграфа
D называют вершины, которые являются сцепленными Что называется путем от
v1 до v2 в графе?
(1) путем от
v1 до v2 в графе называется такая последовательность ребер, ведущая от v1 к v2, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза
(2) путем от
v1 до v2 в графе называется последовательность вершин от v1 до v2
(3) путем в графе называется число его ребер
(4) путем в графе называется петля висячей вершины
Что называется стоком в орграфе?
(1) вершина, степень входа которой положительна, а степень выхода равна 0
(2) эргодическое состояние цепи Маркова
(3) эргодическая цепь Маркова
(4) вершина, у которой и степень входа и степень выхода равны 0
Любое дерево имеет либо одну, либо две корневые вершины. Как корневые вершины дерева расположены относительно друг друга?
(1) корневые вершины – смежные
(2) корневые вершины не могут быть смежными
(3) корневые вершины расположены на расстояние диаметра
(4) корневые вершины расположены на расстоянии радиуса
Существует ли граф с шестью вершинами, степени которых 2, 3, 3, 4, 4, 4?
(1) существует
(2) не существует
(3) в графе должно быть минимум четыре вершины
(4) в графе должно быть минимум две вершины
Каким графом является сетевой график?
(1) граф, не содержащий циклов и имеющий только один исток и только один сток, называется направленным графом. Сетевой график есть ориентированный связный асимметрический граф с одним истоком, одним стоком и без циклов, то есть это направленный граф
(2) сетевой график есть ориентированный связный асимметрический граф с одним истоком, одним стоком и без циклов, то есть это направленный граф
(3) сетевой график есть не ориентированный связный асимметрический граф и без циклов, то есть это направленный граф
(4) сетевой график есть ориентированный связный асимметрический граф с одним истоком, одним стоком и с циклами, то есть это направленный граф
Операции объединения и соединения графов коммутативны и ассоциативны?
(1) да, операции объединения и соединения коммутативны и ассоциативны
(2) нет, операции объединения и соединения не коммутативны и не ассоциативны
(3) операции объединения и соединения графов коммутативны, но не ассоциативны
(4) операции объединения и соединения графов не коммутативны, но ассоциативны
Предположим, что
E={1,2,3,4,5,6}, а S1=S2={1,2},S3=S4={2,3},S5={1,4,5,6} Имеет ли семейство а ϕ=(S1,...,S5) трансверсаль?
(1) да
(2) нет, так как здесь невозможно найти пять различных элементов из
Е - по одному из каждого подмножества Si
(3) да, если заменить
Si
(4) да, если заменить
Si и Е Может ли в сети величина любого максимального потока быть равна пропускной способности любого минимального разреза?
(1) во всякой сети величина любого максимального потока равна пропускной способности любого минимального разреза
(2) во всякой сети величина любого максимального потока меньше пропускной способности любого минимального разреза
(3) во всякой сети величина любого максимального потока больше пропускной способности любого минимального разреза
(4) данные величины несравнимы
Какой граф называется помеченным?
(1) если существует такая последовательность ребер, ведущая от
v1 к v2, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза
(2) если существует последовательность вершин от
v1 до v2
(3) если его ребра пронумерованы
(4) если все его вершины "помечены" целыми числами от 1 до n
Сколько бесконечных граней имеет всякое плоское представление графа?
(1) всякое плоское представление графа либо не имеет бесконечной грани, либо имеет в точности одну бесконечную грань
(2) бесконечное множество
(3) столько, сколько у него ребер
(4) столько, сколько у него вершин
Решение каждого ли лабиринта может быть найдено?
(1) безвыходных лабиринтов нет
(2) существует бесконечное множество решений
(3) да
(4) нет
Каким графом является плоское представление додекаэдра?
(1) гамильтоновым
(2) полуэйлеровым
(3) полугамильтоновым
(4) эйлеровым
Какой бесконечный граф называется эйлеровым?
(1) связный бесконечный граф
G, если в нем существует бесконечная в обе стороны цепь, содержащая каждое ребро графа G
(2) полуэйлеровый граф
(3) полугамильтоновый граф
(4) граф, обладающий бесконечной (двусторонней) эйлеровой цепью
Какое минимальное число вершин имеет полный граф, ребра которого окрашены в два цвета и который имеет хотя бы один треугольник с одинаковыми ребрами?
(1) в графе минимум шесть вершин
(2) в графе минимум пять вершин
(3) в графе минимум четыре вершин
(4) в графе минимум две вершины
Что называется замкнутой жордановой кривой?
(1) замкнутой жордановой кривой называется жорданова кривая, начало и конец которой совпадают
(2) замкнутой жордановой кривой называется жорданова дуга, начало и конец которой совпадают
(3) замкнутой жордановой кривой называют самопересекающуюся жорданову дугу
(4) замкнутой жордановой кривой называют диаметр графа
Может ли быть сильно связный турнир гамильтонов?
(1) всякий сильно связный турнир гамильтонов
(2) да, если сильно связный турнир
T с n вершинами содержит орциклы длины 3,4,...,n
(3) всякий сильно связный турнир не может быть гамильтоновым
(4) всякий сильно связный турнир гамильтонов, если каждая его вершина является истоком и стоком