도로색소정리

Road coloring theorem

그래프 이론에서 이전에 도로 착색 추측으로 알려진 도로 착색 정리는 동기화된 지시사항을 다룬다.이 문제는 그러한 지시를 사용함으로써 네트워크 내의 다른 지점(도시 거리 또는 미로의 표현일 수 있음)에서 물체나 목적지에 도달하거나 위치를 찾을 수 있는지 여부를 포함한다.[1]현실 세계에서는 이런 현상이 마치 친구에게 전화를 걸어 자기 집으로 가는 길을 물어보는 것과 같을 것이고, 그는 어디서부터 시작했든 간에 효과가 있는 일련의 길을 알려 주었다.이 정리는 상징적 역학에도 시사하는 바가 있다.

이 정리는 로이 애들러와 벤자민 와이스(1970년)에 의해 처음 추측되었다.그것은 Avraham Trahtman(2009)에 의해 증명되었다.

예와 직감

색상이 동기화된 방향 그래프

오른쪽의 이미지는 각 꼭지점이 2도 밖에 있는 8개의 정점에 방향 그래프를 보여준다. (이 경우 각 꼭지점은 2도 안에 있지만, 동기화하는 색상이 존재하기 위해 필요한 것은 아니다.)이 그래프의 가장자리는 빨강과 파랑색으로 칠해져 있어 싱크로나이징 컬러를 만들어 냈다.

예를 들어 노란색으로 표시된 정점을 고려해 보십시오.그래프의 어느 부분에서 시작하든 "파란색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색" 보행 중 9개 가장자리를 모두 횡단하면 노란색 꼭지점에 도달하게 된다.마찬가지로 "파란색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색-빨간색" 걷기

도로 채색 정리는 지시된 그래프의 특정 범주에 대해 그러한 채색을 만드는 것이 항상 가능하다고 명시하고 있다.

수학적 설명

G는 모든 정점이 동일한 아웃도 k를 갖는 유한하고 강하게 연결된 방향 그래프가 되도록 한다.Let a는 문자 1, ..., k를 포함하는 알파벳이다. G에서 동기화하는 컬러링(접을 수 있는 컬러링이라고도 함)은 A의 문자로 G의 가장자리를 표시하는 것으로, (1) 각 꼭지점에 주어진 라벨과 함께 정확하게 하나의 발신 가장자리를 가지고 있고 (2) 그래프의 모든 꼭지 v에 대해, G co의 모든 경로에 W가 있다.v.에서 종료되는 w에 대한 응답.

색소 동기화라는 용어는 유한한 자동자 이론에서 이 개념과 동기화 단어 사이의 관계에 기인한다.

그런 색채가 조금이라도 존재하기 위해서는 G가 주기적인 것이 필요하다.[2]도로 색소 정리에는 그러한 색소가 존재하기에 주기성도 충분하다고 명시되어 있다.따라서 도로 색소 문제는 다음과 같이 간단히 말할 수 있다.

균일하게 연결된 모든 유한한 유도 주기 그래프는 동기화하는 색상을 가지고 있다.

이전 부분 결과

이전의 부분적 또는 특수 사례 결과는 다음을 포함한다.

  • G가 다중 가장자리가 없는 유한하게 연결된 주기적 방향 그래프이고 G가 G의 적절한 부분집합인 프라임 길이의 단순한 사이클을 포함하고 있다면 G는 싱크로나이징 컬러를 가진다.(O'Brien 1981)
  • G가 유한하게 연결된 주기적 방향 그래프(복수의 가장자리 허용)이고 모든 정점들이 동일한 인도 및 아웃도 k를 가지고 있다면 G는 동기화하는 색상을 가진다.(Kari 2003)

참고 항목

메모들

  1. ^ Seigel-Itzkovich, Judy (2008-02-08). "Russian immigrant solves math puzzle". The Jerusalem Post. Retrieved 2010-09-13.
  2. ^ 헤그드 & 자인(2005년).

참조