Формула максимума рёбер графа с условиями

[Halenner]

Здравствуйте. Возникла необходимость подсчёта максимума рёбер для графа с ниже описанными условиями. Сам я не далеко математик, поэтому даже не знаю, как подступиться...
В графе на квадратной сетке, где есть 8 видов вершин: A, B, C, Z, Y, X, N, M.
Рёбра образуются, когда подходящие пары вершин стоят на одной линии (только горизонталь или вертикаль). Эти пары:
A-B, B-C, C-Z, Z-Y, Y-X, X-A, M-A, M-B, M-C, M-Z, M-Y, M-X, M-N
Некоторым парам запрещено находиться на одной линии. Эти пары:
A-Z, B-Y, C-X, N-A, N-B, N-C, N-Z, N-Y, N-X, M-M
Вершины непрозрачны, т.е. ребро не может быть образовано сквозь вершину.
Касаемо количества вершин, могу только обозначить:
A=a, B=b, C=c, Z=z, Y=y, X=x, M=m, N=n
Если возможно, подскажите формулу пожалуйста.
Если необходимо, могу привести рассчитанные алгоритмом имитации отжига результаты для некоторых конфигураций.

[b4b5]

Можно попробовать нарисовать на бумажке в клеточку, возникнут идеи.

[svv]

Поясните условие задачи. А то я могу выстроить по горизонтали цепочку ABABA... хоть из миллиона вершин и соединить соседние рёбрами.

[Halenner]

svv в сообщении #1718146 писал(а):

Поясните условие задачи. А то я могу выстроить по горизонтали цепочку ABABA... хоть из миллиона вершин и соединить соседние рёбрами.

a, b, c, z, y, x, m, n - натуральные числа. Т.е. количество вершин ограничено, просто это переменные. Прошу прощения, что не упомянул это сразу.

[Halenner]

svv в сообщении #1718146 писал(а):

Поясните условие задачи. А то я могу выстроить по горизонтали цепочку ABABA... хоть из миллиона вершин и соединить соседние рёбрами.

Или же требуется иное пояснение?

[svv]

Спасибо, теперь, вроде, понял. Задано количество вершин каждого вида. Расставим их на сетке так, чтобы можно было их соединить как можно большим числом рёбер, согласно Вашим правилам. И Вас интересует это максимально возможное число рёбер.

Вопросы:
1) Можно ли соединять ребром вершины, которые находятся не в соседних узлах сетки? Иначе говоря, обязаны ли рёбра иметь длину 1?

2) Если рёбра длиннее 1 допускаются, то могут ли они пересекаться?

3) Обязан ли граф быть связным, или он может состоять из нескольких несвязанных кусков?

4)

Halenner в сообщении #1718144 писал(а):

Некоторым парам запрещено находиться на одной линии. Эти пары:
A-Z, B-Y, C-X, N-A, N-B, N-C, N-Z, N-Y, N-X, M-M

То есть мы их не просто ребром не можем соединить, их даже на одной горизонтали/вертикали ставить нельзя, верно?

5) Количества вершин каждого типа на практике совершенно произвольны, или всё-таки подчиняются каким-то правилам?

[Halenner]

1) Да, можно - рёбра не обязаны быть длины 1.
2) Да, рёбра могут пересекаться.
3) Нет, граф не обязан быть связным.
4) Да, верно, однако тут мне следует на всякий случай уточнить: их запрещено ставить на одной линии только тогда, когда они в оказываются в прямой видимости друг друга (A-Z - запрещено, A-M-Z - разрешено).
5) Произвольны, к сожалению.