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

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

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

Рассмотрим Кнезеровский граф KG_{n,k}(V,E). Покрасим в цвет 1 все вершины, которые содержат 1; в цвет 2 все вершины, которые содержат 2, ..., в цвет n-2k+1 все вершины, которые содержат n-2k+1. Сколько еще потребуется цветов, чтобы раскрасить граф таким образом, как это требуется для определения хроматического числа графа?

(Ответ необходимо ввести в поле ввода.)
Варианты ответа
Похожие вопросы
Рассмотрим Кнезеровский граф KG_{n,k}(V,E). Покрасим в цвет 1 все вершины, которые содержат 1; в цвет 2 все вершины, которые содержат 2, ..., в цвет n-2k+1 все вершины, которые содержат n-2k+1. Элементы какого из перечисленным множества остатись не покрашенными?
Рассмотрим случайную раскраску полного графа K_n на nвершинах в красный и синий цвета. Пусть p-вероятность покрасить ребро в красный цвет и 1-p - вероятность покрасить ребро в синий цвет. Определим события A_1,...,A_{C_n^3};B_1,...,B_{C_n^t}, где A_i-состоит в том, что i-ый треугольник целиком красный и B_i-состоит в том, что i-ая клика размера t целиком синяя. Если для некоторого события A_i построен орграф зависимостей, то какое выражение позволит сверху оценить количество ребер, которые выйдут из вершины A_i орграфа зависимостей в вершины A_j?
Рассмотрим случайную раскраску полного графа K_n на nвершинах в красный и синий цвета. Пусть p-вероятность покрасить ребро в красный цвет и 1-p - вероятность покрасить ребро в синий цвет. Определим события A_1,...,A_{C_n^3};B_1,...,B_{C_n^t}, где A_i-состоит в том, что i-ый треугольник целиком красный и B_i-состоит в том, что i-ая клика размера t целиком синяя. Если для некоторого события A_i построен орграф зависимостей, то какое выражение позволит сверху оценить количество ребер, которые выйдут из вершины B_i орграфа зависимостей в вершины B_j?
Рассмотрим случайную раскраску полного графа K_n на nвершинах в красный и синий цвета. Пусть p-вероятность покрасить ребро в красный цвет и 1-p - вероятность покрасить ребро в синий цвет. Определим события A_1,...,A_{C_n^3};B_1,...,B_{C_n^t}, где A_i состоит в том, что i-ый треугольник целиком красный и B_i состоит в том, что i-ая клика размера t целиком синяя. Если для некоторого события A_i построен орграф зависимостей, то какое выражение позволит сверху оценить количество ребер, которые выйдут из вершины A_i орграфа зависимостей в вершины B_i?
Имеется множество натуральных чисел от 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?
Рассмотрим случайную раскраску полного графа K_n на nвершинах в красный и синий цвета. Пусть p-вероятность покрасить ребро в красный цвет и 1-p - вероятность покрасить ребро в синий цвет. Определим события A_1,...,A_{C_n^3};B_1,...,B_{C_n^t}, где A_i-состоит в том, что i-ый треугольник целиком красный и B_i-состоит в том, что i-ая клика размера t целиком синяя. Чему равна P(A_i)?
Рассмотрим случайную раскраску полного графа K_n на nвершинах в красный и синий цвета. Пусть p-вероятность покрасить ребро в красный цвет и 1-p - вероятность покрасить ребро в синий цвет. Определим события A_1,...,A_{C_n^3};B_1,...,B_{C_n^t}, где A_i-состоит в том, что i-ый треугольник целиком красный и B_i-состоит в том, что i-ая клика размера t целиком синяя. Чему равна P(B_i)?
Как называется граф 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.
Определим случайную раскраску так: с вероятностью p красим очередное ребро в красный цвет, с вероятностью (1-p) красим очередное ребро в синий цвет.Пусть событие A_iсостоит в том, что в случайной раскраске i-ая по счету клика K_s в графе K_n целиком красная. Чему равна P(A_i)?
Определим случайную раскраску так: с вероятностью p красим очередное ребро в красный цвет, с вероятностью (1-p) красим очередное ребро в синий цвет.Пусть событие B_i состоит в том, что в случайной раскраске i-ая по счету клика K_s в графе K_n целиком синяя. Чему равна P(B_i)?