База ответов ИНТУИТ

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

<<- Назад к вопросам

Что является верным относительно хроматического числа Кнезеровского графа KG_{n,k}(V,E)?

(Отметьте один правильный вариант ответа.)
Варианты ответа
\chi (KG(n,k)\leqslant n-2k+2
\chi (KG(n,k)< n-2k+2
\chi (KG(n,k)\geqslant n-2k+2(Верный ответ)
\chi (KG(n,k)> n-2k+2
Похожие вопросы
Имеется множество натуральных чисел от 1 до n. И определены следуюшие подмножества A_1=\{1,2,...,k\}, A_2=\{2,3,...,k+1\},...,A_{n-k-1}=\{n-k-1,...,n\},..., A_{n}=\{n,1,...,k-1\}. Обозначим {\cal A }=\{ A_1,...,A_n \}. Рассмотрим {\cal F }=\{ F_1,...,F_s \} - совокупность независимых множеств вершин Кнезеровского графа KG(n,k). Что верно относительно мощности {\cal F}\cap{\cal A}?
Имеется множество натуральных чисел от 1 до n. И определены следуюшие подмножества A_1=\{1,2,...,k\}, A_2=\{2,3,...,k+1\},...,A_{n-k-1}=\{n-k-1,...,n\},..., A_{n}=\{n,1,...,k-1\}. Обозначим {\cal A }=\{ A_1,...,A_n \}. Рассмотрим {\cal F }=\{ F_1,...,F_s \} - совокупность независимых множеств вершин Кнезеровского графа KG(n,k). Что верно относительно | {\cal F}\cap{\cal A}|?
Чему равно кликовое число Кнезеровского графа KG_{n,k}(V,E)?
Пусть имеется простой граф G=(V;E),построенный на n вершинах. Какое утверждение относительно \omega(G) кликового числа графа является верным при больших n?
Имеется множество натуральных чисел от 1 до n. И определены следуюшие подмножества A_1=\{1,2,...,k\}, A_2=\{2,3,...,k+1\},...,A_{n-k-1}=\{n-k-1,...,n\},..., A_{n}=\{n,1,...,k-1\}. Обозначим {\cal A }=\{ A_1,...,A_n \}. Рассмотрим {\cal F }=\{ F_1,...,F_s \} - совокупность независимых множеств вершин Кнезеровского графа KG(n,k). Что является наиболее точной верхней оценкой мощности {\cal F}\cap{\cal A}?
Чему равно число независимости Кнезеровского графа KG_{n,k}(V,E), если k\leqslant\frac n 2?
Чему равно число независимости Кнезеровского графа KG_{n,k}(V,E), если k>\frac n 2?
Имеется множество натуральных чисел от 1 до n. И определены следуюшие подмножества A_1=\{1,2,...,k\}, A_2=\{2,3,...,k+1\},...,A_{n-k-1}=\{n-k-1,...,n\},..., A_{n}=\{n,1,...,k-1\}. Обозначим {\cal A }=\{ A_1,...,A_n \}. Рассмотрим {\cal F }=\{ F_1,...,F_s \} - совокупность независимых множеств вершин Кнезеровского графа KG(n,k). Допустим, A_1 \in {\cal F}. Выберите все множества, которые в таком случае также попадают в {\cal F} кроме A_1?
Рассмотрим Кнезеровский граф KG_{n,k}(V,E). Покрасим в цвет 1 все вершины, которые содержат 1; в цвет 2 все вершины, которые содержат 2, ..., в цвет n-2k+1 все вершины, которые содержат n-2k+1. Сколько еще потребуется цветов, чтобы раскрасить граф таким образом, как это требуется для определения хроматического числа графа?
Как называется граф KG_{n,k}(V,E) построенный следующим образом? Имеется R_n=\{1,....n \} - множество натуральных чисел от 1 до n. Множество вершин данного графа образуют все k-элементные подмножества из множества R_n. Говорят, что пара v_1 \sim v_2 образуют ребро графа, тогда и только тогда v_1 \cap v_2 =\varnothing.