Графы и их применение

Внимание !
Вопросы к тесту выложены исключительно в ознакомительных целях: количество вопросов может не совпадать с действительным, актуальность не поддерживается,- за решением теста Welcome to the cashier!

---

Что называется степенью вершины графа?

степенью вершины называется число ребер графа, которым принадлежит эта вершина
степенью вершины называется число вершин в графе
степенью вершины называется число ребер и вершин графа
степенью или валентностью вершины vграфа G называется число ребер, инцидентных v



Что называется графом?

графом G называется пара V(G), E(G), где V(G) - непустое конечное множество элементов, называемых, вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых ребрами
графом G называется V(G)- непустое конечное множество элементов, называемых вершинами
графом Gназывается E(G)- конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых ребрами
граф представляет собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек
 

 
Что называется вершинами графа?

граф представляет собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек. Точки иначе называются вершинами
граф представляет собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек. Отрезки иначе называются вершинами
если граф представлен парой V(G), E(G), где V(G) - непустое конечное множество элементов, называемых вершинами, а Е(G) - конечное семейство неупорядоченных пар элементов из V(G), называемых ребрами
вершины представляют собой непустое множество точек и множество отрезков, оба конца которых принадлежат заданному множеству точек. Точки и отрезки иначе называются вершинами



Какой граф называется двудольным?

если множество вершин графа можно разбить на два непересекающихся подмножества V1 и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-либо вершиной из V2, тогда G называется двудольным графом
в терминах раскраски вершин графа двумя цветами, скажем красным и синим, граф называется двудольным, если каждую его вершину можно окрасить красным или синим цветом так, чтобы любое ребро имело один конец красный, а другой - синий
простой граф G(V,G) называется двудольным, если он несвязный
простой граф G(V,G)называется двудольным, если он связный


 
Что называется маршрутом в данном графе G(V,Е)?

маршрутом в данном графе Gназывается конечная последовательность ребер вида {v0,v1},{v1,v2},...,{vm-1,vm} (обозначаемая также через v0 v1 v2 ... vm)
маршрутом в графе G(V,Е) называется цепь, если все ее ребра различны
маршрутом в графе G(V,Е) называется простая цепь, если все ее вершины висячие
маршрутом в графе G(V,Е) называется вершина с петлей



Какой граф называется регулярным?

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



Что называется орграфом?

орграфом D называется пара V(D),A(D), где V(D)непустое конечное множество элементов, называемых вершинами, а A(D) - конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами)
орграфом G называется пара V(G),E(G), где V(G) - непустое конечное множество элементов, называемых вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V(G),E(G) V(G) (не обязательно различных), называемых ребрами
орграфом называется такая пара, что E V×V. Элементы множества E для орграфа называются дугами. Дуга в орграфе изображается линией со стрелкой, указывающей ориентацию дуги, т.е. направление от начала к концу
полный ориентированный граф
 

 
 Что называется путем от v1 до v2 в графе?
 
путем от v1 до v2в графе называется такая последовательность ребер, ведущая от v1к v2, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза
путем от v1до v2 в графе называется последовательность вершин от v1 до v2
путем в графе называется число его ребер
путем в графе называется петля висячей вершины
 

 
Что называется ориентированным полным графом?

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



Чему равна сумма чисел в любой строке или столбце матрицы смежности?

степени соответствующей вершины
не имеет никакого отношения к степеням вершин графа
степени соответствующей вершины пустого графа
степени соответствующей вершины регулярного графа 



Что называется обхватом графа?

длина его кратчайшего цикла
число вершин в графе
число ребер и вершин графа
его радиус



Можно получить несколько различных матриц смежности данного графа?

да
нет
только для ориентированного графа
только для графа, степени вершин которого равны 1



Какой граф называется регулярным степени r?

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



Какой граф называется регулярным?

если множество его вершин можно разбить на два непересекающихся подмножества V1и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-либо вершиной из V2, тогда G называем двудольным графом
граф, у которого все вершины имеют одну и ту же степень, называется регулярным графом
простой граф называется регулярным, если он несвязный
простой граф G(V,G) называется регулярным, если он связный
 


Что называется каркасом графа G?
 
остов дерева
остов
простая цепь, если все ее вершины висячие
вершина с петлей



Что называется лесом?

полный ориентированный граф, каждая пара вершин которого соединена в точности одним ориентированным ребром
полный ориентированный граф с неориентированными ребрами
ориентированный граф, у которого число вершин строго равно числу ребер
несвязный граф, представляющий объединение деревьев
 

 
Какой граф называется помеченным?

если существует такая последовательность ребер, ведущая от v1к v2, в которой каждые два соседних ребра имеют общую вершину и никакое ребро не встречается более одного раза
если существует последовательность вершин от v1 до v2
если его ребра пронумерованы
если все его вершины "помечены" целыми числами от 1 до n
 

 
Что называется мостом графа?

все ребра графа
в графе G называется мостом пара V(G),E(G) , где V(G) - непустое конечное множество элементов, называемых вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых V(G),E(G) ребрами
такая пара, что E V×V. Элементы множества E для графа называются дугами
ребро {a,b} называется мостом графа G, если в графе, полученном после удаления из G ребра {a,b}, вершины aи b оказываются несвязными



Что называют гранью в плоском представлении графа?

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



Какой граф называется планарным?

граф, изоморфный плоскому графу
граф, изображенный на плоскости так, что никакие два его ребра (или, вернее, представляющие их кривые) геометрически не пересекаются нигде, кроме инцидентной им обоим вершины
если его можно нарисовать на плоскости так, чтобы никакие два его ребра не имели других общих точек, кроме их общей вершины
если у него любые две вершины смежны



Какой граф называют плоским?

изображенный на плоскости так, что никакие два его ребра (или, вернее, представляющие их кривые) геометрически не пересекаются нигде, кроме инцидентной им обоим вершины
если его можно нарисовать на плоскости так, чтобы никакие два его ребра не имели других общих точек, кроме их общих вершин
только ориентированные графы
только граф, степени вершин которого равны 1



Что называется перегородками в графе?

ребра, соединяющие циклы
мосты, соединяющие циклы
бесконечная грань
диаметр графа
 


Какой граф называется максимально плоским?

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

 
Какие графы называются гомеоморфными?

два графа гомеоморфны (или тождественны с точностью до вершин степени 2), если они оба могут быть получены из одного и того же графа "включением" в его ребра новых вершин степени 2
два графа гомеоморфны, если они планарны
два графа гомеоморфны, если они плоские
два графа гомеоморфны, если они простые и плоские



Сколько бесконечных граней имеет всякое плоское представление графа?

всякое плоское представление графа либо не имеет бесконечной грани, либо имеет в точности одну бесконечную грань
бесконечное множество
столько, сколько у него ребер
столько, сколько у него вершин



