Граф Рукса

График ходов шахматной ладьи

В теории графов граф ладьи — это неориентированный граф , который представляет все допустимые ходы шахматной фигуры ладьи на шахматной доске . Каждая вершина графа ладьи представляет собой квадрат на шахматной доске, и между любыми двумя квадратами, разделяющими строку (ряд) или столбец (вертикаль), есть ребро , квадраты, между которыми может перемещаться ладья. Эти графы можно построить для шахматных досок любой прямоугольной формы. Хотя графы ладьи имеют лишь второстепенное значение в шахматной науке, они более важны в абстрактной математике графов благодаря своим альтернативным конструкциям: графы ладьи являются декартовым произведением двух полных графов и являются линейными графами полных двудольных графов . Графы квадратной ладьи составляют двумерные графы Хэмминга .

Графы ладьи высоко симметричны, имея симметрии, переводящие каждую вершину в каждую другую вершину. В графах ладьи, определенных с помощью квадратных шахматных досок, более строго, каждые два ребра симметричны, и каждая пара вершин симметрична каждой другой паре на том же расстоянии в ходах (что делает граф дистанционно-транзитивным ). Для прямоугольных шахматных досок, ширина и высота которых взаимно просты , графы ладьи являются циркулянтными графами . За одним исключением, графы ладьи можно отличить от всех других графов, используя только два свойства: количество треугольников, которым принадлежит каждое ребро, и существование уникального 4 - цикла, соединяющего каждую несмежную пару вершин.

Графы ладьи являются совершенными графами . Другими словами, каждое подмножество клеток шахматной доски может быть раскрашено так, что никакие два квадрата в строке или столбце не будут иметь одинаковый цвет, используя количество цветов, равное максимальному количеству квадратов из подмножества в любой отдельной строке или столбце ( число клик индуцированного подграфа ). Этот класс индуцированных подграфов является ключевым компонентом разложения совершенных графов, используемого для доказательства сильной теоремы о совершенном графе , которая характеризует все совершенные графы. Число независимости и число доминирования графа ладьи оба равны меньшему из ширины и высоты шахматной доски. В терминах шахмат число независимости — это максимальное количество ладей, которые можно разместить, не нападая друг на друга; число доминирования — это минимальное количество, необходимое для атаки на все незанятые клетки доски. Графы ладьи являются хорошо покрытыми графами , что означает, что размещение неатакующих ладей по одной за раз никогда не может застрять, пока не будет достигнут набор максимального размера.

Определение и математические конструкции

Граф ладьи n × m представляет собой ходы ладьи на шахматной доске n × m . ^[1] Его вершины представляют собой клетки шахматной доски и могут быть заданы координатами ( x , y ) , где 1 ≤ x ≤ n и 1 ≤ y ≤ m . Две вершины с координатами ( x ₁ , y ₁ ) и ( x ₂ , y ₂ ) являются смежными тогда и только тогда, когда x ₁ = x ₂ или y ₁ = y ₂ . (Если x ₁ = x ₂ , вершины разделяют вертикаль и соединяются вертикальным ходом ладьи; если y ₁ = y ₂ , они разделяют ранг и соединяются горизонтальным ходом ладьи.) ^[1]

Все квадраты одного ряда или вертикали напрямую соединены друг с другом, поэтому каждый ряд и вертикаль образуют клику — подмножество вершин, образующих полный граф . Весь граф ладьи для шахматной доски n × m может быть образован из этих двух видов клик, как декартово произведение графов K _n ◻ K _m . ^[2] Поскольку граф ладьи для квадратной шахматной доски является декартовым произведением клик равного размера, он является примером графа Хэмминга . Его размерность как графа Хэмминга равна двум, и каждый двумерный граф Хэмминга является графом ладьи для квадратной шахматной доски. ^[3] Графы квадратной ладьи также называются « графами латинских квадратов »; применительно к латинскому квадрату его ребра описывают пары квадратов, которые не могут содержать одно и то же значение. ^[4] Графы судоку — это графы ладьи с некоторыми дополнительными ребрами, соединяющими квадраты головоломки судоку, которые должны иметь неравные значения. ^[5]

Дуопризма 3-3 , четырехмерный выпуклый многогранник, имеющий граф ладьи 3 × 3 в качестве своего скелета.

