Итак, графы – это рисунки, которые состоят из точек и линий, соединяющих эти точки. Каждая пара точек в графе может быть соединена линиями. Линия указывает на связь между двумя точками. Точки называются вершинами графа, а линиями рёбрами. Ребро может иметь направление, которое указывается стрелочкой. У графа обязательно есть вершины. Граф без рёбер называется пустым. Направленная линия (со стрелкой) называется дуга. Линия ненаправленная (без стрелки) называется ребро. Линия, выходящая из некоторой вершины и входящая в неё же, называется петля...

В этой публикации я разберу два задачи из теории графов, где одновременно фигурируют лемма Турана и числа Рамсея. Напомню, что лемма Турана в общем виде звучит так. Наибольшее число ребер у графов, имеющих v вершин и у которого нет n попарно соединённых вершин равно ex(v,n)=(n-2)(v^2-r^2)/(2n-2)+r(r-1)/2, где r - остаток при делении v на (n-1). Числом Рамсея r(m,n) называется минимальное количество человек в компании, в которой обязательно найдётся либо m попарно знакомых, либо n попарно незнакомых. Задача 1. Ребра графа на 300 вершинах покрашены в красный и синий цвета так, что нет одноцветных треугольников...