Какое выражение является формулой Эйлера (здесь V - число вершин в графе, E - число ребер, а R - число граней)?

V-E+R=2
V-E+R=2+2E
3R 2E
2E=20
 

 
Какие грани в графе называются соседними?

две грани в графе, если они имеют одну общую вершину
две грани, если они ограничены неориентированными ребрами
две грани, если число их вершин строго равно числу ребер
две грани, если их границы имеют хотя бы одно общее ребро



Какой граф называется эйлеровым графом?

связный граф G, если существует замкнутая цепь, проходящая через каждое его ребро
граф, ограниченный простым циклом и не содержащий других циклов
граф G, содержащий его дополнение
связный граф G, если существует замкнутая цепь, проходящая через каждую его вершину



Что называется эйлеровой цепью?

цепь, проходящая через каждое ребро графа
цепь, проходящая через каждую вершину графа
разомкнутая цепь, проходящая через все вершины графа степени 1
разомкнутая цепь, проходящая через каждое ребро графа



Что называется эйлеровым путем в графе?

путь, содержащий все ребра графа
путь, который можно нарисовать на плоскости так, чтобы никакие два его ребра не имели других общих точек, кроме общей вершины
только ребра ориентированного графа
путь, содержащий все ребра графа, степени смежных вершин которых равны 1



Какой граф обладает эйлеровым циклом?

эйлеров граф
триангулированный граф
если граф G связный и все его вершины четные, то он обладает эйлеровым циклом
если в графе существует замкнутая цепь, проходящая через каждое его ребро, он называется эйлеровым циклом
 

 
Какой граф называется полуэйлеровым?

если снять ограничение на замкнутость цепи, то граф называется полуэйлеровым, при этом каждый эйлеров граф будет полуэйлеровым
связный граф G будет полуэйлеровым, если существует замкнутая цепь, проходящая через каждое его ребро
связный граф Gназывается полуэйлеровым, если существует замкнутая цепь, проходящая через каждую его вершину
эйлеровым графом G называется граф, ограниченный простым циклом и не содержащий других циклов



Решение каждого ли лабиринта может быть найдено?

безвыходных лабиринтов нет
существует бесконечное множество решений
да
нет



Может ли связный граф обладать эйлеровым путем, если va и vb - единственные нечетные его вершины?

если граф G связный и va и vb единственные нечетные вершины его, то граф G обладает эйлеровым путем с концами va и vb
граф обладает эйлеровым путем, если его грани ограничены неориентированными ребрами
граф обладает эйлеровым путем, если у него число вершин строго равно числу ребер
граф обладает эйлеровым путем, если он имеет бесконечную грань
 

 
Какой граф называется мультиграфом?

граф, в котором не допускаются петли, но пары вершин могут соединяться более чем одним ребром. Эти ребра называются кратными, а граф – мультиграфом
граф, в котором нет петель, но есть кратные ребра
граф, в котором все вершины имеют четную степень
граф, в котором все вершины имеют нечетную степень
 

 
 
Что называется гамильтоновым путем в графе?

путь, содержащий все ребра графа
если граф можно нарисовать на плоскости так, чтобы никакие два его ребра не имели других общих точек, кроме их общей вершины, то это называют гамильтоновым путем в графе
только ребра ориентированного графа
замкнутая цепь, проходящая ровно один раз через каждую вершину графа
 


Какой граф называется гамильтоновым графом?

связный граф G, если существует замкнутая цепь, проходящая через каждую вершину ровно один раз
граф, ограниченный простым циклом и не содержащий внутри других цикло
граф, содержащий его дополнение
связный граф G, если существует замкнутая цепь, проходящая через каждую его четную вершину



Что называется гамильтоновой цепью?

замкнутая цепь, проходящая через каждое ребро графа
замкнутая цепь, проходящая через каждую вершину графа
разомкнутая цепь, проходящая через все вершины графа степени 1
разомкнутая цепь, проходящая через каждое ребро графа



Какой граф называется полугамильтоновым?

если снять ограничение на замкнутость цепи, то граф называется полугамильтоновым, при этом каждый гамильтонов граф будет полугамильтоновым
связный граф G будет полугамильтоновым, если существует замкнутая цепь, проходящая через каждую его вершину
связный граф Gназывается полугамильтоновым, если существует замкнутая цепь, проходящая через каждое его ребро
гамильтоновым графом G называется граф, ограниченный простым циклом и не содержащий внутри других циклов



Какой граф является эйлеровым или гамильтоновым графом?
 
G1 - эйлеров граф
G4 - гамильтонов граф
G2 - гамильтонов граф
G3 - эйлеров граф
 
 
 
Какой граф обладает гамильтоновым циклом?

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



Каким является граф N1?

вырожденным гамильтоновым
мультиграфом
Эйлеровым
полуэйлеровым
 

 
Если в простом графе с n( 3) вершинами ρ(v) n/2 для любой вершины v, то каким является граф G?

если в простом графе с n( 3)вершинами ρ(v) n/2для любой вершины v, то граф G является гамильтоновым
граф, в котором нет петель, но есть кратные ребра
граф, в котором все вершины имеют четную степень
граф, в котором все вершины имеют нечетную степень
 

 
Каким графом является плоское представление додекаэдра?

гамильтоновым
полуэйлеровым
полугамильтоновым
эйлеровым



Какой граф называется бесконечным?

бесконечным графом называется пара V(G),E(G), где V(G) - бесконечное множество элементов, называемое вершинами, а E(G) - бесконечное семейство неупорядоченных пар элементов из V(G), называемых ребрами
графом G называется пара V(G),E(G), где V(G) - непустое конечное множество элементов, называемых вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых ребрами. Употребление слова "семейство" говорит о том, что допускаются кратные ребра. Будем называть V(G)множеством вершин, а E(G)- семейством ребер графа G. О каждом ребре вида {v,w}говорят, что оно соединяет вершины v и w. Каждая петля {v,v}соединяет вершину vсаму с собой
бесконечным графом D называется пара V(D),A(D), где V(D)непустое конечное множество элементов, называемых вершинами, а A(D) - конечное семейство упорядоченных пар элементов из V(D) , называемых дугами (или ориентированными ребрами). Дуга, у которой вершина vявляется первым элементом, а вершина w - вторым, называется дугой из v в w(v,w). Заметим, что дуги (v,w)и (w,v) различны. Хотя графы и орграфы – существенно различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположно ориентированные дуги
допустим, что множество вершин графа можно разбить на два непересекающихся подмножества V1и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1 с какой-либо вершиной из V2, тогда Gназываем бесконечным графом



Какой граф называется локально конечным?

бесконечный граф, все вершины которого имеют конечные степени
если существует замкнутая цепь, проходящая через каждую вершину графа, то такой граф называется локально конечным
если существует разомкнутая цепь, проходящая через все вершины графа степени 1, то такой граф называется локально конечным
если существует разомкнутая цепь, проходящая через каждое ребро графа, то такой граф называется локально конечным
 

 
Какой граф называется локально счетным бесконечным графом?

