 |
Сколько бинарных ребер надо удалить в Кениговом представлении гиперграфа, чтобы в нем, а, следовательно, и в гиперграфе, не было циклов.
|
|
|
|
Итоговая рэпчинка
Установите соответствие между действиями над множествами и их определениями.
Объединение множеств А и В <-> приводит к образованию такого нового множества С, которое состоит из таких и только таких элементов, которые принадлежат хотя бы одному из множеств А и В.
Пересечение множеств А и В <-> приводит к образованию такого нового множества С, которое состоит из таких и только таких элементов, которые одновременно принадлежат множествам А и В.
Разность множеств А и В <-> приводит к образованию такого нового множества С, которое состоит из элементов множества А за исключением элементов множества В.
Симметрическая разность множеств А и В <-> приводит к образованию такого нового множества С, которое состоит из объединения элементов, полученных из множества А за исключением элементов множества В и из множества В за исключением элементов множества А.
Дополнение множества А до множества В <-> приводит к образованию такого нового множества С, которое состоит из таких элементов множества В, которые одновременно не принадлежат множеству А.
Укажите название специального бинарного отношения R, если для каждого элемента "х" существует отношение "хRх".
(<рефл*>)
Укажите название специального бинарного отношения R, если для каждой пары элементов "х" и "y" существуют отношения "xRy" и "yRx".
(<сим*>)
Укажите название специального бинарного отношения R, если для каждых трех элементов "x", "y" и "z" из условия существования отношений "хRу" и "уRz" следует и существование отношения "хRz".
(<транз*>)
Всякое специальное бинарное отношение, обладающее одновременно свойствами рефлексивности, симметричности и транзитивности, называется отношением...
|
|
|
(<эквивалент*>)
Всякое специальное бинарное отношение, обладающее одновременно свойствами антирефлексивности, антисимметричности и транзитивности, называется отношением...
(<поряд*>V<упоряд*>V<частичного поряд*>)
Специальное бинарное отношение доминирования в отличие от специального бинарного отношения порядка не обладает свойством...
(<транз*>)
Установите соответствие между способами отображения множества Х в множество Y и их определениями.
Взаимнооднозначное отображение <-> каждый элемент множества Х имеет только один образ в множестве Y, а каждый элемент множества Y только один прообраз в множестве Х.
Однозначное отображение <-> каждый элемент множества Х имеет только один образ в множестве Y.
Многозначное отображение <-> каждый элемент множества Х имеет один или несколько образов в множестве Y.
Как называется характеристика множества, определяемая как число элементов в этом множестве?
(<мощность*>)
Как называется отношение между множествами А и В, если оба множества состоят из одних и тех же элементов?
(<равенст*>)
Как называется множество А по отношению к множеству В, если оно полностью содержится в множестве В?
(<подмножест*>)
Как называется множество, в котором элементы имеют степени принадлежности к данному множеству из интервала [0,1]?
(<нечётк*> V <нечетк*> V<расплывчат*>)
Установите соответствие между названиями графов и свойствами бинарных отношений в них.
Орграф <-> несимметричные отношения.
Неограф <-> симметричные отношения.
Как называется характеристика вершины неографа, определяемая количеством ребер, инцидентных данной вершине?
<степен*>V(<локал*>&<степен*>)V<валент*>
Установите соответствие между названиями графов и их свойствами.
|
|
|
Псевдограф <-> граф с кратными ребрами и петлями.
Мультиграф <-> граф без петель, но с кратными ребрами.
Скелет <-> граф без петель и кратных ребер.
Как называется скелетный n,m-неограф, у которого m = n(n-1)/2?
(<полн*>)
Установите соответствие между частями графа и их определениями.
Подграф <-> граф, который порождается в исходном графе заданным непустым подмножеством его вершин, и содержащий все ребра, оба конца которых принадлежат этому подмножеству.
Суграф <-> граф, который получается из исходного путем удаления некоторых ребер (дуг); при этом множество вершин графа равно множеству вершин исходного графа.
Надграф <-> граф, который получается из исходного путем добавления новых вершин вместе с инцидентными им рёбрами (дугами).
Установите соответствие между операциями над графами и правилами нахождения множества рёбер в результате выполненной операции.
Объединение (наложение) двух графов G1 и G2 <-> граф G, в котором множество ребер определяется на основании утверждения: для каждой вершины множество ее образов определяется как объединение множеств образов этой вершины в G1 и G2.
Перечесение двух графов G1 и G2 <-> граф G, в котором множество ребер определяется на основании утверждения: для каждой вершины множество ее образов определяется как пересечение множеств образов этой вершины в G1 и G2.
Вычитанием двух графов G1 без G2 <-> граф G, в котором множество ребер определяется на основании утверждения: для каждой вершины множество ее образов определяется как пересечение множества вершин в графе G и множества образов этой вершины в G1.
Укажите, чем определяется длина маршрута в неографе?
Количеством ребер.
Какое понятие для орграфа аналогично понятию цепи в неографе?
(<пут*>V <контрпут*>V<полупут*>)
Какое понятие для орграфа аналогично понятию цикла в неографе?
(<контур*>V<полуконтур*>)
Связный орграф, в котором для любой вершины множество достижимости этой вершины есть само множество вершин этого орграфа, называется...
(<сильн*>V<сильносвяз*>)
Связный орграф, в котором есть такие пары вершин, которые можно соединить только полупутём, называется...
(<слаб*> V <слабосвязн*>)
Связный орграф, в котором есть такие вершины, у которых множество достижимости не совпадает с множеством вершин этого орграфа, и нет таких пар вершин, которые нельзя было бы соединить путём и (или) полупутём, называется...
|
|
|
(<односторон*>V<одностороннесвяз*>)
Ребро, удаление которого из связного неографа приводит к образованию несвязного неографа, называется...
(<мост*> V <переше*>)
Именем какого ученого назван связный граф, в котором есть цикл, содержащий все ребра этого графа?
(<Эйлер*>)
Именем какого ученого назван связный граф, в котором есть цикл, содержащий все вершины этого графа?
(<Гамильтон*>)
Как называется связный граф без циклов?
(<дерев*>)
Как называется несвязный граф, каждая компонета связности которого представляет собой дерево?
(<лес*>)
Сколько ребер содержит дерево на n вершинах?
(<n?1>V<n? 1>V<n?1>V<n? 1>)
Чему равна полустепень захода корневой вершины в корневом дереве?
Чему равна полустепень исхода листа в корневом дереве?
Как называется характеристика вершины корневого дерева, определяемая длиной пути от корня до данной вершины?
(<глубин*>)
Как называется характеристика вершины корневого дерева, определяемая длиной максимального пути от этой вершины до одного из листов дерева?
(<высот*>)
Как называется характеристика вершины корневого дерева, определяемая как разность высоты дерева и глубина вершины?
(<уров*>)
Как называется граф, который избражен на плоскости без пересечения (самопересечения) ребер?
(<плоск*>)
Установите соответствие между экстремальными числами графа и их определениями.
Цикломатическое число <-> указывает на то, сколько ребер надо удалить из графа, чтобы превратить его в остовное дерево (в остовный лес).
Хроматическое число <-> указывает на минимальное число цветов для вершинной раскраски графа.
Число внутренней устойчивости <-> указывает на максимальное число вершин в графе, не смежных между собой.
Число внешней устойчивости <-> указывает на минимальное количество вершин для вершинного покрытия графа.
|
|
|
Кликовое число <-> указывает на максимальное количество вершин графа, попарно смежных между собой.
Число паросочетания <-> указывает на максимальное количество ребер, не смежных между собой.
Число реберного покрытия <-> указывает на минимальное количество ребер, концы которых образуют множество вершин графа.
Укажите максимальное количество независимых циклов в связном графе n,m-размерности?
(<m-n+1>)V(<m - n + 1>)
Сколько цветов потребуется для вершинной раскраски полного графа n,m-размерности?
<n>
Сколько цветов потребуется для вершинной раскраски двудольного графа n,m-размерности?
Определите верхнюю границу хроматического числа для связного графа, у которого локальная степень вершин не превышает число 4?
Граф, в котором нет простых циклов нечётной длины, называется графом...
(<Кёниг*> V <Кениг*> V <двудол*>)
Математическая модель n-арных отношений называется...
(<гиперграф*>)
Гиперграф состоит из двух множеств, находящихся в отношении инцидентности: множества вершин и множества...
(<гиперребер*> V <гиперрёбер>)
Гиперребро - это непустое подмножество... гиперграфа.
(<вершин>)
Порядок гиперграфа определяется количеством его...
(<вершин*>)
Если вершина принадлежит гиперребру, то говорят, что они...
(<инцидент*> V <инц*>)
Количество гиперребер, инцидентных вершине, определяет ее...
(<степень>)
Количество вершин, принадлежащих гиперребру, определяет... этого гиперребра.
(<степень>)
Сколько граней имеет связный плоский n,m-граф?
(<m-n+2> V <m - n + 2>)
Укажите верхнюю границу числа ребер m для связного плоского n,m-графа (n>=3)?
(<3n-6> V <3*n-6> V <3n - 6> V <3*n - 6>)
Могут ли повторяться гиперребра в цепи гиперграфа (да или нет)?
~<да> & <не*>
Длина цепи в гиперграфе определяется количеством в ней...
(<гиперребер*> V <гиперрёбер>)
Цикл гиперграфа соответствует... в его Кениговом представлении.
Простому циклу
Связность двух вершин в гиперграфе определяется их принадлежностью...
Цепи
Цикломатический ранг гиперграфа указывает на то,...
сколько бинарных ребер надо удалить в Кениговом представлении гиперграфа, чтобы в нем, а, следовательно, и в гиперграфе, не было циклов.
Установите соответствие между структурными элементами дискретной системы и её модели в виде сети Петри.
событие <-> переход
условие <-> позиция
предусловие <-> входная позиция
постусловие <-> выходная позиция
Некоторый факт в дискретной системе, трактуемый как потенциальное действие одного из ее элементов, которое может осуществиться один раз, несколько раз или ни разу, называется...
|
|
|
(<событи*>)
Предикат, являющийся логическим описанием ситуации, при котором некоторое событие может реализоваться в дискретной системе, называется...
(<услови*>)
Логическое отношение нескольких условий, при истинном значении которого некоторое событие может реализоваться в дискретной системе, называется...
(<предуслови*>)
Определенное сочетание нескольких условий, на которое будет влиять реализация некоторого события в дискретной системе, называется...
(<постуслови*>)
Вершина двудольного графа, соответствующая в сети Петри некоторому k-ому событию в дискретной системе, называется...
(<переход*>)
Пересечение множеств переходов и позиций в сети Петри равно...
Пустому множеству
Вершина двудольного графа, соответствующая в сети Петри некоторому k-ому условию в дискретной системе, называется...
(<позици*>)
Позиция, из которой имеется дуга к некоторому переходу, является... по отношению к этому переходу.
(<входн*>)
Позиция, в которую направлена дуга из некоторого перехода, является... по отношению к этому переходу.
(<выходн*>)
Функция, которая отображает Т -> Р в сети Петри и устанавливает соответствие между переходами и множествами их выходных позиций, называется...
(<выходн*>)
Функция, которая отображает Т -> Р в сети Петри и устанавливает соответствие между каждым переходом и множеством его выходных позиций, называется...
(<выходн*>)
Числовая характеристика степени выполнения k-го условия в дискретной системе определяет в сети Петри... соответствующей позиции.
(<емкост*> V <ёмкост*>)
Процедура приписания емкостей позициям сети Петри, называется...
(<маркировк*>V<разметк*> V <размётк*>)
Что определяет в сети Петри характеристика # (Pk, I (Ti))?
|
|
|
