В компании 100 человек. Известно, что среди любых 10 есть трое попарно знакомых(кроме этих знакомств могут быть и еще). При каком наименьшем n гаранти ...
В галактическом сенате 1024 сенатора. Каждые два из них - друзья или враги. Причем известно, что у любых двух врагов есть общий друг сенатор. Какое на ...
250 студентов поехали на картошку, причём у каждого из них ровно 4 друга среди остальных. По окончании уборочных работ оказалось, что ровно 188 студен ...
Добрый вечер. Есть у меня вот такая задачаИзвестно, что в графе K(m,n) есть гамильтонов цикл и и этот цикл планарен. Найдите наибольшее такое к, что д ...
Пете необходимо спаять электрическую схему, состоящую из 10 чипов, соединённых между собой проводами (один провод соединяет два различных чипа; два чи ...
Докажите, что случайный граф на n вершинах связен.Точная формулировка: исходы — все неориентированные графы без кратных ребер с одним и тем жемножеств ...
Найти все натуральные числа N такие, что диаграмма Хассе решетки делителей числа N является плоским графомБыло использовано решение отсюда, но оно сло ...
Дополнением обыкновенного графа G = (V, E) называется граф G’=(V, E’), где E’ - дополнение E. Доказать, что граф, изоморфный своему дополнению, связен ...
Помогите построить минимальный по числу вершин связный обыкновенный граф с одним мостом, с одной точкой сочленения и четырьмя блоками.У меня получился ...
Помогите решить задачку: дан граф, все n вершин которого имеют одну и ту же степень. Какой максимальный размер может иметь независимое множество в так ...
Докажите, что для любого n принадлежащего натуральным числам, существует ориентированный граф c n вершинами и по меньшей мере 2^(1-n)*n! гамильтоновым ...