Cтраница 3
На рис. 137 изображены все возможные способы раскраски графа трем-я цветами. [31]
Последовательные раскраски в общем случае не обеспечивают раскраску графа в минимальное число цветов. [32]
Будем говорить о правильной ( неполной) раскраске графа, даже если окрашена только часть его ребер и подграф, образованный всеми окрашенными ребрами, правильно раскрашен. [33]
Пусть мы имеем некоторую, быть может, неполную раскраску графа G, и пусть В - некоторая его вершина. [34]
Так как в любой x ( G) - раскраске графа G есть одноцветный класс, содержащий по, крайне мере pl % ( G) вершин, то существует полный подграф графа G, у которого не менее p / x ( G) вершин. Таким образом, х ( Сг) p / x ( G), откуда следует доказываемое неравенство. [35]
Приведем еще оценку, вывод которой будет рассмотрен при изучении приближенных методов раскраски графа. [36]
Тем не менее именно попытки обосновать эту гипотезу стимулировали получение ряда результатов по раскраске графов, которые в свою очередь привели к исследованиям некоторых других разделов теории графов. [37]
Полученный график показывает ( рис 3.16), что экономия памяти, производимая раскраской графа несовместимости, может быть весьма существенной. [38]
Аналог динамического распределения ресурсов ЛИВС целесообразно искать в классе задач о коммивояжере, теории расписаний, раскраски графов и других, которые решаются методами целочисленного программирования. Эти методы относятся к подклассу методов нелинейного программирования, но допускают сведение к методам линейного или динамического программирования. [39]
Аналогичные рассуждения позволяют доказать следующую теорему, которая окажется полезной, когда мы перейдем к задачам о раскраске графов. [40]
Когда исходный граф не содержит в качестве подграфа граф Гк, то для любой пары вершин графа существует раскраска графа в К цветов, при которой эти вершины несоцветны, что обеспечивает многокомпонентную ЛГ-раскраску вершин графа. Таким образом, граф Гк является запрещенной фигурой многокомпонентной К-раскраски вершин графа. [41]
Применение нестандартных архитектур генетического поиска позволяет находить существующие подстановки внутри подграфов и эффективно решать задачи установления изоморфизма графов, раскраски графов, построения независимых подмножеств. [42]
Соотношение Z ( n 1) Z ( ri) X ( n 1) справедливо только в том случае, если разные раскраски гс-вершинных графов будут приводить по сделанному построению тоже к разным раскраскам. [43]
В этом параграфе будем рассматривать графы без петель и без кратных ребер, поскольку наличие или отсутствие кратных ребер никак не влияет на правильность раскраски графа. Отметим, что подграф, натянутый на множество вершин, окрашенных одинаково, при правильной раскраске графа не содержит ребер. [44]
Объектами, на которых проводятся исследования, являются такие оптимизационные задачи на графах, как разбиение; размещение вершин графа на плоскости и в линейке; задача о коммивояжере; раскраска графов; построение независимых подмножеств, клик графов и распознавания изоморфизма графов, рассмотренные выше. [45]