Геометрически графы ладьи могут быть образованы наборами вершин и ребер ( скелетами ) семейства выпуклых многогранников , декартовых произведений пар соседних многогранников . ^[6] Например, дуопризма 3-3 представляет собой четырехмерную фигуру, образованную как декартово произведение двух треугольников , и имеет граф ладьи 3 × 3 в качестве своего скелета. ^[7]

Регулярность и симметрия

Сильная регулярность

Мун (1963) и Хоффман (1964) отмечают, что граф ладьи (или, что то же самое, как они его описывают, линейный граф полного двудольного графа ) обладает всеми следующими свойствами: ${\displaystyle m\times n}$ ${\displaystyle K_{m,n}}$

• Он имеет вершины, по одной на каждую клетку шахматной доски. Каждая вершина примыкает к ребрам, соединяя ее с клетками того же ранга и клетками того же ряда. ${\displaystyle mn}$ ${\displaystyle m\times n}$ ${\displaystyle m+n-2}$ ${\displaystyle m-1}$ ${\displaystyle n-1}$
• Треугольники в графе ладьи образованы тройками квадратов в пределах одной вертикали или горизонтали. Когда , ровно ребра (соединяющие квадраты в одной вертикали) принадлежат треугольникам; остальные ребра (соединяющие квадраты в одной вертикали) принадлежат треугольникам. Когда , каждое ребро принадлежит треугольникам. ${\displaystyle m\neq n}$ ${\displaystyle n{\tbinom {m}{2}}}$ ${\displaystyle m-2}$ ${\displaystyle m{\tbinom {n}{2}}}$ ${\displaystyle n-2}$ ${\displaystyle m=n}$ ${\displaystyle m-2=n-2}$
• Каждые две несмежные вершины принадлежат уникальному -вершинному циклу , а именно единственному прямоугольнику, использующему эти две вершины в качестве углов. ${\displaystyle 4}$

Они показывают, что за исключением случая , эти свойства однозначно характеризуют граф ладьи. То есть, графы ладьи являются единственными графами с таким количеством вершин, ребер, треугольников на ребро и с уникальным 4-циклом через каждые две несмежных вершины. ^{[8] [9]} ${\displaystyle m=n=4}$

Когда , эти условия можно сократить, заявив, что граф ладьи является сильно регулярным графом с параметрами . Эти параметры описывают количество вершин, количество ребер на вершину, количество треугольников на ребро и количество общих соседей для двух несмежных вершин соответственно. ^[1] И наоборот, каждый сильно регулярный граф с этими параметрами должен быть графом ладьи, если только . ^{[8] [9]} ${\displaystyle m=n}$ ${\displaystyle n\times n}$ ${\displaystyle \operatorname {srg} (n^{2},2n-2,n-2,2)}$ ${\displaystyle n\times n}$ ${\displaystyle n=4}$

Граф Шрикханде, вложенный в тор. Это не граф ладьи, но он сильно регулярен с теми же параметрами, что и граф ладьи. ${\displaystyle 4\times 4}$

Когда , существует другой сильно регулярный граф, граф Шрикханде , с теми же параметрами, что и граф ладьи. ^[10] Граф Шрикханде подчиняется тем же свойствам, что и граф ладьи. Его можно отличить от графа ладьи тем, что окрестность каждой вершины в графе Шрикханде связана, образуя -цикл . Напротив, в графе ладьи окрестность каждой вершины образует два треугольника, один для ее ранга, а другой для ее линии, без каких-либо ребер из одной части окрестности в другую. ^[11] Другой способ отличить граф ладьи от графа Шрикханде использует числа покрытия кликами : граф ладьи может быть покрыт четырьмя кликами (четырьмя горизонталями или четырьмя вертикалями шахматной доски), тогда как для покрытия графа Шрикханде требуется шесть клик. ^[10] ${\displaystyle n=4}$ ${\displaystyle 4\times 4}$ ${\displaystyle 4\times 4}$ ${\displaystyle 6}$ ${\displaystyle 4\times 4}$ ${\displaystyle 4\times 4}$ ${\displaystyle n=4}$

Симметрия

