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

А магический граф это график ребра которого помечены положительными целыми числами, так что сумма по ребрам, инцидентным любой вершине, одинакова, независимо от выбора вершины; или это граф с такой разметкой. Если целые числа являются первыми q положительные целые числа, где q количество ребер, граф и разметка называются сверхмагия.

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

Существует множество вариаций концепции магической разметки графа. Существует много вариантов терминологии. Определения здесь, пожалуй, самые распространенные.

Исчерпывающие ссылки на магические надписи и магические графы есть у Gallian (1998), Wallis (2001) и Marr and Wallis (2013).

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

Диаграмма Эйлера требований некоторых типов магических квадратов 4 × 4. Ячейки одного цвета суммируются с магической константой. * В наиболее совершенных магических квадратах 4 × 4 любые 2 ячейки, которые находятся на 2 ячейки по диагонали друг от друга (включая обход), в сумме составляют половину магической константы, поэтому любые 2 такие пары также суммируются с магической константой.

А полумагический квадрат является п × п квадрат с числами от 1 до п² в его ячейках, в которых сумма каждой строки и столбца одинакова. Полумагический квадрат эквивалентен магической разметке полного двудольного графа K_{п, п}. Два набора вершин K_{п, п} соответствуют строкам и столбцам квадрата соответственно, а метка на ребре р_яs_j это значение в строке я, столбец j полумагического квадрата.

Определение полумагических квадратов отличается от определения магические квадраты в обработке диагоналей квадрата. Магические квадраты должны иметь диагонали с той же суммой, что и суммы строк и столбцов, но для полумагических квадратов этого не требуется. Таким образом, любой магический квадрат является полумагическим, но не наоборот.

использованная литература

• У. Д. Уоллис (2001), Магические графики. Биркхойзер Бостон, Бостон, Массачусетс. ISBN 0-8176-4252-8
• Элисон М. Марр и У. Д. Уоллис (2013), Магические графики. Второе издание. Биркхойзер / Спрингер, Нью-Йорк. ISBN 978-0-8176-8390-0; 978-0-8176-8391-7
• Джозеф А. Галлиан (1998), Динамический обзор разметки графов. Электронный журнал комбинаторики, т. 5, Динамический обзор 6. Обновлялся несколько раз.

Эта комбинаторика-связанная статья является заглушка. Вы можете помочь Википедии расширяя это. v т е