Магический граф

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

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

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

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

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

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

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

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