Рассмотрим ориентированный ациклический граф G(V,E), где V={1,2,3,4,5,6,7} и E={ (1,2),(1,3),(1,4),(2,5),(3,5),(4,6),(5,7),(6,7)}
Проблема здесь состоит в том, чтобы исследовать несколько линейных порядков графа. Следовательно, как кодировать/декодировать его таким образом, чтобы он всегда приводил к возможному линейному упорядочению графа (топологическому порядку)?
Одним из возможных способов изучения различных линейных порядков DAG может быть определение строки (хромосомы) одинакового размера V, где каждый элемент строки обозначает стоимость для каждой вершины, т. е. стоимость i-й вершины задается i-м элементом в строке.
Для декодирования можно использовать специальный алгоритм поперечного графа. Каждый раз, когда может быть найдено больше, чем вершина со всеми посещенными ее предшественниками, алгоритм должен посетить затем в порядке возрастания на основе стоимости, предоставленной строкой.
Для приведенного выше DAG и строки стоимости {0,6, 0,8, 0,5, 0,1, 0,5, 0,3, 0,9} полученный линейный порядок будет {1, 4, 6, 3, 2, 5, 7}.
