Побудова n-мірних паттернів як задача побудови та пофарбування n-дольних графів та їх мінорів
Вантажиться...
Дата
2008
Автори
ORCID
DOI
Науковий ступінь
Рівень дисертації
Шифр та назва спеціальності
Рада захисту
Установа захисту
Науковий керівник
Члени комітету
Видавець
НТУ "ХПІ"
Анотація
У статті розглядається проблема побудови 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
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
Опис
Ключові слова
побудова паттерну, мінор, зірка, вершини графа, pattern, minor, n-partite graph, graph-star
Бібліографічний опис
Скрильник І. І. Побудова n-мірних паттернів як задача побудови та пофарбування n-дольних графів та їх мінорів / І. І. Скрильник // Вестник Нац. техн. ун-та "ХПИ" : сб. науч. тр. Темат. вып. : Информатика и моделирование. – Харьков : НТУ "ХПИ", 2008. – № 24. – С. 151-160.