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

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

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

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

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

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

Полумагический квадрат — это n × n квадрат с числами от 1 до n ² в клетках, в котором сумма по каждой строке и каждому столбцу одна и та же. Полумагический квадрат эквивалентен магической разметке полного двудольного графа K _n,n . Два множества вершин графа K _n,n отвечают соответственно строкам и столбцам квадрата, а метка на ребре r _i s _j — это значение в клетке полумагического квадрата, находящейся на пересечении строки 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.