граф, все вершины которого имеют счетную степень. Под счетным множеством здесь и в дальнейшем понимается бесконечное множество, допускающее взаимно однозначное отображение на множество натуральных чисел
граф, ограниченный простым циклом и не содержащим внутри других циклов
граф, содержащий его дополнение
связный граф Gназывается локально счетным бесконечным, если существует замкнутая цепь, проходящая через каждую его четную вершину



Какими свойствами обладает G - связный счетный граф, являющийся полуэйлеровым, но не эйлеровым?

G содержит либо не более одной вершины нечетной степени, либо не менее одной вершины бесконечной степени
для каждого конечного подграфа Hграфа Gбесконечный граф G (описанный ранее) содержит ровно одну бесконечную компоненту
связный граф Gсодержит столько компонент, сколько он имеет вершин
связный граф Gограничен простым циклом и не содержащим внутри других циклов



G - связный счетный граф, являющийся эйлеровым. Какими свойствами он обладает?

в графе G нет вершин нечетной степени
для каждого конечного подграфа H графа Gбесконечный граф H (полученный удалением из Gребер графа H) имеет не более двух бесконечных связных компонент
если, кроме того, степень любой вершины из Hчетна, то Hимеет ровно одну бесконечную связную компоненту
в графе Gнет вершин четной степени
 

 
При каких условиях счетный граф планарен?

G - счетный граф, каждый конечный подграф которого планарен, тогда и G планарен
триангулированный граф планарен
если граф Gсвязный и все его вершины четные, то он планарен
если в графе существует замкнутая цепь, проходящая через каждое его ребро, то граф планарен



Что называется бесконечным в одну сторону маршрутом в графе G?

бесконечным в одну сторону маршрутом в G, с начальной вершиной v0, называется бесконечная последовательность ребер вида {v0,v1},{v1,v2}...
бесконечным в одну сторону маршрутом в графе G называют последовательность четных вершин
бесконечным в одну сторону маршрутом в графе Gназывают маршрут, в котором все вершины имеют четную степень
бесконечным в одну сторону маршрутом в графе G называют маршрут, в котором все вершины имеют нечетную степень
 

 
Что называется бесконечным в обе стороны маршрутом в графе G?

бесконечная последовательность ребер вида
...,{v-2,v-1},{v-1,v0},{v0,v-1},{v1,v2},...
все маршруты мультиграфа
все маршруты эйлерова графа
все маршруты полуэйлерова графа
 

 
Какой бесконечный граф называется эйлеровым?

связный бесконечный граф G, если в нем существует бесконечная в обе стороны цепь, содержащая каждое ребро графа G
полуэйлеровый граф
полугамильтоновый граф
граф, обладающий бесконечной (двусторонней) эйлеровой цепью



Что называется хроматическим индексом?

если в графе все вершины имеют счетную степень, то эта степень называется хроматическим индексом
число циклов графа
число мостов графа
если граф G реберно k-раскрашиваем, но не является реберно (k-1)-раскрашиваемым, то kназывается хроматическим индексом
 

 
Какой граф G называется реберно k-раскрашиваемым?

граф G называется реберно k-раскрашиваемым, если его ребра можно раскрасить k-красками таким образом, что никакие два смежных ребра не окажутся одного цвета
граф Gназывается реберно k-раскрашиваемым, если его можно задать парой V(G),E(G) , где V(G)- непустое конечное множество элементов, называемых вершинами, а - E(G) конечное семейство неупорядоченных пар элементов из V(G) (не обязательно различных), называемых ребрами. Употребление слова "семейство" говорит о том, что допускаются кратные ребра. Будем называть V(G) множеством вершин, а V(G) - семейством ребер графа G. О каждом ребре вида {v,w} говорят, что оно соединяет вершины vи w. Каждая петля {v,v}соединяет вершину v саму с собой
граф G называется реберно k- раскрашиваемым, если его можно задать бесконечным D(V(D),A(D)) графом D, где V(D), непустое конечное множество элементов, называемых вершинами, а A(D) - конечное семейство упорядоченных пар элементов из V(D) , называемых дугами (или ориентированными ребрами). Дуга, у которой вершина vявляется первым элементом, а вершина w- вторым, называется дугой из v в w(v,w). Заметим, что дуги (v,w)и (w,v)различны. Хотя графы и орграфы – существенно различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположно ориентированные дуги
допустим, что множество вершин графа можно разбить на два непересекающихся подмножества V1и V2так, что каждое ребро в Gсоединяет какую-нибудь вершину из V1с какой-либо вершиной из V2, тогда граф G называется реберно k-раскрашиваемым
 

 
Что называется хроматическим классом?

бесконечный граф, все вершины которого имеют конечные степени
если существует замкнутая цепь, проходящая через каждую вершину графа, то такая цепь называется хроматическим классом
если существует разомкнутая цепь, проходящая через все вершины графа степени 1, то такая цепь называется хроматическим классом
если граф G реберно k-раскрашиваем, но не является реберно (k-1)-раскрашиваемым, то kназывается хроматическим классом



Что называется реберно-хроматическим числом графа G?

число висячих вершин
число петель в графе
максимальная степень в графе
если граф G реберно k-раскрашиваем, но не является реберно (k-1)-раскрашиваемым, то kназывается хроматическим числом графа G
 

 
Какие треугольники называются сцепленными?
 
если два треугольника имеют общую вершину или ребро
треугольники, образованные ребрами бесконечного графа G
треугольники, образованные компонентами связного графа G
треугольники, образованные мостами связного графа G
 

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

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



Как можно изобразить полный граф с пятью вершинами и ребрами двух цветов, если в нем не найдется треугольника с одноцветными сторонами?

если в полном графе с пятью вершинами и ребрами двух цветов не найдется треугольника с одноцветными сторонами, то граф можно изобразить в виде "пятиугольника" с красными сторонами и синими диагоналями
если в полном графе с пятью вершинами и ребрами двух цветов не найдется треугольника с одноцветными сторонами, то граф можно изобразить в виде "пятиугольника" с синими сторонами и красными диагоналями
если в полном графе с пятью вершинами и ребрами двух цветов не найдется треугольника с одноцветными сторонами, то граф можно изобразить в виде "пятиугольника" с зелеными сторонами и красными диагоналями
если в полном графе с пятью вершинами и ребрами двух цветов не найдется треугольника с одноцветными сторонами, то граф можно изобразить в виде "пятиугольника" с красными сторонами и зелеными диагоналями



Сколько одноцветных ребер имеет каждая вершина минимально у полного графа с шестью или более вершинами и ребрами двух цветов?

любая вершина полного графа с шестью или более вершинами и ребрами двух цветов принадлежит, по меньшей мере, трем ребрам одного цвета
имеет минимум два одноцветных ребра
имеет минимум одно ребро
не имеет ребер вообще
 

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

