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

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

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

(Отметьте один правильный вариант ответа.)

Варианты ответа

$\chi(G)\geqslant\omega(G)$ (Верный ответ)

$\chi(G)\leqslant\omega(G)$

$\chi(G)>\omega(G)$

$\chi(G)<\omega(G)$

Похожие вопросы

Пусть имеется простой граф G=(V;E)

,у которого

– множество вершин и

– множество ребер. $\alpha$ число независимости и $\omega$ кликовое число. Какое утверждение является верным?

Пусть имеется простой граф G=(V;E)

,у которого

– множество вершин и

– множество ребер. $\chi(G)$ хроматическое число графа и $\alpha(G)$ число независимости графа. Какое утверждение является верным?

Пусть имеется простой граф G=(V;E)

,у которого

– множество вершин и

– множество ребер. Подмножество

называется … если для любых x,y

принадлежащих

пара $\lbrace x,y \rbrace$ не принадлежит

Пусть имеется простой граф G=(V;E)

,у которого

– множество вершин и

– множество ребер. Подмножество

называется … если для любых x,y

принадлежащих

пара $\lbrace x,y \rbrace$ принадлежит

Пусть имеется простой граф G=(V;E)

,у которого

– множество вершин и

– множество ребер.Кликовое число графа -

Пусть имеется простой граф G=(V;E)

,у которого

– множество вершин и

– множество ребер.Хроматическое число графа -

Пусть имеется простой граф G=(V;E)

,у которого

– множество вершин и

– множество ребер.Число независимости графа -

Имеется множество натуральных чисел от 1 до

. И определены следуюшие подмножества $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 до

. Что является наиболее точной верхней оценкой мощности ${\cal F}\cap{\cal A}$ ?

Пусть

-случайный граф, множество, состоящее из

вершин, а каждое ребро проводим с вероятностью

, которая независит от вероятности проведения других ребер и может зависеть от

. Пусть случайная величина T_n

- число треугольников в случайном графе. Если $p=o\left(\frac 1 n\right)$ , то к чему ассимтотические стремится математическое ожидание MT_n

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

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

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