Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

Магические квадраты [ править ]

Намк Кемаль Чезми.pdfПолумагическим квадрат представляет собой п × п квадрат с номерами от 1 до п 2 в его клетках, в которых сумма каждой строки и столбца одно и то же. Полумагический квадрат эквивалентен магической разметке полного двудольного графа K n, n . Два набора вершин K n, n соответствуют строкам и столбцам квадрата, соответственно, а метка на ребре r i s j является значением в строке i , столбце j полумагического квадрата.

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

Ссылки [ править ]

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