Побудова n-мірних паттернів як задача побудови та пофарбування n-дольних графів та їх мінорів

Abstract

У статті розглядається проблема побудови n-мірних паттернів. Вирішення цієї задачі зводиться до пофарбування n-дольних графів та їх мінорів виду Kn . Доведено, що будь-який n-дольний граф може бути стягнутий у зірку виду Kn . Показано зв¢язок n-мірних паттернів із n-дольними графами, а також, що степінь вершин графа визначає у кінцевому випадку множину оптимальних розв¢язків при побудові паттернуThe problem of n-dimensional pattern design is investigated. The resolving of this problem is regarded as the problem of n-partite graph coloring and its minor Kn. It is shown that any n-partite graph can be reduced to the graph-star Kn. The relationship between n-dimensional patterns and n-partite graphs is proved and it is shown that the vertex degree defines the range of optimal n-dimensional pattern constructions