в графе минимум шесть вершин
в графе минимум пять вершин
в графе минимум четыре вершин
в графе минимум две вершины



Какой граф G называется k-раскрашиваемым?

если его ребра можно раскрасить kкрасками таким образом, что никакие два смежных ребра не окажутся одного цвета
если его можно задать парой (V(G), E(G)), где V(G) - непустое конечное множество элементов, называемых вершинами, а E(G) - конечное семейство неупорядоченных пар элементов из V(G) (необязательно различных), называемых ребрами. Употребление слова "семейство" говорит о том, что допускаются кратные ребра. Будем называть V(G) множеством вершин, а E(G) - семейством ребер графа G. О каждом ребре вида {v,w}говорят, что оно соединяет вершины vи w. Каждая петля (v,v)соединяет вершину v саму с собой
если его можно задать бесконечным графом D(V(D),A(D)), где V(D)непустое конечное множество элементов, называемых вершинами, а A(D) - конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами). Дуга, у которой вершина vявляется первым элементом, а вершина w - вторым, называется дугой из vв w(v,w). Заметим, что дуги (v,w)и (w,v)различны. Хотя графы и орграфы – различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположно ориентированные дуги
пусть граф Gне имеет петель; тогда Gназывается k-раскрашиваемым, если каждой его вершине можно приписать один из kцветов таким образом, чтобы никакие две смежные вершины не оказались одного цвета



Какой граф G называется k-хроматическим?

бесконечный граф, все вершины которого имеют конечные степени
если существует замкнутая цепь, проходящая через каждую вершину графа, то такая цепь называется хроматическим классом
если существует разомкнутая цепь, проходящая через все вершины графа степени 1, то такая цепь называется хроматическим графом
если граф G k-раскрашиваем, но не является (k-1)-раскрашиваемым, то граф G называется k-хроматическим
 

 
Что называется хроматическим числом графа?

если в графе все вершины имеют счетную степень, то эта степень называется хроматическим числом графа
число циклов графа
число мостов графа
если граф Gявляется k-раскрашиваемым, но не является (k-1)-раскрашиваемым, назовем его k-хроматическим, а число kназовем хроматическим числом графа G и обозначим через χ(G)



Если наибольшая степень графа равна (ρ+1)G, скольки-раскрашиваемым является граф?

если наибольшая из степеней вершин графа Gравна (ρ+1), то этот граф ρ-раскрашиваем
если наибольшая из степеней вершин графа Gравна (ρ+1), то этот граф (ρ+3)-раскрашиваем
если наибольшая из степеней вершин графа Gравна (ρ+1), то этот граф (ρ-2)-раскрашиваем
если наибольшая из степеней вершин графа Gравна (ρ+1), то этот граф (ρ+2)-раскрашиваем


 
Как определяем географическую карту?

удобно определить карту, как связный плоский граф, не содержащий мостов. Заметим, что при таком определении карты не исключаем петель или кратных ребер
удобно определить карту, как полный граф, не содержащий мостов. Заметим, что при таком определении карты не исключаем петель или кратных ребер
удобно определить карту, как полный граф четной степени, не содержащий мостов. Заметим, что при таком определении карты не исключаем петель или кратных ребер
удобно определить карту, как полный граф нечетной степени, не содержащий мостов. Заметим, что при таком определении карты не исключаем петель или кратных ребер
 

 
Какую карту называют k-раскрашиваемой?

назовем карту k-раскрашиваемой, если ее грани можно раскрасить kкрасками так, чтобы никакие две смежные грани, то есть грани, границы которых имеют общее ребро, не были одного цвета
назовем карту k-раскрашиваемой, если ее грани можно раскрасить kкрасками так, чтобы никакие два смежных ребра не были одного цвета
назовем карту k-раскрашиваемой, если ее грани можно раскрасить kкрасками так, чтобы ее смежные ребра были одного цвета
назовем карту k-раскрашиваемой, если она имеет kграней



Что называется замкнутой жордановой кривой?

замкнутой жордановой кривой называется жорданова кривая, начало и конец которой совпадают
замкнутой жордановой кривой называется жорданова дуга, начало и конец которой совпадают
замкнутой жордановой кривой называют самопересекающуюся жорданову дугу
замкнутой жордановой кривой называют диаметр графа
 

 
Что называют жордановой кривой?

жордановой кривой на плоскости называется непрерывная кривая, не имеющая самопересечений
жордановой кривой называют жорданову дугу
жордановой кривой называют замкнутую кривую на плоскости
жордановой кривой называют самопересекающуюся кривую на плоскости
 

 
Когда карта Gявляется 2-раскрашиваемой?

карта Gявляется 2-раскрашиваемой тогда и только тогда, когда Gпредставляет собой эйлеров граф
карта G является 2-раскрашиваемой тогда и только тогда, когда Gпредставляет собой гамильтонов граф
карта Gявляется 2-раскрашиваемой тогда и только тогда, когда Gпредставляет собой планарный граф
карта Gявляется 2-раскрашиваемой тогда и только тогда, когда Gпредставляет собой орграф



Какой орграф является связным, или слабо связным?

орграф D связен, или слабо связен, если он не может быть представлен в виде объединения двух различных орграфов (определенных обычным образом)
если существует замкнутая орцепь, проходящая через каждую вершину орграфа, то такой орграф является связным или слабо связным
если существует разомкнутая орцепь, проходящая через все вершины орграфа степени 1, то такой орграф является связным или слабо связным
если граф G реберно k-раскрашиваем, но не является реберно k-1-раскрашиваемым, то такой орграф является связным или слабо связным
 

 
Какой орграф называется эйлеровым?

связный орграф Dназывается эйлеровым, если в нем существует замкнутая орцепь, содержащая каждую его дугу
орграф Dназывается эйлеровым, если в нем существует орцикл, включающий каждую его вершину
орграф, содержащий простую орцепь, проходящую через каждую вершину, называется эйлеровым
пусть D - сильно связный орграф, имеющий n вершин. Если и для любой его вершины v, то D является эйлеровым орграфом


 
Какие орграфы называются простыми?

орграфы, не содержащие петель и кратных ребер, называются простыми
орграф называется простым, если он реберно k-раскрашиваем
орграф называется простым, если его можно задать бесконечным графом D(V(D),A(D)), где V(D)непустое конечное множество элементов, называемых вершинами, а A(D) - конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами). Дуга, у которой вершина vявляется первым элементом, а вершина w - вторым, называется дугой из vв w (v,w). Заметим, что дуги (v,w)и (w,v)различны. Хотя графы и орграфы – различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположно ориентированные дуги
орграф называется простым, если множество его вершин можно разбить на два непересекающихся подмножества V1и V2 так, что каждое ребро в орграфе соединяет какую-нибудь вершину из V1с какой-либо вершиной из V1



