WikiDer > Интегральный график

Integral graph

в математический поле теория графов, интегральный график это граф, матрица смежностис спектр полностью состоит из целых чисел. Другими словами, граф является интегральным графом, если все корни из характеристический многочлен его матрицы смежности - целые числа.^[1]

Это понятие было введено в 1974 г. Harary и Швенк.^[2]

Примеры

В полный график K_п является неотъемлемой частью для всех п.
В безреберный граф ${ displaystyle { bar {K}} _ {n}}$ является неотъемлемой частью для всех п.
Среди кубических симметричных графов график полезности, то Граф Петерсена, то Науру график и График дезарга являются цельными.
В График Хигмана – Симса, то График Холла – Янко, то Граф Клебша, то Граф Хоффмана – Синглтона, то Граф Шриханде и Граф Хоффмана являются цельными.
А регулярный граф является периодический тогда и только тогда, когда это интегральный граф.
А регулярный граф это допускает совершенный государственный перевод является интегральным графом.
В Судоку графики, графы, вершины которых представляют ячейки доски судоку, а ребра представляют собой ячейки, которые не должны быть равными, являются целыми.^[3]

^ Вайсштейн, Эрик В. «Интегральный граф». MathWorld.
^ Харари, Ф. и Швенк, А. Дж. "Какие графы имеют интегральный спектр?" В графах и комбинаторике (ред. Р. Бари и Ф. Харари). Берлин: Springer-Verlag, стр. 45–51, 1974.
^ Сандер, Торстен (2009), «Графики судоку целостны», Электронный журнал комбинаторики, 16 (1): Примечание 25, 7, Г-Н 2529816