Главная / Графы и их применение

Графы и их применение - ответы на тесты Интуит

В курсе излагаются основные понятия теории графов. Описаны методы решения задач.

Список вопросов:

# Что называется графом?
# Что называется вершинами графа?
# Что называется степенью вершины графа?
# Какой граф называется двудольным?
# Что называется маршрутом в данном графе G(V,Е)?
# Какой граф называется регулярным?
# Что называется орграфом?
# Что называется ориентированным полным графом?
# Что называется путем от v1 до v2 в графе?
# Какая вершина в ориентированном графе D называется изолированной?
# Что называется путем в ориентированном графе D?
# Что называется вектором вероятностей?
# Что называется матрицей перехода?
# Когда цепь Маркова неприводима?
# Что называют цепью Маркова (или просто цепью)?
# Что называется дискретной стационарной цепью Маркова?
# Что называется источником в орграфе?
# Что называется стоком в орграфе?
# Что называется представлением дерева?
# Какие представления деревьев правильны?
# Пусть задано дерево с пронумерованными вершинами. Спрашивается: сколько существует таких разных деревьев?
# Что нужно сделать, чтобы произвольный граф G преобразовать в дерево?
# Сколько корневых вершин может быть у дерева?
# Можно ли построить дерево, используя множество целых чисел в качестве вершин графа?
# Из чего состоит остовной лес?
# Расстоянием d(vx,vy) между вершинами графа G называем длину кратчайшего пути, их соединяющего. Наибольшее из таких d(vx,vy) называем диаметром G, наименьшее – радиусом. Может ли у какой – то вершины дерева максимальное из расстояний до других вершин равняться радиусу?
# Любое дерево имеет либо одну, либо две корневые вершины. Как корневые вершины дерева расположены относительно друг друга?
# Какие деревья называются изоморфными?
# Какие помеченные деревья называются изоморфными?
# Чему равна сумма чисел, стоящих в любом из столбцов матрицы инциденций?
# Чему равна сумма чисел, стоящих в любой из строк матрицы инциденций графа G?
# Из какого графа нельзя выделить дерево, содержащее все вершины графа?
# Сколько матчей необходимо провести для того, чтобы выявить по олимпийской системе обладателя кубка среди 147 команд?
# Граф, который может быть изображен проволочной моделью куба, =
# Сколько получится кусков бумаги, если первоначально имелось m кусков, некоторые из кусков разрезали на n частей, а всего было разрезано k кусков?
# Существует ли граф с шестью вершинами, степени которых 2, 3, 3, 4, 4, 4?
# Пусть граф имеет n вершин. Когда граф T является деревом?
# Как из связного графа получить остовное дерево?
# Как из связного графа получить каркас?
# Граф G состоит из k компонент. Что нужно сделать, чтобы из заданного графа получить остовной лес?
# Что называется циклическим рангом?
# Что называется цикломатическим числом?
# Пусть ген G наследуется и от отца, и от матери с вероятностью p, а ген g - с вероятностью q. Чему равна вероятность унаследованных генов?
# Какой граф описывает ситуацию случая кровного родства ?
# Что называется проектом?
# С какими параметрами связана работа?
# Как изображается работа на сетевом графике?
# Какая работа называется фиктивной?
# Какая работа имеет нулевой расход ресурсов?
# Что в сетевом графике называется событием?
# Что называют исходным событием в сетевом графике?
# Что называется событиями первого ранга?
# Каким графом является сетевой график?
# Что называется совершенным паросочетанием в двудольном графе G(V1V2)?
# Какой граф называется двудольным?
# Какой граф называется полным двудольным графом?
# Что называется латинским прямоугольником?
# Что называется латинским квадратом?
# Можно ли латинский прямоугольник расширить до латинского квадрата?
# Можно ли получить двудольный граф соединением двух графов Km,n=Nm+Nn?
# Можно ли операции объединения и соединения распространить на любое конечное число графов?
# Операции объединения и соединения графов коммутативны и ассоциативны?
# Если Е - непустое конечное множество и ϕ=(S1,...,Sm) - семейство непустых его подмножеств, то что называется трансверсалью для ϕ?
# Что называется частичной трансверсалью для ϕ?
# Что называется матрицей инциденций?
# Чему равен словарный ранг матрицы?
# Когда два семейства непустых подмножеств имеют общую трансверсаль?
# Предположим, что E={1,2,3,4,5,6}, а S1=S2={1,2},S3=S4={2,3},S5={1,4,5,6} Имеет ли семейство а ϕ=(S1,...,S5) трансверсаль?
# Что такое сеть?
# Что называется полустепенью исхода вершины x?
# Что называется полустепенью захода вершины x?
# Что называется разрезом в сети?
# Что называется потоком через сеть N?
# Какая дуга в сети называется насыщенной?
# Что называют величиной потока?
# Что называется пропускной способностью разреза?
# Может ли в сети величина любого максимального потока быть равна пропускной способности любого минимального разреза?
# Можно получить несколько различных матриц смежности данного графа?
# Чему равна сумма чисел в любой строке или столбце матрицы смежности?
# Что называется обхватом графа?
# Какой граф называется регулярным?
# Что называется каркасом графа G?
# Какой граф называется регулярным степени r?
# Что называется мостом графа?
# Что называется лесом?
# Какой граф называется помеченным?
# Какой граф называют плоским?
# Какой граф называется планарным?
# Что называют гранью в плоском представлении графа?
# Что называется перегородками в графе?
# Какие графы называются гомеоморфными?
# Какой граф называется максимально плоским?
# Какое выражение является формулой Эйлера (здесь V - число вершин в графе, E - число ребер, а R - число граней)?
# Какие грани в графе называются соседними?
# Сколько бесконечных граней имеет всякое плоское представление графа?
# Что называется эйлеровым путем в графе?
# Что называется эйлеровой цепью?
# Какой граф называется эйлеровым графом?
# Какой граф называется полуэйлеровым?
# Какой граф обладает эйлеровым циклом?
# Какой граф называется мультиграфом?
# Может ли связный граф обладать эйлеровым путем, если va и vb - единственные нечетные его вершины?
# Решение каждого ли лабиринта может быть найдено?
# Что называется гамильтоновым путем в графе?
# Что называется гамильтоновой цепью?
# Какой граф называется гамильтоновым графом?
# Какой граф является эйлеровым или гамильтоновым графом? [Большая Картинка]
# Какой граф называется полугамильтоновым?
# Какой граф обладает гамильтоновым циклом?
# Если в простом графе с n(≥3) вершинами ρ(v)≥n/2 для любой вершины v, то каким является граф G?
# Каким является граф N1?
# Каким графом является плоское представление додекаэдра?
# Какой граф называется бесконечным?
# Какой граф называется локально конечным?
# Какой граф называется локально счетным бесконечным графом?
# G - связный счетный граф, являющийся эйлеровым. Какими свойствами он обладает?
# Какими свойствами обладает G - связный счетный граф, являющийся полуэйлеровым, но не эйлеровым?
# При каких условиях счетный граф планарен?
# Что называется бесконечным в одну сторону маршрутом в графе G?
# Что называется бесконечным в обе стороны маршрутом в графе G?
# Какой бесконечный граф называется эйлеровым?
# Какой граф G называется реберно k-раскрашиваемым?
# Что называется хроматическим классом?
# Что называется хроматическим индексом?
# Что называется реберно-хроматическим числом графа G?
# Какие треугольники называются сцепленными?
# Сколько несцепленных треугольников с одноцветными сторонами найдется в полном графе с восемью вершинами, ребра которого окрашены в два цвета?
# Как можно изобразить полный граф с пятью вершинами и ребрами двух цветов, если в нем не найдется треугольника с одноцветными сторонами?
# Сколько одноцветных ребер имеет каждая вершина минимально у полного графа с шестью или более вершинами и ребрами двух цветов?
# Какое минимальное число вершин имеет полный граф, ребра которого окрашены в два цвета и который имеет хотя бы один треугольник с одинаковыми ребрами?
# Какой граф G называется k-раскрашиваемым?
# Какой граф G называется k-хроматическим?
# Что называется хроматическим числом графа?
# Если наибольшая степень графа равна (ρ+1)G, скольки-раскрашиваемым является граф?
# Как определяем географическую карту?
# Какую карту называют k-раскрашиваемой?
# Когда карта G является 2-раскрашиваемой?
# Что называют жордановой кривой?
# Что называется замкнутой жордановой кривой?
# Какие орграфы называются простыми?
# Какой орграф является связным, или слабо связным?
# Какой орграф называется эйлеровым?
# Какой орграф D называется гамильтоновым?
# Что называют источником орграфа D?
# Что называют стоком орграфа?
# Какой орграф называется турниром?
# Может ли быть турнир полугамильтонов?
# Может ли быть сильно связный турнир гамильтонов?