2-11 정리
2-factor theorem그래프 이론의 수학 분야에서는 줄리어스 피터슨이 발견한 2-요인 정리는 그래프 이론에서 가장 초기 작품 중 하나이다.다음과 같이 진술할 수 있다.
여기서, 2-요인은 모든 정점이 2도를 갖는 G의 하위 그래프로, 즉 각 정점을 정확히 한 번 만지는 사이클의 집합이다.
증명
이렇게 일반화된 형태의 정리를 증명하기 위해 피터슨은 먼저 오일러 트레일에서 대체 에지를 취함으로써 4-정규 그래프를 두 개의 2-요소로 인자화할 수 있다는 것을 증명했다.그는 4-정규 그래프에 사용된 것과 동일한 기법이 2k-정규 그래프를 두 k-요소로 인자화한다는 점에 주목했다.[2]
이 정리를 증명하기 위해서는 연결된 그래프를 고려하는 것으로 충분하다.짝수 정도의 연결된 그래프에는 오일러 자국이 있다.이 오일리언 트레일을 통과하면 G의 방향 D가 생성되어 모든 점이 외설적이고 외향적인 = k. 다음, 모든 정점 v v V(D)를 두 개의 정점 v'와 v"로 교체하고, 방향 그래프의 모든 방향 UV를 u'에서 v"로 방향화된 가장자리로 교체한다.D는 k와 인·아웃 도수가 같기 때문에 결과적인 양분 그래프 G'는 k-일반이다.G'의 가장자리는 Kőnig의 정리에 의해 k perfect matching으로 분할할 수 있다.이제 모든 v에 대해 v'를 v"와 병합하면 그래프 G가 복구되고, G'의 k 완벽한 일치를 가장자리를 분할하는 G의 k 2-요소에 매핑한다.[1]
역사
이 정리는 덴마크의 수학자인 줄리어스 피터슨에 의해 발견되었다.사실 그래프 이론의 첫 번째 결과 중 하나이다.이 정리는 1891년 기사 "Die Theory der reguléren graphs"에서 먼저 나타난다.그 정리를 증명하기 위해 피터슨의 근본적인 생각은 시행의 가장자리나 경로의 가장자리를 빨강과 파랑으로 번갈아 '색칠'한 다음, 한 가지 또는 두 가지 색상의 가장자리를 다른 경로나 시험의 건설에 사용하는 것이었다.[3]
