Случай 1: (петли не допускаются)
Матрица для N узлов будет иметь N*N ячеек.
Мы можем игнорировать основную диагональ, поэтому у нас осталось N * N - N клеток.
Поскольку матрица симметрична, мы можем избавиться от половины из них, поэтому у нас осталось (N * N - N) / 2 клеток
Каждая ячейка будет представлена битом, поэтому нам нужны только (N * N - N) / 2 биты
Случай 2: (допускаются циклы)
Аналогичновыше, но нам понадобятся дополнительные N биты для главной диагонали.
Таким образом, всего нам потребуется ( N * N - N) / 2 + N биты