Cтраница 2
Говорят, что вершины ( соответственно ребра) неориентированного графа G без петель правильно раскрашены, если каждой вершине ( соответственно каждому ребру) графа сопоставлен ровно один из заданного набора цветов, причем любым двум соседним вершинам ( соответственно смежным ребрам) сопоставлены разные цвета. Граф, вершины или ребра которого правильно раскрашены, будем называть правильно раскрашенным, если из контекста ясно, какие именно элементы графа раскрашиваются или это безразлично. Очевидно, что всякий подграф правильно раскрашенного графа также правильно раскрашен. Можно сказать, что ( правильная) раскраска вершин ( соответственно ребер) графа - это функция с натуральными значениями, определенная на множестве вершин ( соответственно ребер) и разнозначная на концах каждого ребра ( соответственно на ребрах каждой звезды) графа. [16]
Настоящая глава содержит дальнейшее подтверждение широкой применимости его метода. Мы займемся перечислением графов, корневых графов, связных графов, 2-раскрашенных графов, локально ограниченных графов, раскрашенных графов, булевых функций и эйлеровых графов. [17]
Стандартное представление, принятое в работах по эвристическому поиску, - это направленный граф, узлы которого представляют дискретные состояния, а дуги, выходящие из некоторого узла, представляют процесс генерирования возможных его преемников. Множество X и функция генерирования множеств преемников Г: Х - 2Х определяют граф задачи. При этом стандартное представление задач в отношении полезности уступает упомянутому выше представлению ( X, Г) в виде раскрашенного графа. [18]
Пусть ребра графа правильно раскрашены и пусть х и у - два различных цвета. Двухцветной ( х, у) - цепью назовем элементарную цепь, состоящую из ребер графа, окрашенных в цвета х и у. Понятно, что цвета х и у на такой цепи чередуются. Двухцветная цепь может, в частности, состоять из одной вершпны, из одного ребра или быть элементарным циклом. Нетрудно убедиться в том, что две максимальные ( х, г /) - цепи ( с одной и той же парой цветов х, у) не могут иметь общих вершин. Отсюда, в частности, следует, что перекраска любой максимальной двухцветной цепи правильно раскрашенного графа не нарушает правильности его раскраски. А; если же у - конец максимальной ( х, у) - цепи А, содержащей хотя бы одно ребро, то в М один из цветов х или у заменяется при перекраске другим. [19]