Что называют стоком орграфа?

стоком орграфа D называют вершину, у которой полустепень исхода равна нулю
стоком орграфа Dназывают вершину, у которой полустепень захода равна нулю
стоком орграфа D называют вершины, которые не являются сцепленными
стоком орграфа D называют вершины, которые являются сцепленными



Что называют источником орграфа D?

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



Какой орграф Dназывается гамильтоновым?

орграф Dназывается гамильтоновым, если в нем существует орцикл, включающий каждую его вершину
связный орграф называется гамильтоновым, если в нем существует замкнутая орцепь, содержащая каждое его ребро
орграф называется гамильтоновым, если в нем существует орцикл, включающий каждое его ребро



Может ли быть сильно связный турнир гамильтонов?

всякий сильно связный турнир гамильтонов
да, если сильно связный турнир Tс nвершинами содержит орциклы длины 3,4,...,n
всякий сильно связный турнир не может быть гамильтоновым
всякий сильно связный турнир гамильтонов, если каждая его вершина является истоком и стоком



Может ли быть турнир полугамильтонов?

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



Какой орграф называется турниром?

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



Какая вершина в ориентированном графе D называется изолированной?

вершина, у которой и степень входа и степень выхода равны 0
вершина, степень выхода которой положительна, а степень входа равна 0
вершина, степень входа которой положительна, а степень выхода равна 0
вершина, степень выхода и степень входа которой положительны и равны



Что называется вектором вероятностей?

вектор-строка, все компоненты вектора неотрицательны и дают в сумме единицу
вектор-строка, все компоненты вектора отрицательны и дают в сумме минус единицу
вектор-строка, все компоненты вектора неотрицательны и дают в сумме нуль
вектор-строка, все компоненты вектора отрицательны и дают в сумме нуль
 

 
 Что называется путем в ориентированном графе D?
 
путем в ориентированном графе Dот v1 до vnназывается последовательность ориентированных дуг (ребер) (v1,v2),(v2,v3),...,(vn-1,vn), такая, что конец каждой предыдущей дуги (ребра) совпадает с началом следующей и ни одна дуга (ребро) не встречается более одного раза
если существует замкнутая ?

Внимание !
Вопросы к тесту выложены исключительно в ознакомительных целях: количество вопросов может не совпадать с действительным, актуальность не поддерживается,- за решением теста Welcome to the cashier!

---

Какие представления деревьев правильны?

представление с помощью матрицы смежности
представление с помощью списков смежности
представление с помощью списка ребер и кода Прюфера
дерево задается перечислением пар (vi,vj)или троек (vi,vj,uk), если дополнительно нужна нумерация ребер. Здесь vi,vj - вершины дерева



Пусть задано дерево с пронумерованными вершинами. Спрашивается: сколько существует таких разных деревьев?

деревьев с nпронумерованными вершинами ровно столько, сколько можно образовать последовательностей вида (v1,v2,...,vn-2) длины n-2, элементы которых выбираются из элементов множества M={1,2,3,...,n-1,n}
деревьев с nпронумерованными вершинами ровно столько, сколько можно образовать последовательностей вида (v1,v2,...,vn-2) длины n-2, элементы которых выбираются из элементов множества vi M
деревьев с nпронумерованными вершинами ровно столько, сколько можно образовать последовательностей вида (v1,v2,...,vn-2) длины 10
деревьев с nпронумерованными вершинами ровно столько, сколько можно образовать последовательностей вида (v1,v2,...,vn-2) длины n-2, элементы которых выбираются из элементов множества vi 5



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

можно построить дерево, вершины которого взяты из множества целых чисел
можно построить дерево, вершины которого взяты из множества простых чисел
можно построить столько деревьев с n вершинами, сколько последовательностей вида (v1,v2,...,vn-2) длины n-2 , элементы которых выбираются из элементов множества M={1,2,3,...,n-1,n}
можно построить столько деревьев с вершинами сколько последовательностей вида (v1,v2,...,vn-2)длины n-2 , элементы которых выбираются из элементов множества простых чисел мощностью n
 

 
Что нужно сделать, чтобы произвольный граф Gпреобразовать в дерево?

убрать циклы
убрать мосты
добавить циклы
добавить мосты
 
 
 
Сколько корневых вершин может быть у дерева?

одна
две
нет корневых вершин
столько, сколько вершин, для которых максимальное из расстояний до других вершин равно радиусу графа



Из чего состоит остовной лес?

из остовных деревьев
из компонент, в которых нет циклов
из компонент, в которых нет мостов
остовной лес - это частный случай остовного дерева
 

 
Расстоянием d(vx,vy)между вершинами графа Gназываем длину кратчайшего пути, их соединяющего. Наибольшее из таких d(vx,vy)называем диаметром G, наименьшее – радиусом. Может ли у какой – то вершины дерева максимальное из расстояний до других вершин равняться радиусу?

да
нет
для корневых вершин
для листьев дерева
 

 
Любое дерево имеет либо одну, либо две корневые вершины. Как корневые вершины дерева расположены относительно друг друга?

корневые вершины – смежные
корневые вершины не могут быть смежными
корневые вершины расположены на расстояние диаметра
корневые вершины расположены на расстоянии радиуса



Чему равна сумма чисел, стоящих в любом из столбцов матрицы инциденций?

сумма чисел в каждом столбце матрицы инциденций равна степени вершины, которую он характеризует
сумма чисел в каждом столбце матрицы инциденций равна рангу матрицы
сумма чисел в каждом столбце матрицы инциденций равна числу петель в графе
сумма чисел в каждом столбце матрицы инциденций равна числу компонент графа
 
 
 
Какие деревья называются изоморфными?

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

 
Какие помеченные деревья называются изоморфными?

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



Сколько матчей необходимо провести для того, чтобы выявить по олимпийской системе обладателя кубка среди 147 команд?

146
145
100
172
 
 
 
Из какого графа нельзя выделить дерево, содержащее все вершины графа?

из любого несвязного графа
из графа, состоящего из четного числа компонент
из пустого графа



Чему равна сумма чисел, стоящих в любой из строк матрицы инциденций графа G?

сумма чисел в каждой строке матрицы инциденций равна степени вершины, которую она характеризует
сумма чисел в каждой строке матрицы инциденций равна рангу матрицы
сумма чисел в каждой строке матрицы инциденций равна числу петель в графе
сумма чисел в каждой строке матрицы инциденций равна числу компонент графа



Существует ли граф с шестью вершинами, степени которых 2, 3, 3, 4, 4, 4?

существует
не существует
в графе должно быть минимум четыре вершины
в графе должно быть минимум две вершины
 

 
Граф, который может быть изображен проволочной моделью куба, =

плоский
эйлеров
не плоский
 

 
Сколько получится кусков бумаги, если первоначально имелось mкусков, некоторые из кусков разрезали на nчастей, а всего было разрезано kкусков?

