Дискретный анализ и теория вероятностей - тест 6

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

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

Чего НЕ содержит простой граф?

Пусть имеется простой граф ,у которого  – множество вершин и  – множество ребер.Число независимости графа - 

 (2) мощность множества называется … если для любых принадлежащих пара принадлежит  

 (3) мощность множества называется … если для любых принадлежащих пара не принадлежит  

Пусть имеется простой граф ,у которого  – множество вершин и  – множество ребер.Кликовое число графа - 

 (2) мощность множества называется … если для любых принадлежащих пара принадлежит  

 (3) мощность множества называется … если для любых принадлежащих пара не принадлежит  

Пусть имеется простой граф ,у которого  – множество вершин и  – множество ребер.Хроматическое число графа - 

 (2) мощность множества называется … если для любых принадлежащих пара принадлежит  

 (3) мощность множества называется … если для любых принадлежащих пара не принадлежит  

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

 (1)  

 (2)  

 (3)  

 (4)  

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

 (1)  

 (2)  

 (3)  

 (4)  

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

 (1)  

 (2)  

 (3)  

 (4)  

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

 (1)  

 (2)  

 (3)  

Рассмотрим множество - множество всех графов на  вершинах. Чему равна мощность множества 

 (1)  

 (2)  

 (3)  

 (4)  

Рассмотрим множество - множество всех графов на  вершинах. Чему равно отношение количества графов , для которых кликовое число  больше  к мощности множества  если 

Как называется граф  построенный следующим образом? Имеется  - множество натуральных чисел от 1 до . Множество вершин данного графа образуют все -элементные подмножества из множества . Говорят, что пара  образуют ребро графа, тогда и только тогда .

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

 (3) полный граф на вершинах 

Что является Кнезеровским графом 

 (3) полный граф на вершинах 

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

 (2)  

 (3)  

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

 (2)  

 (3)  

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

 (2)  

 (3)  

Чему равно кликовое число  Кнезеровского графа ?

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

Чему равно число независимости Кнезеровского графа ?

Сколько вершин содержит Кнезеровский граф ?

 (1)  

 (2)  

 (3)  

 (4)  

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

Чему равно число независимости Кнезеровского графа ?

 (1)  

 (2)  

 (3)  

 (4)  

Чему равно кликовое число  Кнезеровского графа ?

 (1)  

 (2)  

 (3)  

 (4)  

Чему равно число независимости Кнезеровского графа , если ?

 (1)  

 (2)  

 (3)  

 (4)  

Чему равно число независимости Кнезеровского графа , если ?

 (1)  

 (2)  

 (3)  

 (4)  

Имеется множество натуральных чисел от 1 до . И определены следуюшие подмножества , ,...,,..., . Обозначим . Рассмотрим  - совокупность независимых множеств вершин Кнезеровского графа . Что верно относительно ?

 (1)  

 (2)  

 (3)  

 (4)  

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

 (1)  

 (2)  

 (3)  

 (4)  

Имеется множество натуральных чисел от 1 до . И определены следуюшие подмножества , ,...,,..., . Обозначим . Рассмотрим  - совокупность независимых множеств вершин Кнезеровского графа . Что верно относительно мощности ?

 (1)  

 (2)  

 (3)  

 (4)  

Имеется множество натуральных чисел от 1 до . И определены следуюшие подмножества , ,...,,..., . Обозначим . Рассмотрим  - совокупность независимых множеств вершин Кнезеровского графа . Допустим, . Выберите все множества, которые в таком случае также попадают в  кроме ?

 (1)  

 (2)  

 (3)  

Имеется множество натуральных чисел от 1 до . И определены следуюшие подмножества , ,...,,..., . Обозначим .Среди множеств  и  выберите множество, с котором не пересекается .

 (1)  

 (2)  

 (3)  

 (4)  

Имеется множество натуральных чисел от 1 до . И определены следуюшие подмножества , ,...,,..., . Обозначим .Среди множеств  и  выберите множество, с котором не пересекается .

 (1)  

 (2)  

 (3)  

 (4)  

Рассмотрим Кнезеровский граф . Покрасим в цвет 1 все вершины, которые содержат 1; в цвет 2 все вершины, которые содержат 2, ..., в цвет  все вершины, которые содержат . Элементы какого из перечисленным множества остатись не покрашенными?

 (1)  

 (2)  

 (3)  

 (4)  

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

 (1)  

 (2)  

 (3)  

 (4)  

Рассмотрим Кнезеровский граф . Покрасим в цвет 1 все вершины, которые содержат 1; в цвет 2 все вершины, которые содержат 2, ..., в цвет  все вершины, которые содержат . Сколько еще потребуется цветов, чтобы раскрасить граф таким образом, как это требуется для определения хроматического числа графа?