сортировка симметричной 0/1-матрицы

[maxal]

Дана симметричная матрица с элементами 0 и 1 и нулевой главной диагональю, в которой никакие 4 единицы не стоят в вершинах прямоугольника (с координатами $(x,y)$, $(u,v)$, $(x,v)$, $(u,y)$ для $x<u$ и $y<v$),

1) Докажите, что её можно отсортировать одновременной перестановкой строк и столбцов (т.е. сохраняя симметричность) к виду, где количество единиц в строках не убывает, а сами строки упорядочены лексикографически.

2) Тот же вопрос для матриц без ограничения на прямоугольники из единиц.

[DeBill]

Ну, для 2) есть контрпример: матрица смежности графа $K_{3,1}+K_{4,2}$...

[maxal]

DeBill, про 2) всё верно. А вот матрицы из 1) соответствуют графам без $K_{2,2}$ (или $C_4$), называемыми свободными от квадратов (squarefree graphs).

[TOTAL]

Двоичное число в $i$-ой строке обозначим $E_i$
Cначала упорядочиваем по возрастанию числа единиц в строках.
Затем внутри строк с одинаковым числом единиц меняем соседние строки, опуская вниз большее число.
Величина $\sum iE_i$ возрастает.

Нет, не то, зачеркиваю

[DeBill]

maxal
Что-то у меня не получается...
Пусть вершина 1 соединена с 2,3,4;
Вершины 5 и 6 соединены четырьмя путями длины три.
Циклов запрещенных вроде нет.
Имеем: три вершины степени 1;
8 вершин степени 2;
одна - степени 3;
две - степени 4.
Получается, что число в строке для вершины степени 3 - больше чисел в строках для вершин степени 4.

[maxal]

DeBill, да, не выходит каменный цветок. Давайте потребуем от графов связности - можно в этом случае отсортировать?

[maxal]

Пример отсортированной матрицы для графа с 18 вершинами и максимальным числом ребер (39):

000000000000000111
000000000000111000
000000000111000000
000000001001001001
000000010001010010
000000100010100010
000001000010001100
000010000100010100
000100000100100001
001000011000100100
001001100000010001
001110000000001010
010001001100000010
010010010010000001
010100100001000100
100000110100001000
100011000001100000
100100001010010000