Графы ладьи являются вершинно-транзитивными , что означает, что они имеют симметрии, переводящие каждую вершину в каждую другую вершину. Это означает, что каждая вершина имеет равное количество ребер: они - регулярные . Графы ладьи являются единственными регулярными графами, образованными из ходов стандартных шахматных фигур таким образом. ^[12] Когда , симметрии графа ладьи образуются путем независимой перестановки строк и столбцов графа, поэтому группа автоморфизмов графа имеет элементы. Когда , граф имеет дополнительные симметрии, которые меняют местами строки и столбцы, поэтому количество автоморфизмов равно . ^[13] ${\displaystyle (m+n-2)}$ ${\displaystyle m\neq n}$ ${\displaystyle m!n!}$ ${\displaystyle m=n}$ ${\displaystyle 2n!^{2}}$

Любые две вершины в графе ладьи находятся на расстоянии один или два друг от друга, в зависимости от того, являются ли они смежными или несмежными соответственно. Любые две несмежных вершины могут быть преобразованы в любые другие две несмежных вершины с помощью симметрии графа. Когда граф ладьи не является квадратным, пары смежных вершин попадают в две орбиты группы симметрии в зависимости от того, являются ли они смежными по горизонтали или вертикали, но когда граф квадратный, любые две смежные вершины также могут быть отображены друг в друга с помощью симметрии, и граф, следовательно, является дистанционно-транзитивным . ^[14]

Когда и взаимно просты , группа симметрии графа ладьи содержит в качестве подгруппы циклическую группу , которая действует путем циклической перестановки вершин. Следовательно, в этом случае граф ладьи является циркулянтным графом . ^[15] ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle S_{m}\times S_{n}}$ ${\displaystyle C_{mn}=C_{m}\times C_{n}}$ ${\displaystyle mn}$

Графы квадратной ладьи являются связно-однородными , что означает, что любой изоморфизм между двумя связанными индуцированными подграфами может быть расширен до автоморфизма всего графа. ^[16]

Другие свойства

Совершенство

Граф ладьи 3×3 (граф дуопризмы 3-3 ), раскрашенный тремя цветами и показывающий клику из трех вершин. В этом графе и каждом из его индуцированных подграфов хроматическое число равно числу клики, поэтому это совершенный граф.

Граф ладьи также можно рассматривать как линейный граф полного двудольного графа K _{n , m} — то есть, он имеет одну вершину для каждого ребра K _{n , m} , и две вершины графа ладьи являются смежными тогда и только тогда, когда соответствующие ребра полного двудольного графа имеют общую конечную точку. ^{[2] [17]} В этом представлении ребро в полном двудольном графе от i -й вершины с одной стороны двудольного графа до j -й вершины с другой стороны соответствует шахматному квадрату с координатами ( i , j ) . ^[1]

Любой двудольный граф является подграфом полного двудольного графа, и соответственно любой линейный граф двудольного графа является индуцированным подграфом графа ладьи. ^[18] Линейные графы двудольных графов являются совершенными : в них и в любом из их индуцированных подграфов количество цветов, необходимых для любой раскраски вершин , совпадает с количеством вершин в наибольшем полном подграфе . Линейные графы двудольных графов образуют важное семейство совершенных графов: они являются одним из небольшого числа семейств, использованных Чудновским и др. (2006) для характеристики совершенных графов и для того, чтобы показать, что каждый граф без нечетных дыр и без нечетных антидыр является совершенным. ^[19] В частности, графы ладьи сами по себе совершенны.

8-раскраска шахматного графа, полученного из таблицы Кэли конечной группы

Поскольку граф ладьи является совершенным, количество цветов, необходимых для любой раскраски графа, равно размеру его наибольшей клики. Клики графа ладьи являются подмножествами одной строки или одного столбца, и самые большие из них имеют размер max( m , n ) , так что это также хроматическое число графа. n -раскраска графа ладьи n × n может быть интерпретирована как латинский квадрат : он описывает способ заполнения строк и столбцов сетки n × n n различными значениями таким образом, что одно и то же значение не встречается дважды ни в одной строке или столбце. ^[20] Таким же образом раскраска прямоугольного графа ладьи соответствует латинскому прямоугольнику . ^[21] Хотя нахождение оптимальной раскраски графа ладьи является простым, NP-полной задачей является определение того, можно ли расширить частичную раскраску до раскраски всего графа (эта задача называется расширением предварительной раскраски ). Эквивалентно, задача определения того, можно ли дополнить частичный латинский квадрат до полного латинского квадрата, является NP-полной. ^[22]

Независимость

Неатакующая расстановка восьми ладей на шахматной доске, образующая максимальное независимое множество в соответствующем ладейном графе.

