Перейти к навигации Перейти к поиску
В математической области теории графов , интеграл граф называется граф, матрица смежности «ы спектр целиком состоит из целых чисел. Другими словами, график является интегральным графом , если все корни этого характеристического полинома его матрицы смежности представляют собой целые числа. [1]
Это понятие было введено в 1974 году Харари и Швенком. [2]
Примеры [ править ]
- Полный граф К п является неотъемлемой частью для всех п .
- Edgeless график является неотъемлемой частью для всех п .
- Среди кубических симметричных графов полезности графа , то граф Петерсен , то граф Науру и Desargues графа является неотъемлемой частью.
- График Хигмана-Sims , то граф Холла-Янко , то граф Клебша , то график Hoffman-Singleton , то граф Шрикханде и график Hoffman являются неотъемлемой частью.
- Регулярный граф является периодическим , если и только если она является составным графом.
- График ходить регулярные , допускающий совершенное состояние передачи является составным графом.
- В графы Судоку , графы, вершины представляют собой клетки доски судоку и чьи края представляют собой клетки , которые не должны быть равны, являются неотъемлемой частью. [3]
Ссылки [ править ]
- ^ Вайсштейн, Эрик В. «Интегральный граф» . MathWorld .
- ^ Harary, F. и Schwenk, AJ "Какие графы имеют интегральные спектры?" В графах и комбинаторике (ред. Р. Бари и Ф. Харари). Берлин: Springer-Verlag, стр. 45–51, 1974.
- ^ Сандер, Торстен (2009), «Графики судоку являются интегральными» , Электронный журнал комбинаторики , 16 (1): Примечание 25, 7, MR 2529816