BEST 정리

이산 수학의 일부인 그래프 이론에서, BEST 정리는 방향(지향적) 그래프에서 오일러 회로의 수에 대한 제품 공식을 제공한다.그 이름은 그것을 발견한 사람들의 이름들의 약칭이다: de Bruijn, van Aardenne-Ehrenfest, Smith, Tutte.

정밀한 명세서

G = (V, E)를 지시된 그래프로 한다.오일러 서킷은 각 가장자리를 정확히 한 번 방문하는 방향의 폐쇄 경로다.1736년 오일러는 G가 연결되어 있고 외설물이 모든 꼭지점에서 외도와 같을 경우에만 G가 오일러 회로를 가지고 있다는 것을 보여주었다.이 경우 G를 오일리언이라고 한다.우리는 정점 v의 외설적인 부분을 dg(v)로 나타낸다.

BEST 정리는 연결된 오일러 그래프 G에서 오일러 회로의 숫자 ec(G)는 공식에 의해 주어진다고 기술하고 있다.

${\displaystyle \operatorname {ec}(G)=t_{w}(G)\prod _{v\in V}{\bigl(}\deg(v)-1{\bigr )!}$

여기서 t_w(G)는 수목의 수로서, G에서 고정 정점 w에서 뿌리를 향하는 나무다.지시된_w 그래프의 행렬 트리 정리 버전에 의해 숫자 t(G)를 결정 요인으로 계산할 수 있다.연결된 오일러 그래프 G에서 두_v 꼭지점 v와 w마다 t(G) = t_w(G)가 되는 것은 오일러 그래프의 속성이다.

적용들

BEST 정리는 지시된 그래프에서 오일러 회로의 수가 다항 시간 단위로 계산될 수 있다는 것을 보여주는데, 이는 간접되지 않은 그래프에 대해 #P-완전인 문제다.^[1]완전하고 완전한 초당적 그래프의 오일러 회로의 점증적 열거에도 사용된다.^[2][3]

역사

베스트 정리는 판 아덴-에렌페스트와 데 브루옌(1951년),^[4] §6, 정리 6에 기인한다.그들의 증거는 비굴적이며 드 브루옌 시퀀스를 일반화한다."증명에 추가된 노트"에서, 그것들은 모든 꼭지점에서 deg(v)=2가 있는 그래프의 공식을 증명하는 Smith와 Tutte(1941)의 초기 결과를 가리킨다.

메모들

참조

• Euler, L. (1736), "Solutio problematis ad geometriam situs pertinentis", Commentarii Academiae Scientiarum Petropolitanae (in Latin), 8: 128–140.
• Tutte, W. T.; Smith, C. A. B. (1941), "On unicursal paths in a network of degree 4", American Mathematical Monthly, 48: 233–237, doi:10.2307/2302716, JSTOR 2302716.
• van Aardenne-Ehrenfest, T.; de Bruijn, N. G. (1951), "Circuits and trees in oriented linear graphs", Simon Stevin, 28: 203–217.
• Tutte, W. T. (1984), Graph Theory, Reading, Mass.: Addison-Wesley.
• Stanley, Richard P. (1999), Enumerative Combinatorics, vol. 2, Cambridge University Press, ISBN 0-521-56069-1. 정리 5.6.2
• Aigner, Martin (2007), A Course in Enumeration, Graduate Texts in Mathematics, vol. 238, Springer, ISBN 3-540-39032-4.