얽힘(그래프 측정)

그래프 이론에서 지시된 그래프의 얽힘은 그래프의 주기가 얼마나 강하게 얽혀 있는지를 측정하는 숫자다.그것은 그래프 가장자리를 따라 도망치는 강도를 경찰들이 붙잡으려 하는 수학적인 게임으로 정의된다.사이클 순위와 같은 다른 그래프 측정과 유사하게 패리티 게임과 같은 일부 알고리즘 문제는 경계가 걸린 그래프에서 효율적으로 해결할 수 있다.

정의

이 얽힘 게임은^[1] 경찰들이 지시된 그래프 G에서 강도를 상대로 하는 게임이다.처음에는 모든 경찰이 그래프 밖에 있고 강도는 임의로 G의 시작 꼭지점 v를 선택한다.더 나아가 선수들이 차례로 움직인다.각각의 움직임에서 경찰은 그들이 있는 곳에 머무르거나, 그들 중 한 명을 강도가 현재 점유하고 있는 정점에 배치한다.강도는그녀의 현재 정점에서,가장자리를 따라, 경찰이 점령하지 않은 후계자로 이동해야 한다.경찰이 따라오지 않으면 강도는 반드시 움직여야 한다.강도가 움직일 수 있는 자유로운 후계자가 없다면, 그녀는 잡히고, 경찰은 이긴다.강도는 잡히지 않으면 이긴다. 즉, 연극이 영원히 지속되도록 만들어질 수 있다.

G 그래프에는 G에서 n명의 경찰이 게임에서 이기면 n명의 경찰이 게임에서 지면 n - 1의 경찰은 게임에서 진다.

속성 및 응용 프로그램

얽힘 0과 1의 그래프는 다음과 같이 특징 지을 수 있다.^[1]

• G가 반복적인 경우에만 G의 얽힘이 0이다.
• G가 반복되지 않는 경우에만 G의 결합이 1이며, G의 모든 강하게 연결된 구성 요소에는 제거가 해당 구성 요소를 반복하는 노드가 있다.

얽힘은 또한 모달무 미적분의 가변적 계층 구조가 엄격하다는 것을 증명하는 데 있어 핵심적인 개념이었다.^[2]

참조

외부 링크

당신은 tPlay에서 온라인에서 얽힘 게임을 할 수 있다.