В теории графов , А граф ладьи представляет собой график , который представляет все юридические ходы ладьи шахматной части на виде шахматной доски . Каждая вершина града ладьи представляет собой квадрат на шахматной доске, а каждое ребро представляет собой допустимый ход с одной клетки на другую. Одни и те же графики могут быть определены математически как декартово произведение двух полных графов или как линейные графики из полных двудольных графов .
График ладьи | |
---|---|
Вершины | нм |
Края | нм ( n + m ) / 2 - нм |
Диаметр | 2 |
Обхват | 3 (если max ( n , m ) ≥ 3 ) |
Хроматическое число | макс ( п , м ) |
Характеристики | правильный , вершинно-транзитивный , отлично покрытый |
Таблица графиков и параметров |
Графы Ладья очень симметричны. Для квадратных шахматных досок они являются дистанционно-транзитивными графами и дистанционно-регулярными графами , в то время как для прямоугольных шахматных досок с относительно простыми измерениями они являются циркулирующими графами . Их можно охарактеризовать числом треугольников, которым принадлежит каждое ребро, и наличием 4 -цикла, соединяющего каждую несмежную пару вершин.
Графы Рука являются совершенными графами , что означает, что их индуцированные подграфы (линейные графы двудольных графов) имеют хроматическое число, равное их кликовому числу . Индуцированные подграфы ладейных графов являются одним из ключевых компонентов разложения совершенных графов, используемых для доказательства сильной теоремы о совершенных графах, характеризующей все совершенные графы. Число независимости и доминирование число графа ладьи в обеих равно меньшему из двух размеров, и это хорошо укрытые графы это означает , что каждый независимый набор может быть расширен до максимального независимого множества .
Определение
An н × м Ладейный граф представляет ходы ладьи на в н × м шахматной доске. [1] Его вершинам можно задать координаты ( x , y ) , где 1 ≤ x ≤ n и 1 ≤ y ≤ m . Две вершины ( x 1 , y 1 ) и ( x 2 , y 2 ) смежны тогда и только тогда, когда либо x 1 = x 2, либо y 1 = y 2 ; то есть, если они принадлежат к одному и тому же рангу или одной вертикали шахматной доски. [1]
Для града ладьи размером n × m общее количество вершин просто nm, а количество ребер равно nm (n + m) / 2 - nm . В графе ладьи n × n общее количество вершин равно n 2, а общее количество ребер равно n 3 - n 2 ; в этом случае граф также известен как двумерный граф Хэмминга [2] или граф латинского квадрата . [3]
График ладьи для шахматной доски размером n × m также может быть определен как декартово произведение двух полных графов K n и K m , выраженное одной формулой как K n ◻ K m . Дополнение графа из А 2 х н графа ладьи является венцом графа .
Сильная регулярность
Moon (1963) и Hoffman (1964) отмечают, что График ладьи обладает всеми следующими свойствами:
- Оно имеет вершины, каждая из которых смежна с края.
- Когда , точно края принадлежат треугольники и остальные края принадлежат треугольники. Когда, каждое ребро принадлежит треугольники.
- Каждые две несмежные вершины принадлежат единственному -вертексный цикл .
Как они показывают, кроме случая , эти свойства однозначно характеризуют график ладьи. То есть графики ладьи - единственные графы, подчиняющиеся всем этим свойствам. [4] [5]
Когда , эти условия могут быть сокращены, указав, что график ладьи - это сильно регулярный граф с параметрами. [1] И наоборот, любой сильно регулярный граф с этими параметрами должен быть ладейный график, если только . [4] [5]
Когда , существует еще один сильно регулярный граф, граф Шриханде , с теми же параметрами, что иГрафик ладьи. [6] Граф Шриханде подчиняется тем же свойствам, что и Мун и Мозер. Его можно отличить отграф ладьи в том, что окрестность каждой вершины в графе Шрикханде соединена, чтобы сформировать-цикл. Напротив, вграфа ладьи, окрестность каждой вершины образует два не связанных друг с другом треугольника. [7] Кроме того, их можно отличить по номерам на обложке группы :граф ладьи может быть покрыт четырьмя кликами (четырьмя строками или четырьмя столбцами графа), тогда как для покрытия графа Шриханде необходимо шесть клик. [6]
Симметрия
Графы Рока вершинно-транзитивны и- обычный ; это единственные регулярные графы, сформированные таким образом из ходов стандартных шахматных фигур. [8] Когда, симметрии графа ладьи образуются путем независимой перестановки строк и столбцов графа, так что группа автоморфизмов графа имеетэлементы. Когда, граф имеет дополнительные симметрии, которые меняют местами строки и столбцы, поэтому количество автоморфизмов равно . [9]
Любые две вершины в графе ладьи находятся на расстоянии один или двух друг от друга, в зависимости от того, являются ли они смежными или несмежными соответственно. Любые две несмежные вершины могут быть преобразованы в любые две другие несмежные вершины симметрией графа. Когда граф ладьи не квадратный, пары смежных вершин попадают на две орбиты группы симметрии в зависимости от того, являются ли они смежными по горизонтали или вертикали, но когда граф квадратный, любые две соседние вершины также могут отображаться друг в друга с помощью симметрия, и поэтому граф дистанционно транзитивен . [10]
Когда а также являются взаимно простыми , группа симметрииграфа ладьи содержит в качестве подгруппы циклическую группу который действует путем циклической перестановкивершины; следовательно, в данном случае график ладьи - циркулянтный граф . [11]
Графы квадратной ладьи связно-однородны , что означает, что любой изоморфизм между двумя связными индуцированными подграфами может быть расширен до автоморфизма всего графа. [12]
Совершенство
График ладья также можно рассматривать как линейный график в виде полного двудольного графа K п , м - то есть, он имеет одну вершину для каждого ребра К п , м , и две вершины графа ладьи смежны тогда и только тогда , соответствующие ребра полного двудольного графа имеют общий конец. [13] С этой точки зрения, ребро в полном двудольном графе от i- й вершины на одной стороне двудольного графа до j- й вершины на другой стороне соответствует квадрату шахматной доски с координатами ( i , j ) . [1]
Любой двудольный граф является подграфом полного двудольного графа, и, соответственно, любой линейный граф двудольного графа является индуцированным подграфом ладейного графа. [14] Линейные графы двудольных графов совершенны : в них и в любом из их индуцированных подграфов количество цветов, необходимых для любой раскраски вершин, равно количеству вершин в самом большом полном подграфе . Линейные графы двудольных графов образуют важное семейство совершенных графов: они являются одним из небольшого числа семейств, используемых Чудновским и др. (2006), чтобы охарактеризовать идеальные графы и показать, что каждый граф без нечетных отверстий и без нечетных антидырок совершенен. [15] В частности, графики ладьи сами по себе совершенны.
Поскольку граф ладьи идеален, количество цветов, необходимых для любой раскраски графа, равно размеру его самой большой клики. Клики в графе ладьи - это подмножества его строк и столбцов, причем самый большой из них имеет размер max ( m , n ) , так что это также хроматическое число графа. П -раскраска из п × п графа грача может быть интерпретирована как латинского квадрата : оно описывает способ заполнения строк и столбцов в п × п сетки с п различных значений таким образом , что такое же значение не появляется дважды в любой строке или столбце. [16] Хотя найти оптимальную раскраску града ладьи несложно, NP-полно определить, можно ли распространить частичную раскраску на раскраску всего графа (эта проблема называется расширением предварительной раскраски ). Эквивалентно, NP-полный, чтобы определить, может ли частичный латинский квадрат быть завершен до полного латинского квадрата. [17]
Независимость
а | б | c | d | е | ж | грамм | час | ||
8 | 8 | ||||||||
7 | 7 | ||||||||
6 | 6 | ||||||||
5 | 5 | ||||||||
4 | 4 | ||||||||
3 | 3 | ||||||||
2 | 2 | ||||||||
1 | 1 | ||||||||
а | б | c | d | е | ж | грамм | час |
Независимое множество в графе ладья представляет собой множество вершин, никакие два из которых не принадлежат к одной и той же строки или столбца графика; в шахматном плане это соответствует расстановке ладей, две из которых не атакуют друг друга. Совершенные графы также можно описать как графы, в которых в каждом индуцированном подграфе размер наибольшего независимого множества равен количеству клик в разбиении вершин графа на минимальное количество клик. В графе ладьи наборы строк или наборы столбцов (в зависимости от того, у кого меньше наборов) образуют такое оптимальное разделение. Таким образом, размер самого большого независимого множества в графе равен min ( m , n ) . [1] Каждый цветовой класс в любой оптимальной раскраске града ладьи является максимально независимым множеством.
Графы ладьи - это хорошо покрытые графы : каждое независимое множество в графе ладьи может быть расширено до максимального независимого множества, и каждое максимальное независимое множество в графе ладьи имеет тот же размер, min ( m , n ) . [18]
Господство
Число доминирования графа - это минимальная мощность среди всех доминирующих множеств. На графе ладьи набор вершин является доминирующим множеством тогда и только тогда, когда соответствующие им клетки либо занимают, либо являются отходом ладьи от всех полей на доске m × n . Для доски m × n число доминирования min ( m , n ) . [19]
На графе ладьи k- доминирующее множество - это набор вершин, соответствующие клетки которых атакуют все остальные поля (ходом ладьи) не менее k раз. К -кратному доминирующему множеству на графике ладьи представляет собой набор вершин, соответствующие квадраты атаковать все другие квадраты по крайней мере K раза и сами атаковали по крайней мере , к - 1 разы. Минимальная мощность среди всех k- доминирующих и k -компонентных доминирующих множеств - это k- число доминирования и k -элементное доминирующее число, соответственно. На квадратной доске и для четного k число k- доминирования равно nk / 2, когда n ≥ ( k 2 - 2 k ) / 4 и k <2 n . Аналогичным образом, число доминирования k -элемента равно n ( k + 1) / 2, когда k нечетно и меньше 2 n . [20]
Смотрите также
- 3-3 дуопризма , четырехмерный многогранник, имеющий граф ладьи как граф его вершин и ребер
- Граф короля и графа Рыцаря , две другие графы определяются из ходов шахматных фигур
- Решетчатый граф , график горизонтального и вертикального примыкания квадратов на шахматной доске
- График судоку , суперграф графика Ладьи, соединяющий квадраты головоломки Судоку, которые должны иметь неравные значения
Рекомендации
- ^ a b c d e Ласкар, Рену; Уоллис, Чарльз (1999), "CHESSBOARD графы, связанные конструкции и параметры доминация", Журнал статистического планирования и умозаключений , 76 (1-2): 285-294, DOI : 10.1016 / S0378-3758 (98) 00132-3 , Руководство по ремонту 1673351.
- ^ Азизоглу, М. Джемил; Eğecioğlu, Омер (2003), "наборы сведения к минимуму размера Экстремальных нормированных границ в виде графиков Хемминг", SIAM журнал по дискретной математике , 17 (2): 219-236, DOI : 10,1137 / S0895480100375053 , МР 2032290.
- ^ Goethals, J.-M .; Зайдель, JJ (1970), "Сильно регулярные графы , полученные из комбинаторных конструкций", Canadian Journal математики , 22 (3): 597-614, DOI : 10,4153 / CJM-1970-067-9 , MR 0282872.
- ^ а б Луны, JW (1963), "О линейном графике полного bigraph", Анналы математической статистики , 34 (2): 664-667, DOI : 10,1214 / АОМ / 1177704179.
- ^ а б Хоффман, AJ (1964), "На графике полного двудольного графа", Анналы математической статистики , 35 (2): 883-885, DOI : 10,1214 / АОМ / 1177703593 , МР 0161328.
- ^ а б Фиала, Ник С .; Haemers, Willem H. (2006), "5-хроматические сильно регулярные графы", Дискретная математика , 306 (23): 3083-3096, DOI : 10.1016 / j.disc.2004.03.023 , MR 2273138.
- ^ Буриченко В.П .; Махнев, А.А. (2011), «Об автоморфизмах сильно регулярных локально циклических графов», Докл. Академии наук , 441 (2): 151–155, MR 2953786.. Перевод в Докладах математики 84 (3): 778-782, 2011, DOI : 10.1134 / S1064562411070076 . С первой страницы перевода: «Граф Шриханде - единственный сильно регулярный локально гексагональный граф с параметрами (16, 6, 2, 2)».
- ^ Элкис, Ноам , Глоссарий теории графов.
- ^ Харари, Frank (1958), "О числе двухцветных графов" , Тихоокеанский журнал математики , 8 (4): 743-755, DOI : 10,2140 / pjm.1958.8.743 , MR 0103834. См., В частности, уравнение (10), стр. 748 для группы автоморфизмов график ладьи и приведенное выше уравнение для порядка этой группы.
- ^ Биггс, Норман (1974), "Симметрия линейных графиков", Utilitas Mathematica , 5 : 113–121, MR 0347684.
- ^ Это следует из определения графа ладьи как графа декартового произведения вместе с предложением 4 Броэр, Изак; Хаттинг, Йоханнес Х. (1990), "Продукты циркулянтных графов", Quaestiones Mathematicae , 13 (2): 191-216, DOI : 10,1080 / 16073606.1990.9631612 , МР 1068710.
- ^ Gray, R .; Макферсона, D. (2010), "Счетный подключен-однородные графы", Журнал комбинаторной теории , Series B, 100 (2): 97-118, DOI : 10.1016 / j.jctb.2009.04.002 , МР 2595694. См., В частности, теорему 1, которая идентифицирует эти графы как линейные графы полных двудольных графов.
- ^ Об эквивалентности декартовых произведений полных графов и линейных графов полных двудольных графов см. de Werra, D .; Hertz, A. (1999), "О совершенности сумм графов" (PDF) , дискретная математика , 195 (1-3): 93-101, DOI : 10.1016 / S0012-365X (98) 00168-X , MR 1663807.
- ^ де Верра и Герц (1999) .
- ^ Чудновский, Мария ; Робертсон, Нил ; Сеймур, Пол ; Томас, Робин (2006), «Сильная теорема о совершенном графе» (PDF) , Annals of Mathematics , 164 (1): 51–229, arXiv : math / 0212070 , doi : 10.4007 / annals.2006.164.51 , JSTOR 20159988.
- ^ Об эквивалентности полных двудольных графов с раскраской ребер и латинских квадратов см., Например, LeSaulnier, Timothy D .; Стокер, Кристофер; Wenger, Paul S .; Запад, Дуглас Б. (2010), "Радуга соответствия в краевых цвета графов" , Электронный журнал Комбинаторика , 17 (1): Примечание 26, 5, DOI : 10,37236 / 475 , МР 2651735.
- ^ Колборн, Чарльз Дж. (1984), «Сложность заполнения частичных латинских квадратов», Дискретная прикладная математика , 8 (1): 25–30, DOI : 10.1016 / 0166-218X (84) 90075-1 , MR 0739595.
- ^ Для эквивалентного утверждения о свойстве хорошо покрытых ладейных графов в терминах паросочетаний в полных двудольных графах см. Самнер, Дэвид П. (1979), «Случайно сопоставимые графы», Журнал теории графов , 3 (2): 183–186, DOI : 10.1002 / jgt.3190030209 , hdl : 10338.dmlcz / 102236 , MR 0530304.
- ^ Яглом AM ; Яглом, И.М. (1987), "Решение задачи 34b", " Сложные математические задачи с элементарными решениями" , Довер, с. 77, ISBN 9780486318578.
- ^ Берчетт, Пол; Лейн, Дэвид; Лахниет, Джейсон (2009), « K- доминирование и k- кратное доминирование на графике ладьи и другие результаты», Congressus Numerantium , 199 : 187–204.
Внешние ссылки
- Вайсштейн, Эрик В. "Решетчатый граф" . MathWorld .