Расширение матрицы смежностей

Такая концепция есть: иерархические матрицы (с соответсвующим набором операций иерархической матричной арифметики). В данном представлении, матрица представляет собой в общем случае - дерево матриц, c данными хранящимися на листьях, при этом листья могут быть расположены на разных уровнях.

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

Кроме того, замечание Mikhailo имеет полную силу:

соседствование 3 с индивидуальными элементами 2.1, 2.2, 2.3 и 2.4 не определяется напрямую из структуры (в общем случае и с произвольными модификациями областей).

Поэтому, советую обратить внимание на более простые структуры данных и представление смежности. В зависимости от прикладной задачи, такие структуры как k-d деревья могут быть гораздо предпочтительнее.

В общем случае - никак. Просто потому, что одного описания зеленой матрицы недостаточно - надо еще описывать, как ее НОВЫЕ ЭЛЕМЕНТЫ (на которые она разбита) соотносятся со старыми.

Из зеленой матрицы никак не следует, что с 3 смежны 2.1 и 2.3, а не 2.2 и 2.4. Если вы замените в зеленой матрице 2.1 и 2.3, зеленая матрица не изменится, а вот красные поменяются. Так что ожной зеленой матрицы мало, и такая операция невозможна.