Магический граф (Bgincyvtnw ijgs)

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

Маги́ческий граф — это граф, допускающий такую разметку его рёбер положительными целыми числами, что сумма меток всех рёбер, инцидентных любой вершине, постоянна (то есть не зависит от выбора вершины). Если метки — первые q целых положительных чисел, где q — число рёбер, то граф и его разметка называются супермагическими.

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

Тотально-магический — это граф, рёбра и вершины которого можно пометить целыми числами так, что сумма метки вершины и меток всех смежных вершине дуг будет постоянной величиной.

Имеется большое количество вариантов концепции разметки графа. Имеется также много вариантов в терминологии. Приведённые здесь определения, по-видимому, являются наиболее принятыми.

Всестороннее обозрение магических разметок и магических графов дали Дж. Галлиан[1], У. Валлис[2] и А. Марр[3].

Магические квадраты

[править | править код]
Диаграмма разных типов магических квадратов

Полумагический квадрат — это n × n квадрат с числами от 1 до n2 в клетках, в котором сумма по каждой строке и каждому столбцу одна и та же. Полумагический квадрат эквивалентен магической разметке полного двудольного графа Kn,n. Два множества вершин графа Kn,n отвечают соответственно строкам и столбцам квадрата, а метка на ребре risj — это значение в клетке полумагического квадрата, находящейся на пересечении строки i и столбца j (полумагический квадрат нередко называют в математике магическим квадратом, но он не имеет всех свойств магического квадрата).

Примечания

[править | править код]

Литература

[править | править код]
  • Gallian, Joseph A. . A dynamic survey of graph labeling // Electronic Journal of Combinatorics, 1998, 5 (Dynamic Survey 6).
  • Wallis W. D. . Magic Graphs. — Boston, Mass.: Birkhäuser Boston, 2001. — ISBN 0-8176-4252-8.
  • Marr A. M., Wallis W. D. . Magic Graphs. Second edition. — New York: Birkhäuser/Springer, 2013. — ISBN 978-0-8176-8390-0; 978-0-8176-8391-7.