Введение

Магический граф – это граф, чьи ребра помечены первыми q положительными целыми числами, где q – число ребер, таким образом, что сумма меток ребер, инцидентных любой вершине, одинакова, независимо от выбора вершины; или это граф, допускающий такую маркировку. Название "магический" иногда используется, когда целые числа могут быть любыми положительными целыми числами; тогда граф и маркировка, использующие первые q положительных целых чисел, называются супермагическими. Граф называется вершинно-магическим, если его вершины можно пометить так, чтобы сумма меток на каждом ребре была одинаковой. Он называется тотально-магическим, если его ребра и вершины можно пометить так, чтобы метка вершины плюс сумма меток ребер, инцидентных этой вершине, была постоянной. Существует множество вариантов концепции магической маркировки графа. Терминология также весьма разнообразна. Приведенные здесь определения, пожалуй, наиболее распространены. Всесторонние источники по магическим маркировкам и магическим графам – Gallian (1998), Wallis (2001) и Marr and Wallis (2013).

Волшебные квадраты

Полумагический квадрат – это квадрат n × n, ячейки которого заполнены числами от 1 до n², таким образом, что сумма чисел в каждой строке и каждом столбце одинакова. Полумагический квадрат эквивалентен магической раскраске полного двудольного графа Kn,n. Два множества вершин Kn,n соответствуют строкам и столбцам квадрата соответственно, а метка ребра ri sj соответствует значению в строке i и столбце j полумагического квадрата. Определение полумагических квадратов отличается от определения магических квадратов отношением к диагоналям квадрата. В магических квадратах требуется, чтобы сумма чисел на диагоналях была равна сумме чисел в строках и столбцах, но для полумагических квадратов это условие не обязательно. Следовательно, любой магический квадрат является полумагическим, но не наоборот.