"사각격자의 도미노 타일링 (dimer problem)"의 두 판 사이의 차이

수학노트
둘러보기로 가기 검색하러 가기
잔글 (찾아 바꾸기 – “<br><math>” 문자열을 “:<math>” 문자열로)
잔글 (찾아 바꾸기 – “수학사연표” 문자열을 “수학사 연표” 문자열로)
47번째 줄: 47번째 줄:
  
 
* http://www.google.com/search?hl=en&tbs=tl:1&q=
 
* http://www.google.com/search?hl=en&tbs=tl:1&q=
−
* [[수학사연표 (역사)|수학사연표]]
+
* [[수학사 연표]]
  
 
 
 
 

2013년 1월 14일 (월) 15:46 판

이 항목의 수학노트 원문주소

 

 

개요

  • 사각격자를 도미노로 덮는 문제
  • planar bipartite graph 의 perfect matching 문제로 생각할 수 있다
  • 그래프의 적당한 weighted adjacency matrix 와 그 파피안(Pfaffian) 을 통해 답을 표현할 수 있다
  • 통계물리에서는 dimer configuration = covering of a graph by pairs of fermions connected by an edge

 

 

2x2 격자

  • 다음 두 가지 경우가 존재
    파일:10224838-dimer1.gif
  • 다음 행렬의 파피안(Pfaffian) 을 구해서 경우의 수를 얻을 수 있다\[\left( \begin{array}{cccc} 0 & 1 & 1 & 0 \\ -1 & 0 & 0 & -1 \\ -1 & 0 & 0 & 1 \\ 0 & 1 & -1 & 0 \end{array} \right)\]

 

 

\(\left( \begin{array}{cccc} 0 & t_{1,2} & t_{1,3} & 0 \\ -t_{1,2} & 0 & 0 & -t_{2,4} \\ -t_{1,3} & 0 & 0 & t_{3,4} \\ 0 & t_{2,4} & -t_{3,4} & 0 \end{array} \right)\) 의 파피안은 \(t_{1,3} t_{2,4}+t_{1,2} t_{3,4}\) 으로 주어진다. 파피안의 각 항은 도미노 타일링에 대응된다. 

 

 

3x2 격자

  • 다음 세 가지 경우가 존재
     파일:10224838-dimer2.gif
  • 다음 행렬의 파피안은 3이다\[\left( \begin{array}{cccccc} 0 & 1 & 1 & 0 & 0 & 0 \\ -1 & 0 & 0 & -1 & 0 & 0 \\ -1 & 0 & 0 & 1 & 1 & 0 \\ 0 & 1 & -1 & 0 & 0 & -1 \\ 0 & 0 & -1 & 0 & 0 & 1 \\ 0 & 0 & 0 & 1 & -1 & 0 \end{array} \right)\]

 

\(\left( \begin{array}{cccccc} 0 & t_{1,2} & t_{1,3} & 0 & 0 & 0 \\ -t_{1,2} & 0 & 0 & -t_{2,4} & 0 & 0 \\ -t_{1,3} & 0 & 0 & t_{3,4} & t_{3,5} & 0 \\ 0 & t_{2,4} & -t_{3,4} & 0 & 0 & -t_{4,6} \\ 0 & 0 & -t_{3,5} & 0 & 0 & t_{5,6} \\ 0 & 0 & 0 & t_{4,6} & -t_{5,6} & 0 \end{array} \right)\) 의 파피안은 \(t_{1,2} t_{3,5} t_{4,6}+t_{1,3} t_{2,4} t_{5,6}+t_{1,2} t_{3,4} t_{5,6}\) 이다.

 

역사

 

 

 

메모

 

 

관련된 항목들

 

 

수학용어번역

 

 

 

사전 형태의 자료

 

 

리뷰논문, 에세이, 강의노트

   

 


 

 

원본 주소 "https://wiki.mathnt.net/index.php?title=사각격자의_도미노_타일링_(dimer_problem)&oldid=25679"