Использование z3 для поиска графа с определенными свойствами ⇐ Python

[Anonymous]

Я использую z3 в Python для проверки некоторых свойств графа в соответствии с версией проблемы с раскраской. На очень высоком уровне я пишу некоторое ограничение, и когда z3 не может решить проблему, меня интересует именно этот граф.
Дано:

• Nt: общее количество узлов
• M: матрица смежности
• X цвет узла i (0 или 1)
• Nborder: количество узлов некоторого подграфа, называемого границей (граничными узлами являются первые узлы Nborder)
• некоторые ограничения, связанные с моей проблемой с раскраской, которые нет необходимости здесь подробно описывать.

Сначала я хотел проверить график, на котором все граничные узлы будут иметь одинаковый цвет . Это понимание списка, которое я написал для этого ограничения:

Код: Выделить всё

const1 = [sum([X[i]*(1-X[j]) for i in range(Nborder) for j in range(Nborder) ])>=1]

то есть, он заставляет два узла на границе иметь разный цвет. Если это не удается, то M заставляет все узлы на границе иметь один и тот же цвет, следовательно, Z3 не может решить эту проблему. Затем я сохраняю М для дальнейшего использования. Эта линия сработала отлично.
Теперь я хочу взглянуть на эти графы, у которых есть дополнительное следующее свойство:
На границе есть как минимум два узла, у которых есть ровно два соседа. цвета 1.
Поэтому я написал это дополнительное ограничение:

Код: Выделить всё

const2= [sum([(sum([M[i][j]*X[j] for j in range(Nt)]) ==2) for i in range(Nborder)])

Подробнее здесь: [url]https://stackoverflow.com/questions/79017839/using-z3-to-find-graph-with-certain-properties[/url]