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

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

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

Пусть имеется простой граф G=(V;E),у которого V – множество вершин и E – множество ребер.\chi(G) хроматическое число графа и \alpha(G) число независимости графа. Какое утверждение является верным?

(Отметьте один правильный вариант ответа.)
Варианты ответа
\chi(G)<\frac{\mid V\mid}{\alpha(G)}
\chi(G)\leqslant\frac{\mid V\mid}{\alpha(G)}
\chi(G)\geqslant\frac{\mid V\mid}{\alpha(G)}(Верный ответ)
\chi(G)>\frac{\mid V\mid}{\alpha(G)}
Похожие вопросы
Пусть имеется простой граф G=(V;E),у которого V – множество вершин и E – множество ребер.\alpha число независимости и \omegaкликовое число. Какое утверждение является верным?
Пусть имеется простой граф G=(V;E),у которого V – множество вершин и E – множество ребер.\chi хроматическое число и \omega - кликовое число. Какое утверждение является верным?
Пусть имеется простой граф G=(V;E),у которого V – множество вершин и E – множество ребер.Хроматическое число графа -
Пусть имеется простой граф G=(V;E),у которого V – множество вершин и E – множество ребер.Число независимости графа -
Пусть имеется простой граф G=(V;E),у которого V – множество вершин и E – множество ребер. Подмножество W называется … если для любых x,y принадлежащих W пара \lbrace x,y \rbrace не принадлежит E.
Пусть имеется простой граф G=(V;E),у которого V – множество вершин и E – множество ребер. Подмножество W называется … если для любых x,y принадлежащих W пара \lbrace x,y \rbrace принадлежит E.
Пусть имеется простой граф G=(V;E),у которого V – множество вершин и E – множество ребер.Кликовое число графа -
Имеется множество натуральных чисел от 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?
Имеется множество натуральных чисел от 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}?