Ответы к контрольной работе: Графы и их применение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Что называется совершенным паросочетанием в двудольном графе G(V1V2)?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Что называется путем от v1 до v2 в графе?

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Что называется дискретной стационарной цепью Маркова?

Что называют цепью Маркова (или просто цепью)?

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

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

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

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

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

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

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