Магический граф: различия между версиями

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Интерактивная навигация по истории
[отпатрулированная версия][непроверенная версия]
← Предыдущая правкаСледующая правка →
Содержимое удалено Содержимое добавлено
ВизуальныйВики-текст
м + {{изолированная статья}}
оформление, проверка орф.и пункт.
Строка 1: Строка 1:
'''Магический граф''' — это [[Граф (математика)|граф]], рёбра которого помечены положительными целыми числами, так что сумма всех рёбер, смежных любой вершине постоянна (то есть не зависит от выбора вершины), либо граф допускает такую разметку рёбер. Если метки – первые ''q'' целых положительных чисел, где ''q'' — число рёбер, граф и его разметка называются '''супермагическими'''.
'''Магический граф''' — это [[Граф (математика)|граф]], [[Глоссарий_теории_графов#ребро|рёбра]] которого помечены положительными целыми числами, так что сумма всех рёбер, смежных любой [[Вершина_(теория_графов)|вершине]], постоянна (то есть не зависит от выбора вершины), либо граф допускает такую разметку рёбер. Если метки — первые ''q'' целых положительных чисел, где ''q'' — число рёбер, граф и его разметка называются '''супермагическими'''.


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


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


Всестороннее обзрение магических разметок и магических графов дали Галлиан (Gallian, 1998), Валлис (Wallis, 2001) и Марр (Marr, Wallis, 2013).
Всестороннее обзрение магических разметок и магических графов дали Галлиан{{sfn|Gallian|1998}}, Валлис{{sfn|Wallis|2001}} и Марр{{sfn|Marr, Wallis|2013)}}.


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


'''Полумагический квадрат''' — это ''n'' &times; ''n'' квадрат с числами от 1 до ''n''<sup>2</sup> в клетках, в котором сумма по каждой строке и каждому столбцу одна и та же. Полумагический квадрат эквивалентен магической разметке полного двудольного графа ''K<sub>n,n</sub>''. Два множества вершин графа ''K<sub>n,n</sub>'' соответствуют строкам и столбцам квадрата, соответственно, а метки на рёбрах ''r<sub>i</sub>s<sub>j</sub>'' — это значение в строке ''i'' и столбце ''j'' полумагического квадрата. (Полумагический квадрат часто называют в математике ''магическим квадратом'', но он не имеет всех свойств [[Магический квадрат|магического квадрата]].)
'''Полумагический квадрат''' — это ''n'' &times; ''n'' квадрат с числами от 1 до ''n''<sup>2</sup> в клетках, в котором сумма по каждой строке и каждому столбцу одна и та же. Полумагический квадрат эквивалентен магической разметке полного двудольного графа ''K<sub>n,n</sub>''. Два множества вершин графа ''K<sub>n,n</sub>'' соответствуют строкам и столбцам квадрата, соответственно, а метки на рёбрах ''r<sub>i</sub>s<sub>j</sub>'' — это значение в строке ''i'' и столбце ''j'' полумагического квадрата (полумагический квадрат часто называют в математике ''магическим квадратом'', но он не имеет всех свойств [[Магический квадрат|магического квадрата]]).

== Ссылки ==

* W. D. Wallis (2001), ''Magic Graphs''. Birkhäuser Boston, Boston, Mass. ISBN 0-8176-4252-8


== Примечания ==
* Alison M. Marr and W. D. Wallis (2013), ''Magic Graphs''. Second edition. Birkhäuser/Springer, New York. ISBN 978-0-8176-8390-0; 978-0-8176-8391-7
{{примечания}}


== Литература ==
* Joseph A. Gallian (1998), A dynamic survey of graph labeling. ''Electronic Journal of Combinatorics'', vol. 5, Dynamic Survey 6. Updated several times.
* {{книга |автор= W. D. Wallis|заглавие=Magic Graphs |ответственный= |ссылка= |место= Boston, Mass.|издательство= Birkhäuser Boston |год=2001 |том= |страниц= |страницы= |isbn= ISBN 0-8176-4252-8|ref= Wallis}}
* {{книга |автор= Alison M. Marr, W. D. Wallis |заглавие= Magic Graphs. Second edition|ответственный= |ссылка= |место=New York |издательство=Birkhäuser/Springer |год=2013 |том= |страниц= |страницы= |isbn=978-0-8176-8390-0; 978-0-8176-8391-7 |ref= Alison, Wallis}}
* {{статья |автор= Joseph A. Gallian|заглавие=A dynamic survey of graph labeling |ссылка= |язык= |издание= Electronic Journal of Combinatorics|тип= |год=1998 |том= |номер=5 |страницы= |doi= |issn=|ref=Gallian}}


{{изолированная статья}}
{{изолированная статья}}
Строка 23: Строка 25:
[[Категория:Теория графов]]
[[Категория:Теория графов]]
[[Категория:Магические квадраты]]
[[Категория:Магические квадраты]]
{{rq|checktranslate|style|grammar}}
{{rq|checktranslate}}
{{math-stub}}
{{math-stub}}

Версия от 08:52, 6 июля 2015

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

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

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

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

Всестороннее обзрение магических разметок и магических графов дали Галлиан[1], Валлис[2] и Марр[3].

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

Полумагический квадрат — это n × n квадрат с числами от 1 до n2 в клетках, в котором сумма по каждой строке и каждому столбцу одна и та же. Полумагический квадрат эквивалентен магической разметке полного двудольного графа Kn,n. Два множества вершин графа Kn,n соответствуют строкам и столбцам квадрата, соответственно, а метки на рёбрах risj — это значение в строке i и столбце j полумагического квадрата (полумагический квадрат часто называют в математике магическим квадратом, но он не имеет всех свойств магического квадрата).

Примечания

  1. ↑ Gallian, 1998.
  2. ↑ Wallis, 2001.
  3. ↑ Marr, Wallis, 2013).

Литература

  • W. D. Wallis. Magic Graphs. — Boston, Mass.: Birkhäuser Boston, 2001. — ISBN ISBN 0-8176-4252-8.
  • Alison M. Marr, W. D. Wallis. Magic Graphs. Second edition. — New York: Birkhäuser/Springer, 2013. — ISBN 978-0-8176-8390-0; 978-0-8176-8391-7.
  • Joseph A. Gallian. A dynamic survey of graph labeling // Electronic Journal of Combinatorics. — 1998. — № 5.
Источник — https://ru.wikipedia.org/w/index.php?title=Магический_граф&oldid=71943084