매직 그래프

Magic graph

매직 그래프는 첫 번째 q 양의 정수로 가장자리가 라벨로 표시된 그래프를 의미한다. 여기서 q는 가장자리의 수로서 어떤 꼭지점과 충돌하는 가장자리 위의 합은 정점 선택과는 무관하게 동일하다. 또는 그러한 라벨이 표시된 그래프다."마법"이라는 이름은 때때로 정수가 어떤 양의 정수라는 것을 의미하기도 한다. 그러면 첫 번째 q의 양의 정수를 사용한 그래프와 라벨링은 슈퍼매직이라고 불린다.

그래프의 정점이 어떤 가장자리의 합이 같도록 라벨을 붙일 수 있다면 그래프는 정점 마법이다.그것의 가장자리와 꼭지점에 라벨을 붙여 그 꼭지점과 충돌하는 가장자리의 라벨 합을 상수로 할 수 있다면 그것은 완전한 마법이다.

그래프의 마법 라벨 표시 개념에는 매우 많은 변화가 있다.용어에도 많은 차이가 있다.여기서의 정의는 아마도 가장 흔한 것일 것이다.

마술 연구와 마법 그래프에 대한 포괄적인 참조는 갈리아어(1998), 월리스(2001), 마러와 월리스(2013)이다.

매직 스퀘어

4 × 4 마법 사각형 일부 유형의 요구 사항에 대한 오일러 다이어그램.같은 색상의 세포가 마법 상수에 합하다.* 4 × 4 가장 완벽한 마법의 사각형에서, 2개의 세포가 대각선으로 떨어져 있는 2개의 세포는 마법 상수의 절반으로 합하므로, 그러한 2개의 쌍은 마법 상수도 합한다.

반모음 사각형은 셀에 1부터 n까지의2 숫자가 있는 n × n 제곱으로, 각 행과 열의 합이 같다.반매직 사각형은 완전한 양분 그래프 K의n,n 마법 레이블에 해당한다.K의n,n 두 꼭지점 집합은 각각 정사각형의 행과 열에 대응하며, 가장자리 ri s의j 라벨은 반모음 사각형의 i행 j의 값이다.

반마법 정사각형의 정의는 정사각형의 대각선 처리에 있어서 마법 정사각형의 정의와 다르다.매직 스퀘어는 행과 컬럼의 합과 같은 합을 가진 대각선을 가져야 하지만, 반매직 스퀘어의 경우 이것은 필요하지 않다.그러므로 모든 마법의 광장은 반모술적이지만 그 반대는 아니다.

참조

  • 노라 하츠필드와 게르하르트 링겔(1994, 2003), 진주 인 그래프 이론, 개정판.뉴욕 주 마이놀라, 6.1절 도버 출판물
  • W. D. Wallis(2001), Magic Graphs.버커호이저 보스턴, 미사 미사 ISBN0-8176-4252-8
  • Alison M. Marr과 W. D. Wallis(2013), Magic Graphs.제2판.비르카유저/뉴욕 스프링거ISBN 978-0-8176-8390-0; 978-0-8176-8391-7
  • Joseph A. Gallian (1998년), 그래프 라벨링에 대한 동적 조사.Electronic Journal of Combinatorics, vol. 5, 동적 설문 조사 6.여러 번 업데이트됨.


Stub icon

이 콤비네이터 관련 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.