5cdc/nz5 => 33pp

В этом посте пытаюсь разобраться в том, можно ли по 5cdc решению или по nz5 потоку построить какой-нибудь (3,3)-parity-pair flow-cover.

О чём речь:

• todo: картинка для 33pp
• todo: картинка для получающегося 5cdc (который не o5cdc)
• todo: картинка для получающегося nz5

todo: проверить, какие nz5 мы получаем из всего набора 33pp

Дальше: рассмотрим табличку из статьи Dezheng Xie и Cun-Quan Zhang (Flows, flow-pair covers and cycle double covers):

f1	f2	nz5
0	±2	±1
±2	0	±3
±2	±2	±2 или ±4
±1	±1	±2 или ±1

А в (3,3)-edp имеем пары:

• 0, 2
• 0, 1
• 1, 1
• 1, 0
• 2, 0

Сразу видим отсюда, что:

• по ±4 в nz5 мы сразу можем восстановить местоположение для пар (f1, f2) вида (±2, ±2) и то что они сонаправленны
• по ±3 мы можем только сказать, что неупорядоченно имеем пару (±2, 0)
• по ±2 мы можем понять, что f1 совпадает с f2, с точностью до направления
• если nz5 = 3f1/2 + f2/2, то все рёбра f1 совпадают по направлению с рёбрами nz5, а там где в f1 стоит 0 - те рёбра совпадают по направлению с f2

про 5cdc тоже можно сделать выводы:

• todo нужно переписать theorem 6.1 через 33pp, и распарсить lemma 2.5 из статьи
• lemma 2.5 - Let H be a subgraph of G. Then G admits a nowhere-zero 4-flow (D, f) with E_{f=2}= E(H) <=> G has a 2-cycle cover with the edges of H covered twice and all other edges covered once.
• [15] W.T. Tutte, On the imbedding of linear graphs in surfaces
• [12] P.D. Seymour, On Tutte’s extension of the four-color problem
• ну не знаю - проще книжку Жанга распарсить ещё раз
• theorem 5.1 - (3,3)-pp <=> (3,3)-edp
• в одну сторону => очевидно: если имели потоки f1,f2, то новые будут (f1+f2)/2, (f1-f2)/2
• в другую <= тоже: если имели потоки f1,f2, то новые будут (f1+f2), (f1-f2)
• theorem 6.1 - 5cdc <=> имеем (4,4)-edp
• в одну сторону => очевидно: вместо циклов рассматриваем 2-потоки f_i, i=1,2,3,4. А циклы были C_i, i=1,2,3,4,5. Рассмотрим новые циклы - C_ij = C_i Δ C_j, f_ij = соответсвующий поток. Тогда f_12+2f2, f_34+2f4 - искомое (4,4)-edp, причём C_5 можно вытащить по несложной логике. TODO: но я в любом случае хочу переписать это всё в (4,4)-pp, а не edp.
• в другую сторону <= по модулю lemma 2.5 тоже очевидно: имеем циклы f1,f2. имеем разбиение рёбер на: A=E_{f1=2}, B=E{f2=2}, C=E_{f1=odd}∪E_{f2=odd}. Юзаем лемму 2.5 - получаем 4 цикла. Если ребро из A ∪ B, то оно покрыто 2 раза. Если оно из E_{f1=odd} ∩ E_{f2=odd}, то оно снова покрыто 2 раза. Ну а оставшиеся - 1 раз, и мы докидываем на них 5ый цикл. TODO: переписать это док-во на (4,4)-pp рельсы.
• TODO: что даёт замена (4,4)-edp на (3,3)-edp? скажем, в плане получаемых nz5 или 5cdc.

Нашёл тут интересного:

• Разложение nz3 в 2 цикла очень простое - в один из них попадают все рёбра с весом 2, а также все рёбра веса 1 по часовой стрелке; во второй - все рёбра веса 2  + рёбра веса 1 против часовой;
• Кажется я догнал как связаны 5cdc и nz5, получаемые из 33pp - можно просто глянуть на веса рёбер в nz5 и ровно такие и кинуть на циклы из 5cdc (а C5 достанется вес 0, например). А это значит что можно проверить гипотезу, что по любому 5cdc можно построить какой-нибудь 33pp или nz5, беру nz5, одному из циклов кидаю вес 0, а на два цикла кидаю вес 1, на оставшиеся два - вес 2 (и ещё надо им как-то перебрать ориентацию), суммирую и проверяю, что получаются nz5 и 33pp.
• так вот, 33pp из 5cdc: пытаемся накинуть потоки, и после этого строим (f1+f2)+(f3+f4) и (f1+f2)-(f3+f4), nz5 = 2*(f1+f2)+(f3+f4)
• Судя по числам, уже в 18.05g1 и в 18.05g2 есть 5cdc,  из которых нельзя напрямую получить 33pp, например: g1: 8544/9476, g2: 8782/9314.

TODO: следующий вопрос - есть ли среди этих 5cdc такие, что C5 - это dominating cycle, или C5 - это dominating circuit (хотя можно ослабить до того, что доминирующим будет любой из циклов, а не конкретно C5).

неослабленный вариант:

g1:

all 5cdc solutions: 9476

with 33pp: 8544

all 5cdc solutions with domcyc: 1532

with 33pp: 1360

relaxed: 1492

all 5cdc solutions with domcirc: 896

with 33pp: 840

relaxed: 880

g2:

all 5cdc solutions: 9314

with 33pp: 8782

all 5cdc solutions with domcyc: 1388

with 33pp: 1338

relaxed: 1376

all 5cdc solutions with domcirc: 818

with 33pp: 792

relaxed: 806

Ну и нормально, остановлюсь на этом, TODO: нарисовать пример и закончить и пойти дальше.

TODO: наверняка здесь ещё будет блок текста про перескоки с одного решения на другое. Через nz5, например. TODO: глянуть такое - фиксирую o5cdc, считаю для каждого nz5 - сколько ему соответствует разных 33pp, и для данного o5cdc выписываю по каждому nz5 сколько у него 33pp. просто глянуть - какие бывают разбросы.

можно ли найти циклы из 5cdc внутри f1 или f2? кажется C5 там точно есть, вокруг которого и строится 33pp; остальных кажется нет, ну или не факт, что будут
todo: можно ли как-то перейти к o5cdc?

todo: дописать
todo: 333pp <=> o5cdc (в одну сторону очевидно, <=, а вот в другую надо подумать ещё)