Изменения

Пусть <tex>G</tex> — неориентированный связный граф, <tex>V</tex> — множество его вершин, <tex>E</tex> — ребер; всего вершин <tex>n</tex>, а ребер <tex>m</tex> . Будем хранить ребра в виде списков связности. Пусть <tex>L_v</tex> — множество вершин, соединенных с <tex>v</tex> ребром, <tex>L</tex> — множество всех <tex>L_v</tex>. Для каждой вершины <tex>v</tex> введем также множество <tex>M_v</tex>, хранящее в себе неупорядоченные пары вершин из <tex>L_v</tex>. Обозначим через <tex>M</tex> множество всех <tex>M_v</tex>. Таким образом если для всех вершин <tex>v</tex> вершины из <tex>L_v</tex> разбиты на пары в <tex>M_v</tex>, то с точностью до первого ребра на <tex>G</tex> задан порядок обхода: пара <tex>(u,w)</tex> в <tex>L_v</tex> означает, что придя из <tex>u</tex> далее нужно идти в <tex>w</tex> (или наоборот).

Напомним, что <tex>d(v)</tex> — степень вершины <tex>v</tex> (количество ребер, которые из нее выходят). Пусть <tex>d(G)</tex> — средняя степень среди вершин <tex>G</tex>, <tex>\Delta G</tex> — максимальная степень среди вершин <tex>G</tex>, а <tex>\delta d(G) = \frac{1} {2m} \sum_{v \in V}d(v)^2</tex>.Есть три способа выбрать две вершины для мутации. '''Ориентированный на вершины''' Сначала выбираем случайно <tex>v</tex> из <tex>V</tex>. Затем случайно и независимо выбираем <tex>u</tex> и <tex>w</tex> из <tex>L_v</tex>. Вероятность <tex>p</tex> выбрать пару <tex>(u,w)</tex> в <tex>L_v</tex> удовлетворяет соотношению: <tex>p = \frac{1} {d(v)^2n} = \frac{d(G)} {2d(v)^2m} \ge \frac{d(G)} {2 \Delta (G)^2m}</tex>  '''Ориентированный на ребра''' Выбираем случайно вершину <tex>u</tex> из всех <tex>2m</tex> вершин во всех списках <tex>L</tex>. Пусть она оказалась в <tex>L_v</tex>. Далее случайно выбираем <tex>w</tex> из <tex>L_v</tex>. Вероятность <tex>p</tex> выбрать пару <tex>(u,w)</tex> в <tex>L_v</tex> удовлетворяет соотношению: <tex>p = \frac{1} {2d(v)m} \ge \frac{1} {2 \Delta (G)m}</tex>  '''Ориентированный на пары вершин''' Выбираем случайно пару <tex>(u,w)</tex> из всех пар для всех <tex>2m</tex> вершин во всех списках <tex>L</tex> вершин во всех списках <tex>L</tex>. Пусть обе вершины присутствуют в <tex>L_v</tex>. Тогда вероятность <tex>p</tex> выбрать пару <tex>(u,w)</tex> в <tex>L_v</tex> удовлетворяет соотношению: <tex>p = \frac{1} {2\delta d(G)m}