m+(n-1)k
m+(n+1)k
m-(n-1)k
m+(n-1)/k
 

Как из связного графа получить каркас?

известно, что в связном графе Gудаление одного ребра, принадлежащего некоторому выбранному циклу, не нарушает связности оставшегося графа. Применим эту процедуру к одному из оставшихся циклов, и так до тех пор, пока не останется ни одного цикла. В результате получим дерево, связывающее все вершины графа, оно называется каркасом
в связном графе Gудаление одного ребра, принадлежащего некоторому выбранному циклу, не нарушает связности оставшегося графа. Применим эту процедуру ко всем циклам. В результате получим дерево, связывающее все вершины графа, оно называется каркасом
чтобы получить из графа G каркас, нужно удалить все мосты
чтобы получить из графа Gкаркас, нужно соединить все его компоненты мостами



Пусть граф имеет n вершин. Когда граф T является деревом?

граф T является деревом, если он не содержит циклов и имеет n-1 ребер
граф T является деревом, если он связан и имеет n-1 ребер
граф T является деревом, если он связан и каждое его дерево является мостом
граф T является деревом, если вершины его соединены ровно одной цепью
 

 
Как из связного графа получить остовное дерево?

известно, что в связном графе Gудаление одного ребра, принадлежащего некоторому выбранному циклу, не нарушает связности оставшегося графа. Применим эту процедуру к одному из оставшихся циклов, и так до тех пор, пока не останется ни одного цикла. В результате получим дерево, связывающие все вершины графа, оно называется остовным деревом
в связном графе Gудаление одного ребра, принадлежащего некоторому выбранному циклу, не нарушает связности оставшегося графа. Применим эту процедуру ко всем циклам. В результате получим дерево, связывающее все вершины графа, оно называется остовным деревом
чтобы получить из графа Gостовное дерево, нужно удалить все мосты
чтобы получить из графа Gостовное дерево, нужно соединить все его компоненты мостами



Что называется циклическим рангом?

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

 
Что называется цикломатическим числом?

число удаленных ребер при получении остовного дерева
циклический ранг
число присоединенных ребер при получении остовного дерева
число удаленных петель при получении остовного дерева
 

 
Граф G состоит из k компонент. Что нужно сделать, чтобы из заданного графа получить остовной лес?

чтобы из такого графа получить остовной лес, нужно к каждой компоненте графа применить такую процедуру: в каждой компоненте графа удаление одного ребра, принадлежащего некоторому выбранному циклу, не нарушает связности оставшейся компоненты . Применим эту процедуру ко всем циклам. В результате получим дерево, связывающее все вершины компоненты, оно называется остовным деревом. А так как у нас было kкомпонент, то получим остовной лес, состоящий из kостовных деревьев
чтобы из такого графа получить остовной лес, нужно к каждой компоненте графа применить такую процедуру: в каждой компоненте графа удалить все циклы, не нарушая связности оставшейся компоненты. Применим эту процедуру ко всем циклам. В результате получим дерево, связывающее все вершины компоненты, оно называется остовным деревом. А так как у нас было kкомпонент, то получим остовной лес, состоящий из kостовных деревьев
чтобы из такого графа получить остовной лес, нужно к каждой компоненте графа применить такую процедуру: нужно получить из каждой компоненты графа Gостовное дерево, удаляя все мосты в каждой компоненте графа. В результате получим дерево, связывающие все вершины компоненты, оно называется остовным деревом. А так как у нас было kкомпонент, то получим остовной лес, состоящий из kостовных деревьев
чтобы из такого графа получить остовной лес, нужно к каждой компоненте графа применить такую процедуру: получить из каждой компоненты графа Gостовное дерево, соединив все его компоненты мостами. В результате получим дерево, связывающее все вершины компоненты, оно называется остовным деревом. А так как у нас было kкомпонент, то получим остовной лес, состоящий из kостовных деревьев



Пусть ген Gнаследуется и от отца, и от матери с вероятностью p, а ген g - с вероятностью q. Чему равна вероятность унаследованных генов?

p+q=1
p-q=1
p-q=0
p*q=1
 

 
Какой граф описывает ситуацию случая кровного родства ?

граф является деревом
граф не является деревом, так как его вершины слипаются
граф является остовом
граф является каркасом
 

 
Как изображается работа на сетевом графике?

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



С какими параметрами связана работа?

работа, как элемент сетевого графика, связана с затратой времени и расходом ресурсов
работа - это физический процесс
работа - это вершина сетевого графика
работа - это начало сетевого графика
 

 
Что называется проектом?

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



Какая работа называется фиктивной?

работа, отражающая только зависимость одного мероприятия от другого, называется фиктивной. Такая работа имеет нулевую продолжительность (или нулевой расход ресурсов) и обозначается пунктирной стрелкой
работа, отражающая только зависимость от истока орграфа
работа, отражающая только зависимость одного стока орграфа
это такая работа, которая имеет нулевую продолжительность (или нулевой расход ресурсов) и обозначается пунктирной стрелкой
 

 
Какая работа имеет нулевой расход ресурсов?

фиктивная работа имеет нулевой расход ресурсов
работа, отражающая только зависимость от истока орграфа, имеет нулевой расход ресурсов
работа, отражающая только зависимость одного стока орграфа, имеет нулевой расход ресурсов
такая работа, которая имеет нулевую продолжительность



Что называют исходным событием в сетевом графике?

событие, обозначающее начала процесса, получило название исходного события, которому присваивается нулевой номер
событие, обозначающее конец процесса, получило название исходного события, которому присваивается нулевой номер
событие, обозначающее текущее значение процесса, получило название исходного события, которому присваивается нулевой номер
событие, обозначающее повторение процесса, получило название исходного события, которому присваивается нулевой номер
 

 
Каким графом является сетевой график?

граф, не содержащий циклов и имеющий только один исток и только один сток, называется направленным графом. Сетевой график есть ориентированный связный асимметрический граф с одним истоком, одним стоком и без циклов, то есть это направленный граф
сетевой график есть ориентированный связный асимметрический граф с одним истоком, одним стоком и без циклов, то есть это направленный граф
сетевой график есть не ориентированный связный асимметрический граф и без циклов, то есть это направленный граф
сетевой график есть ориентированный связный асимметрический граф с одним истоком, одним стоком и с циклами, то есть это направленный граф
 

 
Что называется событиями первого ранга?

события, которые не имеют входящих в них работ
события, которые не имеют четного количества входящих в них работ
события, которые имеют нечетное количество входящих в них работ
события, которые имеют входящую в них работу-петлю
 

 
Какой граф называется двудольным?

бесконечный граф, все вершины которого имеют конечные степени
если существует замкнутая цепь, проходящая через каждую вершину графа, то такой граф называется двудольным
если существует разомкнутая цепь, проходящая через все вершины графа степени 1, то такой граф называется двудольным
допустим, что множество вершин графа можно разбить на два непересекающихся подмножества V1и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1с какой-либо вершиной из V2, тогда G называем двудольным графом
 
 
 
