Целый граф (Eyldw ijgs)

Перейти к навигации Перейти к поиску

Целый граф (целочисленный граф) — граф, спектр матрицы смежности (инвариант графа) которого состоит полностью из целых чисел. Другими словами, граф является целым графом, при условии, что все корни характеристического многочлена его матрицы смежности являются целыми числами[1]. Понятие ввели в 1974 году Харари и Швенк[2].

Примеры:

Регулярный граф является периодическим[англ.] тогда и только тогда, когда он целый. Граф регулярных блужданий, удовлетворяющий условиям идеальной передачи квантового состояния[англ.], является целым графом.

Примечания

[править | править код]
  1. Weisstein, Eric W. Integral Graph (англ.) на сайте Wolfram MathWorld.
  2. Harary F., Schwenk A. J. Which Graphs have Integral Spectra? // Graphs and Combinatorics / R. Bari и F. Harary. — Berlin: Springer-Verlag, 1974. — С. 45—51.
  3. Torsten Sander. Sudoku graphs are integral // Electronic Journal of Combinatorics. — 2009. — Т. 16, вып. 1. — С. Note 25, 7. Архивировано 15 апреля 2011 года.