Cтраница 3
Как правило, определить, является ли данный граф критическим, чрезвычайно трудно. Однако каждый / г-хроматический граф, п 2, содержит - критический подграф. Действительно, если Я - такой наименьший порожденный подграф графа G, что % ( Щ - % ( 0), то Н - критический граф. [31]
Задача, о которой мы упомянули, связана с полным графом, число вершин которого на единицу меньше числа вершин графа Рамсея. Ясно, что такой граф - наибольший, на котором описанная выше игра может закончиться вничью. Такой граф называется критической раскраской для перечисленного выше множества подграфов. Требуется так раскрасить критический граф, чтобы не возник ни один из перечисленных выше подграфов. [32]
В классической теории Рамсея для обозначения полных графов обычно используется одно-единственное число. Иначе говоря, наименьший полный граф, непременно порождающий монохроматический ( одноцветный-только красный или только синий) треугольник, при раскраске ребер в два цвета содержит 6 вершин. Таким образом, если два игрока поочередно раскрашивают ребра полного графа К6 в красный и синий цвет, то один из них заведомо проигрывает, первым заканчивая треугольник своего цвета. Соответствующая и легко разрешимая задача - раскраска в два цвета ребер критического графа Х5, при которой ни один монохроматический треугольник не возникает. [33]
Здесь мы рассматриваем работы, в которых исследуется взаимосвязь между разными свойствами одного и того же графа. Заметим еще, что объектами многочисленных исследований были и остаются всевозможные критические графы: например, критический хроматический граф в ряде работ определяется как такой, что удаление из него хотя бы одной вершины приводит к уменьшению хроматического числа; максимально насыщенный граф имеет наибольшее возможное число ребер при данном количестве вершин и данной плотности. Келли и других авторов, специально посвященные строению критических графов, опубликованы до 1962 года, а некоторые работы, напротив, выходят только в 1963 году. Но и во многих работах 1962 года ( и предшествующих им), для которых изучение критических графов не является основной целью, такое изучение вместе с соответствующими построениями оказывается необходимым при выводе различных оценок, а особенно при доказательстве достижимости этих оценок. В дальнейшем мы не будем специально подчеркивать роль критических графов. [34]
Здесь мы рассматриваем работы, в которых исследуется взаимосвязь между разными свойствами одного и того же графа. Заметим еще, что объектами многочисленных исследований были и остаются всевозможные критические графы: например, критический хроматический граф в ряде работ определяется как такой, что удаление из него хотя бы одной вершины приводит к уменьшению хроматического числа; максимально насыщенный граф имеет наибольшее возможное число ребер при данном количестве вершин и данной плотности. Келли и других авторов, специально посвященные строению критических графов, опубликованы до 1962 года, а некоторые работы, напротив, выходят только в 1963 году. Но и во многих работах 1962 года ( и предшествующих им), для которых изучение критических графов не является основной целью, такое изучение вместе с соответствующими построениями оказывается необходимым при выводе различных оценок, а особенно при доказательстве достижимости этих оценок. В дальнейшем мы не будем специально подчеркивать роль критических графов. [35]
В этой главе рассматривается несколько моделей случайных графов с п занумерованными вершинами и Т ребрами при п, Т - сю. Решающую роль в поведении случайных графов играет параметр 9 - 2Т / п и его мы будем интерпретировать как время в эволюции графов. Удобно различать три области изменения параметра в. Другими словами, в докритическом случае, 9 если и стремится к единице, то не слишком быстро. Критический граф характеризуется тем, что п, Т - оо и ( 1 - ) 3п стремится к некоторой постоянной. Наконец, граф является надкритическим, если п, Т - сю и ( 1 - 9) 3п - - оо. Подчеркнем, что в этой терминологии речь идет об областях изменения параметра в и, следовательно, не о самих графах, а о их последовательностях. [36]