Что называется совершенным паросочетанием в двудольном графе G(V1V2)?

совершенным паросочетанием из V1в V2в двудольном графе G(V1,V2) называется взаимно однозначное соответствие между вершинами из V1и подмножеством вершин из V2, обладающее тем свойством, что соответствующие вершины соединены ребром
совершенным паросочетанием из 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саму с собой
совершенным паросочетанием из V1в V2в двудольном графе G(V1,V2)называется D(V(D),A(D), где V(D)непустое конечное множество элементов, называемых вершинами, а A(D) - конечное семейство упорядоченных пар элементов из V(D), называемых дугами (или ориентированными ребрами). Дуга, у которой вершина v является первым элементом, а вершина - вторым, называется дугой из v в w. Заметим, что дуги {v,w}и {w,v}различны. Хотя графы и орграфы – различные объекты, в определенных случаях графы можно рассматривать как орграфы, в которых каждому ребру соответствуют две противоположно ориентированные дуги
допустим, что множество вершин графа можно разбить на два непересекающихся подмножества V1и V2так, что каждое ребро в Gсоединяет какую-нибудь вершину из V1с какой-либо вершиной из V2графа G, тогда совершенным паросочетанием из в называется взаимно однозначное соответствие между вершинами из V1и подмножеством вершин из V2
 
 
 
Какой граф называется полным двудольным графом?

если в графе все вершины имеют счетную степень, то такой граф называется двудольным
если граф имеет четное число циклов, то такой граф называется полным двудольным графом
если граф имеет четное число мостов, то такой граф называется полным двудольным графом
следует подчеркнуть, что в двудольном графе совсем не обязательно каждая вершина из V1соединена с каждой вершиной из V2; если же это так и если при этом граф Gпростой, то он называется полным двудольным графом и обычно обозначается Km,n, где m,n- число вершин, соответственно, в V1и V2



Что называется латинским прямоугольником?

латинским (m×n)- прямоугольником называется (m×n) - матрица M=(mij), элементами которой являются целые числа, удовлетворяющие условиям (1) 1 mij n, (2) все элементы в каждой строке и в каждом столбце различны. Заметим, что из условий (1) и (2) следует, что m n
прямоугольная матрица, состоящая из реберно-хроматических чисел графа G, называется латинским прямоугольником
прямоугольная матрица, состоящая из степеней вершин графа G, называется латинским прямоугольником
прямоугольная матрица, состоящая из весов графа G, называется латинским прямоугольником


 
Что называется латинским квадратом?

если два графа имеют общую вершину или ребро, то их называют латинским квадратом
квадратная матрица, образованная ребрами бесконечного графа Gназывается латинским квадратом
квадратная матрица, образованная компонентами связного графа G, называется латинским квадратом
латинским (m×n) - квадратом называется (m×n) - матрица M=(mij), элементами которой являются целые числа, удовлетворяющие условиям (1) 1 mij n, (2) все элементы в каждой строке и в каждом столбце различны, если m=n
 

 
Можно ли латинский прямоугольник расширить до латинского квадрата?

да, если взять m=nи выполнить условие 1 mij n
нет
да, если взять m nи выполнить условие 1 mij n
да, если взять m nи выполнить условие 1 mij n



Можно ли получить двудольный граф соединением двух графов Km,n=Nm+Nn?

да, можно
нет, нельзя
нельзя, если m n
нельзя, если m=n
 

 
Операции объединения и соединения графов коммутативны и ассоциативны?

да, операции объединения и соединения коммутативны и ассоциативны
нет, операции объединения и соединения не коммутативны и не ассоциативны
операции объединения и соединения графов коммутативны, но не ассоциативны
операции объединения и соединения графов не коммутативны, но ассоциативны
 

 
Можно ли операции объединения и соединения распространить на любое конечное число графов?

да
нет
да, только на четное число графов
да, только на нечетное число графов
 


Что называется частичной трансверсалью для  ?

трансверсаль произвольного подсемейства семейства  будем называть частичной трансверсалью для 
трансверсаль произвольного подсемейства семейства Е будем называть частичной трансверсалью для 
трансверсаль произвольного подсемейства семейства   E будем называть частичной трансверсалью для 
трансверсаль произвольного подсемейства семейства   E будем называть частичной трансверсалью для 
 

 
Если Е - непустое конечное множество и  =(S1,...,Sm) - семейство непустых его подмножеств, то что называется трансверсалью для  ?

если Е - непустое конечное множество и  =(S1,...,Sm) - семейство непустых его подмножеств, трансверсалью для  называется подмножество множества Е, состоящее из mэлементов: по одному из каждого множества Si
если Е - непустое конечное множество и  =(S1,...,Sm) - семейство обязательно различных непустых его подмножеств, трансверсалью для  называется подмножество множества Е, состоящее из mэлементов: по одному из каждого множества Si
если Е - непустое конечное множество и  =(S1,...,Sm) - семейство не обязательно пустых его подмножеств, трансверсалью для  называется подмножество множества Е, состоящее из mэлементов: по одному из каждого множества Si
если Е - непустое конечное множество и  =(S1,...,Sm)- семейство обязательно пустых его подмножеств, трансверсалью для  называется подмножество множества Е, состоящее из mэлементов: по одному из каждого множества Si



Что называется матрицей инциденций?

другой подход к изучению трансверсалей семейства  =(S1,...,Sm) непустых подмножеств множества E={e1,...,en} состоит в исследовании (m×n) - матрицы A=((aij), в которой aij=1если ej Siи aij=0в противном случае. Любую такую матрицу, все элементы которой равны 0 или 1, называют матрицей инциденций этого семейства
другой подход к изучению трансверсалей семейства  =(S1,...,Sm) пустых подмножеств множества E={e1,...,en} состоит в исследовании (m×n)- матрицы A=((aij), в которой aij=1если ej Siи aij=0в противном случае. (Любую такую матрицу, все элементы которой равны 0 или 1, называют матрицей инциденций этого семейства)
другой подход к изучению трансверсалей семейства  =(S1,...,Sm) непустых подмножеств множества E={e1,...,en} состоит в исследовании (m×m)- матрицы A=((aij), в которой aij=1если ej Siи aij=0в противном случае. Любую такую матрицу, все элементы которой равны 0 или 1, называют матрицей инциденций этого семейства
другой подход к изучению трансверсалей семейства  =(S1,...,Sm) непустых подмножеств множества E={e1,...,en} состоит в исследовании (n×n)- матрицы A=((aij), в которой aij=1если ej Siи aij=0в противном случае. Любую такую матрицу, все элементы которой равны 0 или 1, называют матрицей инциденций этого семейства



Чему равен словарный ранг матрицы?

словарный ранг (0,1)-матрицы А равен минимальному числу μ строк и столбцов, которые в совокупности содержат все единицы из А
cловарный ранг (0,1)-матрицы А равен максимальному числу μ строк и столбцов, которые в совокупности содержат все единицы из А
cловарный ранг (0,1)-матрицы А равен минимальному числу μ строк, которые в совокупности содержат все единицы из А
cловарный ранг (0,1)-матрицы А равен минимальному числу μстолбцов, которые в совокупности содержат все единицы из А



Когда два семейства непустых подмножеств имеют общую трансверсаль?

пусть Е - непустое конечное множество , а  =(S1,...,Sm)и τ=(T1,...,Tm) - два семейства его непустых подмножеств. Тогда  и τимеют общую трансверсаль в том и только в том случае , если для всех подмножеств A и B множества {1,...,m}
пусть Е - непустое конечное множество , а  =(S1,...,Sm)и τ=(T1,...,Tm) - два семейства его непустых подмножеств. Тогда  и τимеют общую трансверсаль в том и только в том случае , если для всех подмножеств A и B множества {1,...,m}
пусть Е - непустое конечное множество , а  =(S1,...,Sm)и τ=(T1,...,Tm) - два семейства его непустых подмножеств. Тогда  и τимеют общую трансверсаль в том и только в том случае , если для всех подмножеств A и B множества {1,...,m}
пусть Е - непустое конечное множество , а  =(S1,...,Sm)и τ=(T1,...,Tm) - два семейства его непустых подмножеств. Тогда  и τимеют общую трансверсаль в том и только в том случае , если для всех подмножеств A и B множества {1,...,m}
 

 
Предположим, что E={1,2,3,4,5,6}, а S1=S2={1,2},S3=S4={2,3},S5={1,4,5,6} Имеет ли семейство а  =(S1,...,S5) трансверсаль?

да
нет, так как здесь невозможно найти пять различных элементов из Е - по одному из каждого подмножества Si
да, если заменить Si
да, если заменить Si и Е
 

 
 
Что такое сеть?

cеть N - это орграф, каждой дуге  которого приписано неотрицательное действительное число  ( ), называемое ее пропускной способностью
cеть представляет собой пару D( )где D - орграф, а  - функция, отображающая множество дуг орграфа D в множество неотрицательных действительных чисел
cеть представляет собой пару D( )где D - орграф, а  - функция, отображающая множество дуг орграфа D в множество отрицательных действительных чисел
допустим, что множество вершин графа можно разбить на два непересекающихся подмножества V1и V2 так, что каждое ребро в G соединяет какую-нибудь вершину из V1с какой-либо вершиной из V2, тогда граф Gназывается сетью
 

 
Что называется полустепенью исхода вершины x?

полустепень исхода вершины x определяется как разность пропускных способностей дуг вида (x,z)
полустепенью исхода x называется число дуг из D вида (w,x)
если x вершина орграфа D, то полустепенью исхода x называют число дуг орграфа D, имеющих вид (x,w)
полустепень исхода вершины x определяется как сумма пропускных способностей дуг вида (x,z)
 


 
Что называется полустепенью захода вершины x?

если в графе все вершины имеют счетную степень, то эта степень называется полустепенью захода
если x вершина орграфа D, то полустепенью захода x называют число дуг орграфа D, имеющих вид (x,w)
полустепень захода вершины xопределяется как сумма пропускных способностей дуг вида (x,z)
полустепенью захода x называется число дуг из D вида (w,x)



Какая дуга в сети называется насыщенной?

дуга  , для которой  ( )= ( ), в сети N=(D, )
дуга  , для которой  ( )  ( ), в сети N=(D, )
дуга  , для которой  ( )  ( ), в сети N=(D, )
дуга  , для которой  ( )  ( ), в сети N=(D, )



Что называется разрезом в сети?

такое множество Aдуг орграфа D, которое обладает тем свойством, что любая простая орцепь из v в w проходит через дугу, принадлежащую A
разрезом в сети является не что иное, как vw - разделяющее множество соответствующего орграфа D
разрезом в сети является не что иное, как функция, составляющая каждой дуге  из Dнеотрицательное действительное число  ( ) (называемое потоком через  ) таким образом , что  ( )  ( )для любой дуги 
разрезом в сети является N=(D, )
 

 
Что называется потоком через сеть N?

для данной сети N=(D, )поток определяется через N как функцию  , составляющую каждой дуге  из Dнеотрицательное действительное число  ( ) (называемое потоком через  ) таким образом , что  ( )  ( )для любой дуги  ; по отношению к сети (D, ) полустепень исхода и полустепень захода любой вершины (отличной от v и w) равны между собой
для данной сети N=(D, )поток определяется через N как функцию  , составляющую каждой дуге  из Dнеотрицательное действительное число  ( ) (называемое потоком через  ) таким образом , что  ( )  ( )для любой дуги  ; по отношению к сети (D, ) полустепень исхода и полустепень захода любой вершины (отличной от v и w) неравны между собой
для данной сети N=(D, )поток определяется через N как функцию  , составляющую каждой дуге  из Dнеотрицательное действительное число  ( ) (называемое потоком через  ) таким образом , что  ( )  ( )для любой дуги  ; по отношению к сети (D, ) полустепень исхода больше полустепени захода
для данной сети N=(D, )поток определяется через N как функция  , составляющая каждой дуге  из Dнеотрицательное действительное число  ( ) (называемое потоком через  ) таким образом , что  ( )  ( )для любой дуги  ; по отношению к сети (D, ) полустепень исхода меньше полустепени захода любой вершины (отличной от v и w)



Что называется пропускной способностью разреза?

сумма пропускных способностей, принадлежащих ему дуг
сумма пропускных способностей, не принадлежащих ему дуг
сумма степеней вершин данной сети
сумма всех ребер, принадлежащих этому разрезу



Что называют величиной потока?

cумма потоков через дуги, инцидентные v, равна сумме потоков через дуги, инцидентные w
cумма потоков через дуги, инцидентные v, равна сумме потоков через дуги, инцидентные w, увеличенная на число вершин сети
cумма потоков через дуги, инцидентные v, равна сумме потоков через дуги, инцидентные w, уменьшенная на число вершин сети
cумма потоков через дуги, инцидентные v, равна сумме потоков через дуги, инцидентные w, поделенная на число вершин



Может ли в сети величина любого максимального потока быть равна пропускной способности любого минимального разреза?

во всякой сети величина любого максимального потока равна пропускной способности любого минимального разреза
во всякой сети величина любого максимального потока меньше пропускной способности любого минимального разреза
во всякой сети величина любого максимального потока больше пропускной способности любого минимального разреза
данные величины несравнимы

Вы можете обратится к нам напрямую, через:

По Skype: molodoyberkut
По Telegram: @MolodoyBerkut
По ICQ: 657089516

Или через форму обратной связи на нашем сайте

Пока сочиняется...