Независимое множество в графе ладьи — это множество вершин, никакие две из которых не принадлежат одной строке или столбцу графа; в шахматных терминах это соответствует размещению ладей, никакие две из которых не атакуют друг друга. Совершенные графы также могут быть описаны как графы, в которых в каждом индуцированном подграфе размер наибольшего независимого множества равен числу клик в разбиении вершин графа на минимальное число клик. В графе ладьи множества строк или множества столбцов (в зависимости от того, какое из них имеет меньше множеств) образуют такое оптимальное разбиение. Размер наибольшего независимого множества в графе, таким образом, равен min( m , n ) . ^[1]

Графы ладьи являются хорошо покрытыми графами : каждое независимое множество в графе ладьи может быть расширено до максимального независимого множества, и каждое максимальное независимое множество в графе ладьи имеет тот же размер, min( m , n ) . ^[23]

Доминирование

Число доминирования графа — это минимальная мощность среди всех доминирующих множеств. На графе ладьи множество вершин является доминирующим множеством тогда и только тогда, когда их соответствующие клетки либо занимают, либо находятся на расстоянии хода ладьи от всех клеток на доске m × n . Для доски m × n число доминирования равно min( m , n ) . ^[24]

На графе ладьи k -доминирующий набор - это набор вершин, чьи соответствующие квадраты атакуют все другие квадраты (через ход ладьи) по крайней мере k раз. K -кортежный доминирующий набор на графе ладьи - это набор вершин, чьи соответствующие квадраты атакуют все другие квадраты по крайней мере k раз и сами подвергаются атаке по крайней мере k − 1 раз. Минимальная мощность среди всех k -доминирующих и k -кортежных доминирующих наборов - это k -число доминирования и k -кортежное доминирующее число, соответственно. На квадратной доске и для четных k число доминирования k равно nk /2 , когда n ≥ ( k ² − 2 k )/4 и k < 2 n . Аналогичным образом, k -кортежное доминирующее число равно n ( k + 1)/2, когда k нечетно и меньше 2 n . ^[25]

Гамильтоновость

Каждый граф ладьи содержит гамильтонов цикл . ^[26] Однако эти циклы могут включать ходы между клетками, которые находятся далеко друг от друга в пределах одной строки или столбца шахматной доски. Вместо этого изучение «туров ладьи» в математике шахмат, как правило, было сосредоточено на особом случае этих гамильтоновых циклов, где ладья ограничена в перемещении только на соседние клетки. Эти одношаговые туры ладьи существуют только на досках с четным числом клеток. Они играют центральную роль в доказательстве теоремы Гомори о том, что если удалить две клетки противоположных цветов со стандартной шахматной доски, оставшиеся клетки всегда можно покрыть домино. ^[27] Они представлены наряду с турами коня в первой работе, в которой обсуждаются туры шахматных фигур, санскритской Kavyalankara Рудраты IX века . ^[28]

Спектр

Спектр графа ладьи ( собственные значения его матрицы смежности ) состоит из четырех собственных значений , , , и . Поскольку все они являются целыми числами, графы ладьи являются целочисленными графами . Существует только три класса графов (и конечное число исключительных графов ), которые могут иметь четыре собственных значения, одно из которых равно ; один из трех классов — это класс графов ладьи. Для большинства комбинаций и граф ладьи является спектрально уникальным: никакой другой граф не имеет того же спектра. В частности, это верно, когда или , или когда два числа и в сумме дают не менее 18 и не имеют вид . ^[29] ${\displaystyle m+n-2}$ ${\displaystyle m-2}$ ${\displaystyle n-2}$ ${\displaystyle -2}$ ${\displaystyle -2}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle m\times n}$ ${\displaystyle n=2}$ ${\displaystyle n=m-1}$ ${\displaystyle m}$ ${\displaystyle n}$ ${\displaystyle 2t^{2}\pm t}$

В других графиках

Графы, для которых соседи каждой вершины индуцируют граф ладьи, были названы локально сеткой . Примерами являются графы Джонсона , для которых соседи каждой вершины образуют граф ладьи. Известны и другие примеры, а для некоторых графов ладьи известна полная классификация. Например, есть два графа, все окрестности которых являются графами ладьи: это граф Джонсона и дополнительный граф графа ладьи. ^[30] ${\displaystyle J(n,k)}$ ${\displaystyle k\times (n-k)}$ ${\displaystyle 3\times 3}$ ${\displaystyle J(6,3)}$ ${\displaystyle 4\times 4}$

Смотрите также

• График Бишопа
• Комплекс шахматной доски , комплекс независимости графа ладьи
• Граф короля
• Граф Рыцаря
• Граф решетки , граф горизонтальных и вертикальных смежностей клеток на шахматной доске.
• Граф королевы

Ссылки

1. Ласкар, Рену ; Уоллис, Чарльз (1999), «Графы шахматной доски, связанные с ними конструкции и параметры доминирования», Журнал статистического планирования и вывода , 76 (1–2): 285–294, doi :10.1016/S0378-3758(98)00132-3, MR  1673351.
2. Stones, Douglas S. (2010), «Множество формул для числа латинских прямоугольников», Electronic Journal of Combinatorics , 17 (1): Статья 1, 46, doi : 10.37236/487 , MR  2661404
3. Азизоглу, М. Джемиль; Эгечиоглу, Омер (2003), «Экстремальные множества, минимизирующие размерно-нормализованную границу в графах Хэмминга», SIAM Journal on Discrete Mathematics , 17 (2): 219–236, doi :10.1137/S0895480100375053, MR  2032290.
4. Goethals, J.-M.; Seidel, JJ (1970), «Строго регулярные графы, полученные из комбинаторных конструкций», Canadian Journal of Mathematics , 22 (3): 597–614, doi : 10.4153/CJM-1970-067-9 , MR  0282872, S2CID  199082328.
5. Герцберг, Агнес М .; Мурти, М. Рам (2007), «Квадраты судоку и хроматические многочлены» (PDF) , Notices of the American Mathematical Society , 54 (6): 708–717, MR  2327972
6. Matschke, Benjamin; Pfeifle, Julian; Pilaud, Vincent (2011), "Prodsimplicial-neighborly polytopes", Discrete & Computational Geometry , 46 (1): 100–131, arXiv : 0908.4177 , doi : 10.1007/s00454-010-9311-y, MR  2794360, S2CID  2070310
7. Мур, Дуг (1992), «Понимание симплоидов», в Kirk, David (ред.), Graphics Gems III , Academic Press , стр. 250–255, doi :10.1016/b978-0-08-050755-2.50057-9
8. Moon, JW (1963), «О линейном графике полного биграфа», Annals of Mathematical Statistics , 34 (2): 664–667, doi : 10.1214/aoms/1177704179.
9. Хоффман, А. Дж. (1964), «О линейном графике полного двудольного графа», Annals of Mathematical Statistics , 35 (2): 883–885, doi : 10.1214/aoms/1177703593 , MR  0161328.
10. Fiala, Nick C.; Haemers, Willem H. (2006), "5-хроматические сильно регулярные графы", Discrete Mathematics , 306 (23): 3083–3096, doi : 10.1016/j.disc.2004.03.023 , MR  2273138.
11. Буриченко, Вице-президент; Махнев А.А. (2011), «Об автоморфизмах сильно регулярных локально циклических графов», Доклады Академии наук , 441 (2): 151–155, MR  2953786. Переведено в Doklady Mathematics 84 (3): 778–782, 2011, doi :10.1134/S1064562411070076. С первой страницы перевода: «Граф Шрикханде — единственный сильно регулярный локально шестиугольный граф с параметрами (16, 6, 2, 2)».
12. Элкис, Ноам (осень 2004 г.), «Глоссарий теории графов», семинар первокурсников 23j: шахматы и математика , математический факультет Гарвардского университета , получено 03.05.2023.
13. Харари, Фрэнк (1958), «О числе двухцветных графов», Pacific Journal of Mathematics , 8 (4): 743–755, doi : 10.2140/pjm.1958.8.743 , MR  0103834. См., в частности, уравнение (10), стр. 748 для группы автоморфизмов графа ладьи и обсуждение выше уравнения для порядка этой группы. ${\displaystyle n\times n}$
14. Биггс, Норман (1974), «Симметрия линейных графиков», Utilitas Mathematica , 5 : 113–121, MR  0347684.
15. Это следует из определения графа ладьи как графа декартового произведения, а также из предложения 4 Броэра, Изака; Хаттинг, Йоханнеса Х. (1990), «Продукты циркулянтных графов», Quaestiones Mathematicae , 13 (2): 191–216, doi :10.1080/16073606.1990.9631612, MR  1068710.
16. Грей, Р.; Макферсон, Д. (2010), «Счетные связно-однородные графы», Журнал комбинаторной теории , Серия B, 100 (2): 97–118, doi : 10.1016/j.jctb.2009.04.002 , MR  2595694. См., в частности, теорему 1, которая определяет эти графы как линейные графы полных двудольных графов.
17. Об эквивалентности между декартовыми произведениями полных графов и линейными графами полных двудольных графов см. de Werra, D.; Hertz, A. (1999), "On perfectness of sums of graphs" (PDF) , Discrete Mathematics , 195 (1–3): 93–101, doi : 10.1016/S0012-365X(98)00168-X , MR  1663807.
18. де Верра и Герц (1999).
19. Чудновски, Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006), «Сильная теорема о совершенном графе» (PDF) , Annals of Mathematics , 164 (1): 51–229, arXiv : math/0212070 , doi :10.4007/annals.2006.164.51, JSTOR  20159988, S2CID  119151552.
20. Об эквивалентности между реберно-раскрашенными полными двудольными графами и латинскими квадратами см., например, LeSaulnier, Timothy D.; Stocker, Christopher; Wenger, Paul S.; West, Douglas B. (2010), "Rainbow matching in edge-colored graphs", Electronic Journal of Combinatorics , 17 (1): Note 26, 5, doi : 10.37236/475 , MR  2651735.
21. Стоунз, Дуглас С. (2010), «Множество формул для числа латинских прямоугольников», Электронный журнал комбинаторики , 17 (1): A1:1–A1:46, doi : 10.37236/487 , MR  2661404
22. Колборн, Чарльз Дж. (1984), «Сложность завершения частичных латинских квадратов», Дискретная прикладная математика , 8 (1): 25–30, doi : 10.1016/0166-218X(84)90075-1 , MR  0739595.
23. Для эквивалентного утверждения для хорошо покрытого свойства графов ладьи, в терминах паросочетаний в полных двудольных графах, см. Lesk, M.; Plummer, MD; Pulleyblank, WR (1984), "Equi-matchable graphs", в Bollobás, Béla (ред.), Graph Theory and Combinatorics: Proceedings of the Cambridge Combinatoric Conference, in Honour of Paul Erdős , London: Academic Press, стр. 239–254, MR  0777180.
24. Яглом, AM ; Яглом, IM (1987), "Решение задачи 34b", Challenging Mathematical Problems with Elementary Solutions, Dover, стр. 77, ISBN 9780486318578.
25. Берчетт, Пол; Лейн, Дэвид; Лачниет, Джейсон (2009), « K -доминирование и k -кортежное доминирование на графе ладьи и другие результаты», Congressus Numerantium , 199 : 187–204.
26. Херли, К. Б.; Олдфорд, Р. В. (февраль 2011 г.), «Графы как навигационная инфраструктура для многомерных пространств данных», Computational Statistics , 26 (4): 585–612, doi :10.1007/s00180-011-0228-6, S2CID  54220980
27. Уоткинс, Джон Дж. (2004), По всей доске: Математика шахматных задач , Princeton University Press, стр. 12, ISBN 9780691130620
28. Мюррей, HJR (январь 1902 г.), «Путь коня: древний и восточный», The British Chess Magazine , т. 22, № 1, стр. 1–7
29. Дуб, Майкл (1970), «О характеристике некоторых графов с четырьмя собственными значениями по их спектрам», Линейная алгебра и ее приложения , 3 (4): 461–482, doi : 10.1016/0024-3795(70)90037-6 , MR  0285432
30. Коэн, Ардже М. (1990), «Локальное распознавание графов, зданий и связанных с ними геометрий» (PDF) , в Кантор, Уильям М.; Либлер, Роберт А.; Пейн, Стэнли Э.; Шульт, Эрнест Э. (ред.), Конечные геометрии, здания и связанные с ними темы: доклады с конференции по зданиям и связанным с ними геометриям, состоявшейся в Пингри-Парке, Колорадо, 17–23 июля 1988 г. , Oxford Science Publications, Oxford University Press, стр. 85–94, MR  1072157; см. в частности стр. 89–90

Внешние ссылки

• Вайсштейн, Эрик В. , «Граф ладьи», MathWorld