색칠하기 책 길. 컬러링 페이지 교통 규칙 안정적인 우정과 유도

웹사이트 업데이트
10.12.2006 15:46
자동차와 만화 팬을 위해 - 만화 자동차의 색칠 페이지.

디즈니와 픽사 덕분에 2006년 6월 전 세계는 자동차만이 영웅이 되는 만화를 보게 되었습니다.

만화 Cars에 나오는 자동차는 평범한 삶을 살고 있습니다. 한 명은 타이어 가게를 운영하고, 다른 한 명은 튜닝 스튜디오를 운영하며, 히피 필모어(Volkswagen T1)나 그의 친구이자 제2차 세계대전 참전 용사처럼 일부는 단순히 자신의 즐거움을 위해 살아갑니다. (윌리스). 영화의 주인공인 '번개'라는 별명을 가진 맥퀸은 경주와 승리, 영광만을 꿈꾼다. 유명한 American Highway 66의 Radiator District에 도착하면 여전히 "녹색"인 McQueen은 즉시 자신이 얼마나 빠르고 멋진지 모든 사람에게 알려줍니다. 그러나 NASCAR 경주에 처음으로 출전하면서 그의 환상은 사라졌습니다. 낡은 견인 트럭 메이터(GMC 픽업), 멘토 닥 허드슨(허드슨 호넷), 진짜 페라리를 보는 꿈을 꾸는 꼬마 루이지(피아트 600) 등 친구들은 영웅이 손실에서 살아남도록 도와줍니다.

글쎄요, 로맨틱한 아름다움인 샐리(매력적인 911 문신을 한 포르쉐)가 없었다면 우리는 어디에 있었을까요! 그들 덕분에 McQueen은 Chico의 주요 라이벌(Plymouth Hemi Cuda)을 물리치고 여전히 경주에서 승리할 것입니다. Luigi의 꿈도 이루어질 것입니다. 언젠가는 "Red Baron"인 Michael Schumacher가 직접 목소리를 낸 "Maranello의 종마"가 타이어를 교체하기 위해 그의 가게에 올 것입니다.

영화의 제작자와 성우가 모두 자동차에 관련된 사람들이라는 점은 주목할 만합니다. 예를 들어, Joe Lasseter 감독은 그의 아버지가 수석 디자이너 중 한 명이었던 Chevrolet 공장에서 거의 어린 시절을 보냈습니다. 포드를 대표하는 디자이너 제이 메이스가 컨설턴트로 활동했다. 이미 언급된 7차례 Formula 1 세계 챔피언 Michael Schumacher 외에도 NASCAR 스타 Richard Petty와 Paul Newman, 그리고 전설적인 레이서 Michael Andretti가 캐릭터 목소리 연기에 참여했습니다.

자동차의 원래 소음만 사용되었습니다. 예를 들어 특히 경주 에피소드의 경우 NASCAR 대회 중 미국 타원형에서 몇 주 동안 소리가 녹음되었습니다. 영화를 만드는 데 2년 이상이 걸렸고, 예산은 7천만 달러였습니다. 이 기간 동안 43,000개의 다양한 자동차 스케치가 만들어졌으며 각 그림을 그리는 데 17시간 이상이 걸렸습니다. 영화에는 새로운 포르쉐와 페라리부터 골동품 포드 T까지 총 120명의 자동차 캐릭터가 등장합니다.

규칙에 대한 어린이의 지식 교통- 거리에서의 안전을 위한 주요 조건 중 하나입니다. 성인을 포함한 많은 보행자들이 이러한 규칙을 다소 가볍게 받아들이고 있으며, 이는 종종 다양한 심각도의 교통사고의 원인이 됩니다. 어린이는 인구 밀집 지역의 거리에 있을 때 도로 교통에 전적으로 참여하므로 교통 규칙을 준수하는 것은 어린이의 책임이라는 점을 분명히 이해해야 합니다.

색칠 공부 페이지 어린이를 위한 교통 규칙입니다.

거리(도로, 보도, 도시 교통)에서의 행동 규칙을 아이에게 가르치는 것은 아주 어릴 때부터 시작해야 합니다. 초기, 그가 스스로 걷고 달리는 법을 배우기 전에. 그리고 여기에서 아이가 길거리에 있는 부모와 다른 어른들의 예가 매우 중요합니다. 자녀에게 도로 규칙을 알려주고 설명할 뿐만 아니라 스스로 엄격하게 준수해야 합니다. 이 페이지에 제시된 교통 규칙 색칠하기 페이지는 주로 미취학 아동을 대상으로 하며 어린이가 도로 근처뿐만 아니라 도로 근처에서의 기본 행동 포인트를 배우는 데 도움이 됩니다.

1. 색칠 공부 페이지 신호등.

안전하게 길을 건너기 가장 좋은 곳은 신호등이 설치된 횡단보도입니다. 신호등 이미지가 포함된 색칠 페이지에는 아이들이 신호등 사용 규칙을 더 쉽게 기억할 수 있도록 도와주는 작은 운율도 포함되어 있습니다.

• 항상 신호등이 녹색일 때만 운전을 시작하십시오.
• 신호등이 빨간색이나 노란색일 때는 근처에 차량이 없더라도 절대 길을 건너지 마세요.
• 녹색 신호등으로 방향을 바꿀 때 추가로 안전을 확인하세요. 왼쪽을 본 다음 오른쪽을 살펴보세요.

2. 컬러링 페이지 횡단보도.

자녀에게 횡단보도에서만 길을 건너도록 가르치십시오. 횡단보도 색칠하기 페이지는 아이들에게 길을 올바르게 건너는 방법을 가르쳐줍니다. 신호등이 설치되어 있지 않은 건널목을 규제되지 않은 건널목이라고 합니다.

• 횡단보도는 노면에 얼룩말 횡단보도로 표시되어 있습니다.
• 길을 건너기 전에 주의 깊게 살펴보고 근처에 차량이 없는지 확인하십시오.
• 길을 건너세요. 건너지 마세요.
• 길을 대각선으로 건너지 마세요.
• 시야를 가리는 정지 차량에 특히 주의하십시오.
• 횡단보도를 통과할 때는 통화를 중단하세요.
• 특히 근처에 지하도나 고가도로가 있으면 교통이 혼잡하므로 꼭 이용하세요.

3. 보도.

보도는 보행자 통행을 위한 것입니다. 어린이들에게 보도, 특히 교통량이 많은 지역에서 올바르게 행동하도록 가르치십시오.

• 도로를 따라 보도를 운전할 때는 보도에 너무 가까이 다가가지 마십시오.
• 안뜰과 골목을 떠나는 차량을 주의 깊게 모니터링하십시오.
• 보도에서 공놀이를 하거나 뛰지 마십시오.

4. 도시 대중교통 및 버스 정류장에서 어린이를 위한 행동 규칙이 포함된 색칠 공부 페이지.

이 색칠하기 페이지는 어린이들에게 대중교통을 안전하게 이용하는 방법을 가르쳐줍니다.

• 대중교통 정류장은 도로의 시야가 좋지 않을 수 있고 많은 사람들이 실수로 어린이를 보도에서 도로로 밀어낼 수 있기 때문에 위험한 장소입니다. 여기서는 특히 조심해야 합니다.
• 차량이 완전히 정지한 후에만 차량 문에 접근하십시오.
• 차량에서 내린 후, 해당 정류장을 벗어난 후에만 길을 건너십시오.

이러한 기본적인 교통 규칙 외에도 아이들은 도로 ​​표지판을 색칠하는 데 관심을 가질 것입니다. 제시된 교통 규칙 색칠 공부 페이지는 유아, 미취학 아동 및 초등학생뿐만 아니라 유치원 및 초등학교 수업에도 사용하기에 적합합니다. 교통 규칙이 포함된 모든 사진은 완전 무료입니다. 다운로드하고 인쇄할 수 있습니다.

당신은 도로 색칠 페이지 카테고리에 있습니다. 귀하가 고려하고 있는 색칠 공부 책은 방문자가 다음과 같이 설명합니다. "" 여기에서 온라인으로 많은 색칠 공부 페이지를 찾을 수 있습니다. 도로 색칠 페이지를 다운로드하여 무료로 인쇄할 수 있습니다. 아시다시피 창의적인 활동은 어린이 발달에 큰 역할을 합니다. 그들은 정신 활동을 활성화하고 미적 취향을 형성하며 예술에 대한 사랑을 심어줍니다. 길을 주제로 그림을 색칠하는 과정이 전개됩니다 훌륭한 운동 능력, 인내와 정확성은 우리 주변 세계에 대해 더 많이 배우는 데 도움이 되며 다양한 색상과 음영을 소개합니다. 매일 저희 웹사이트에 남자아이와 여자아이를 위한 새로운 무료 색칠 공부 페이지가 추가됩니다. 이 페이지는 온라인으로 색칠하거나 다운로드 및 인쇄할 수 있습니다. 카테고리별로 정리된 편리한 카탈로그를 통해 원하는 그림을 더 쉽게 찾을 수 있으며, 다양한 컬러링북을 통해 매일 새로운 흥미로운 컬러링 주제를 찾을 수 있습니다.

샌드박스에서 자동차를 가지고 놀도록 초대하면 소년들을 오랫동안 바쁘게 만들 수 있습니다. 하지만 밖이 춥고 아이가 지루해하면 어떻게 해야 할까요? 이 경우 다음과 같은 자동차용 도로 템플릿을 다운로드하여 인쇄할 수 있습니다. 모든 고리, 회전 및 직선 도로를 잘라내는 것부터 재미가 시작됩니다. 이러한 템플릿을 사용하여 어린이는 어떤 모양의 도로도 만들 수 있습니다. 필요한 A4 용지 수가 필요한지 확인하기만 하면 됩니다.

자동차용 직선 도로 다운로드

이 시트가 가장 많이 필요할 것입니다. A4 용지에 인쇄하고 잘라야 하는 도로 3개를 배치했습니다. 아이에게 필요한 길이에 맞게 구간을 만들기 위해 도로를 직각으로 자르는 방법을 보여주세요.

자동차 도로: 링

도로를 연결하려면 위에 제시된 템플릿이 있는 링이 필요하며 거기에서 인프라 구축을 시작합니다.

자동차 도로: 직진

제시된 회전을 통해 소년은 필요한 방향으로 도로를 90도 회전할 수 있습니다.

자동차 도로에서 급커브가 아닌

다음 A4 템플릿은 모든 반경에서 도로를 회전하는 데 도움이 됩니다.

(이 항목은 수학과 동조자에 대한 지식이 있는 독자에게 흥미로울 수 있습니다)

얼마 전 나는 그래프 이론의 흥미로운 문제인 도로 색칠 추측에 대해 읽었습니다. 이 추측은 37년 동안 공개됐지만 3년 전 이스라엘 수학자 아브라함 트라흐트만에 의해 증명됐다. 그 증명은 아주 초보적인 것으로 밝혀졌고, 약간의 어려움을 겪으면서도(내 뇌가 위축되었기 때문에) 나는 그것을 읽고 이해할 수 있었고, 이 포스트에서 그것을 설명하려고 노력할 것입니다.

문제는 다음 예를 통해 설명할 수 있습니다. 각 교차로에서 북쪽, 남쪽, 동쪽, 서쪽의 네 방향 중 하나로 이동할 수 있는 도시 지도를 상상해 보세요. 자동차가 어떤 교차로에서 출발하여 "북쪽, 북쪽, 동쪽" 등의 지침 목록을 따르는 경우 - 그러면 그녀는 결국 다른 교차로에 도착하게 될 것입니다. 기계가 어디에서 시작하든 동일한 위치로 연결되는 긴 방향 목록을 찾는 것이 가능합니까? 지도가 맨해튼(일반 그리드)처럼 보인다면 그렇지 않습니다. 하지만 막다른 골목이 많고 예상치 못한 방향으로 가는 경우가 많을까요?

아니면 또 다른 예입니다. 당신의 친구는 중심을 찾아야 하는 미로에 갇혀서 당신에게 전화를 걸어 도움을 요청했습니다. 당신은 미로가 어떻게 작동하는지 알지만 친구가 어디에 있는지 모릅니다. 친구가 어디에 있든 반드시 중심으로 데려갈 수 있는 일련의 명령이 있을 수 있을까요?

이 두 가지 예에서는 각 지점의 "방향"이 고정되어 있으며 솔루션이 존재하거나 존재하지 않습니다. 그러나 보다 일반적으로 이 문제는 묻습니다. 예를 들어 "서쪽, 북쪽, 동쪽, 남쪽"이 각 교차로에서 다르게 가리키는 위치를 선택할 수 있다면 "동기화 단어"(동기화 단어)의 존재를 보장할 수 있습니까? 어떤 곳이 고정으로 이어질까요?

일반적인 경우, 정점 사이에 "화살표" 모서리가 있는 유향 그래프 G가 있다고 가정합니다. 이 그래프가 균일한 외차 d를 가지도록 하세요. 이는 각 꼭지점이 정확히 d개의 모서리를 가짐을 의미합니다. 이 경우 각 개별 정점을 입력할 수 있습니다. 다른 수량, 선택사항 d. "색상"이라고 부르는 알파벳 d 글자 세트가 있다고 가정해 보겠습니다. 그런 다음 그래프의 "채색"은 각 꼭지점에 d개의 나가는 가장자리에 대한 모든 d개의 문자를 할당하여 제공됩니다. 따라서 우리가 어떤 정점에 "있고" 색상 α에 따라 어딘가로 "가려고" 한다면 색상 지정은 항상 어느 가장자리에서 어느 새로운 정점으로 가야 하는지 알려줄 것입니다. "단어"는 일련의 문자-색상입니다. 그런 다음 그래프에 색상이 지정되고 x가 정점이고 w가 단어인 경우 xw는 x에서 시작하여 단어 w 다음에 도착할 정점을 나타냅니다.

컬러링북이라고 하는데 동기화 중, 임의의 정점 x를 하나의 고정된 정점 x 0으로 이끄는 단어 w가 있는 경우. 이 경우 w가 호출됩니다. 단어를 동기화하는 중. 도로 색상 문제에서 묻는 질문은 다음과 같습니다. 항상 동기화 색상이 있습니까? 모든 정점이 하나로 줄어들 수 있도록 그래프 가장자리에 색상을 지정하는 것이 항상 가능합니까?

이 문제는 여러 다른 영역에 적용됩니다. 예를 들어 Wikipedia에서 읽을 수 있습니다. 컴퓨터 과학이나 오토마타 이론을 가정해 보겠습니다. 색칠 그래프는 정점이 상태이고 가장자리가 정점 사이를 이동하는 방법을 나타내는 결정론적 유한 자동 장치로 생각할 수 있습니다. 우리가 이 기계를 멀리서 제어하고 일부 정보 채널을 통해 명령을 보내고 일부 고장으로 인해 이 채널이 오염되고 기계가 잘못된 명령을 받았고 이제 어떤 상태인지조차 알 수 없다고 가정해 보겠습니다. 그런 다음 동기화 워드가 있으면 현재 위치에 관계없이 알려진 상태로 가져올 수 있습니다.

그렇다면 동기화 색상은 언제 존재합니까? 도로 색칠 추측은 그래프에 두 가지 제한 사항을 더 부과합니다(각 꼭짓점에 정확히 d 개의 모서리가 있다는 사실 외에도). 첫째, 그래프는 강력하게 연결되어 있어야 합니다. 이는 모든 정점에서 다른 정점으로의 경로가 있음을 의미합니다. 둘째, 그래프는 주기적이어서는 안 됩니다. 그래프의 모든 꼭짓점을 V 1, V 2, ... V n 집합으로 나누어 그래프의 모든 가장자리가 Vi와 Vi+1 또는 V n과 V 0의 꼭짓점을 연결한다고 상상해 봅시다. 각 V의 정점 사이에는 가장자리가 없으며 순서대로만 V 사이를 "점프"할 수 없습니다. 이러한 그래프를 주기적이라고 합니다. 그러한 그래프는 동기화된 색상을 가질 수 없다는 것이 분명합니다. 색상을 어떻게 지정하든, 어떤 단어를 사용하든 서로 다른 V i의 두 꼭지점은 결코 합쳐지지 않을 것이며 계속해서 순환할 것이기 때문입니다.

도로 착색 정리에 따르면 다음 조건이 충분합니다. 각 꼭짓점의 d 모서리가 있는 비주기적이고 강하게 연결된 유향 그래프에는 동기화 색상이 있습니다.. 1970년에 처음으로 가설로 공식화되었고 이후 특수한 경우를 입증하는 부분적인 결과가 많이 나왔으나 2007년이 되어서야 완전한 증거가 나타났다. 다음은 거의 전체 증명을 다시 설명한 것입니다(하나의 기술적 보조정리 제외).

주기성

우선, 비주기성 조건을 다른 등가 조건으로 대체해 보겠습니다. 그래프의 주기 길이를 나누는 숫자 N>1이 있는 경우에만 그래프가 주기적입니다. 저것들. 우리의 비주기성 요구 사항은 그러한 N이 없다는 사실과 동일합니다. 즉, 그래프에 있는 모든 주기 길이의 최대 공약수는 1입니다. 우리는 이 조건을 만족하는 모든 그래프가 다음을 갖는다는 것을 증명할 것입니다. 색상 동기화.

주기성이 "모든 사이클의 길이를 나누는 N>1이 있다"는 조건과 동일하다는 것을 증명하는 것은 한 방향에서는 사소하고 다른 방향에서는 쉽습니다. 이것을 믿음으로 받아들이고 싶다면 이 단락의 나머지 부분을 쉽게 건너뛸 수 있습니다. 나머지 증명에서는 문제가 되지 않습니다. 그래프가 주기적이라면, 즉 정점을 세트 V 1, V 2, ... V n으로 나눌 수 있으므로 가장자리가 사이클을 따라 정점 사이에 놓이게 됩니다. 그러면 모든 사이클의 길이가 n으로 나누어져야 한다는 것이 분명합니다. 새로운 조건이 만족됩니다. 이것은 사소한 방향이지만 교체를 위해서는 두 번째 방향만 필요합니다. 모든 사이클의 길이를 나누는 N>1이 있다고 가정합니다. 정점 r의 루트를 사용하여 그래프에 방향성 스패닝 트리를 구축해 보겠습니다. 임의의 정점 x로 가는 길이 l(x)의 루트에서 시작하는 이 트리의 경로가 있습니다. 이제 우리는 그래프의 모든 간선 p-->q에 대해 l(q) = l(p) + 1(mod N)이 유지된다고 주장합니다. 이 진술이 참이라면, 모든 정점을 l(x) mod N에 따라 세트 Vi로 분할할 수 있으며 그래프는 주기적이 될 것입니다. 이 말이 사실인 이유는 무엇입니까? p-->q가 스패닝 트리의 일부라면 이는 간단합니다. 왜냐하면 단순히 l(q) = l(p) + 1이기 때문입니다. 그렇지 않은 경우 루트 r에서 다음으로 경로를 작성합니다. 정점 p,q를 R p 및 Rq로 지정합니다. 또한 R r 은 그래프에서 q에서 r로 돌아가는 경로를 나타냅니다(그래프는 연결되어 있으므로 존재합니다). 그런 다음 R p p-->q R r 및 R q R r이라는 두 개의 사이클을 작성할 수 있습니다. 조건에 따라, 이들 사이클의 길이를 N으로 나누어 총 값을 빼고 줄이면 l(p)+1 = l(q) mod N이 얻어지며, 이것이 증명되어야 합니다.

안정적인 친목과 유도

그래프 G에 특정 색상을 지정해 보겠습니다. 두 가지를 호출해 보겠습니다. 정점 p,q어떤 단어 w가 그들을 같은 꼭지점으로 가져오면 친구: pw = qw. 전화하자 p,q 적, 그들이 "결코 모이지 않는다면". 어떤 단어 w를 실행한 후에도 친구로 남아 있으면 p,q 안정 친구를 호출합시다. pw는 qw와 동일한 정점에 오지 않을 수 있지만 w"가 더 지나면 친구가 될 수 있습니다. 안정 친구는 결코 적이 될 수 없습니다.

꼭지점 사이의 안정성 관계는 첫째로 등가(반사적, 대칭적, 추이적)이고 두 번째로 그래프의 구조에 의해 보존됩니다. p, q가 안정 친구인 경우 p는 간선을 통해 p에 연결되고 q는 q에 연결됩니다. ", 그리고 이 가장자리는 같은 색입니다. 그러면 p"와 q"도 안정적인 친구입니다. 안정적인 우정을 뜻합니다. 적합성다음과 같이 나눌 수 있습니다: 새 그래프 G"를 생성합니다. 그 정점은 G의 안정적인 우정에 대한 등가 클래스가 됩니다. G에 안정적인 쌍이 하나 이상 있는 경우 G"는 G보다 작습니다. 또한, 원본 그래프 G에서 각 꼭지점의 모서리는 d개였습니다. 그러면 G"에서는 이러한 경우가 됩니다. 예를 들어 P가 새 그래프의 꼭지점인 경우 이는 원래 꼭지점 p1, p2...의 등가 클래스입니다. , α는 임의의 색상이면 모서리 p1--α--> q1, p2---α-->q2 등은 모두 서로 안정적인 우정을 유지하는 정점 q1, q2...로 이어집니다. , 따라서 하나의 새로운 정점 Q에 놓이게 되어 모든 모서리가 새로운 모서리 P --α-->Q가 됩니다. 그리고 각 d 색상에 대해서도 마찬가지입니다.

더욱이 G가 비주기적이라면 G"도 그렇습니다. 결국 - 주기성에 대한 대체 정의를 사용하면 G의 모든 순환은 G"의 순환으로 바뀌므로 G"의 모든 순환 길이는 다음과 같습니다. n > 1로 나누어지면 G의 모든 주기에 대해서도 마찬가지입니다. 따라서 G"의 주기성은 G의 주기성을 의미합니다.

G에서 동기화되는 색상을 찾았다고 가정합니다. 이제 우리가 시작한 색상 대신 G에서 사용할 수 있습니다. 모든 모서리 p-->q는 수신됩니다. 새로운 색상새로운 가장자리 색상에 따라 P-->Q. 좀 더 정확하게 말하면 다음과 같이 말해야 합니다. 그래프 G"의 각 꼭지점 P에서 모든 색상의 일부 순열에 의해 새로운 색상이 지정됩니다. π P: 색상 α로 색상이 지정된 가장자리는 새로운 색상 π P(α)를 받습니다. 그런 다음 안정성 등급 P의 각 꼭지점 p에 있는 원본 그래프 G에서 동일한 순열 π P를 사용하여 가장자리를 다시 칠합니다. 일반적으로 그래프 G의 새로운 색상은 "우정"의 몇 가지 새로운 개념을 정의합니다. 적대감"과 "안정성"은 원래 것과 동일하지 않습니다. 그러나 그럼에도 불구하고 두 꼭지점 p, q가 이전 색상에서 안정적인 친구였다면(같은 클래스 P에 속했음) 새 색상에서도 안정적인 친구로 남게 됩니다. 이는 p, q를 하나의 정점으로 가져오는 시퀀스 w가 도로를 따라 각 정점 p에서 순열 π P를 사용하여 이전 색상에서 새 색상으로 또는 그 반대로 "변환"될 수 있기 때문입니다. p, q는 안정적이므로 이전 채색에서는 "항상" 유지되므로 p, q에서 공통 정점까지의 도로를 따라 있는 각 중간 정점 p n , q n 쌍은 안정적입니다. 즉, 하나의 정점 P n 내부에 있으므로 동일한 순열을 받습니다. π피엔 .

새로운 색상은 G"에 대해 동기화됩니다. 즉, 일부 시퀀스 w는 모든 정점을 하나의 정점 P로 가져옵니다. 이제 w를 G의 새 색상에 적용하면 모든 정점이 "P 내부" 어딘가에 수렴됩니다. 위에서 설명한 대로, 클래스 P 내의 모든 정점은 새로운 색상화에서 안정적으로 유지됩니다. 이는 이제 모든 것이 하나의 정점 G로 수렴될 때까지 여전히 분리된 나머지 정점 쌍을 계속해서 모아서 w를 계속할 수 있음을 의미합니다. 따라서 새로운 색상화는 다음과 같이 동기화됩니다. G.

이 모든 것에서 정리를 증명하려면 조건을 충족하는 그래프에 한 쌍의 안정적인 친구가 있는 색상이 있다는 것을 증명하는 것으로 충분합니다. 그러면 그래프 G에서 그래프 G로 갈 수 있기 때문입니다." 크기가 더 작음, 또한 모든 조건을 충족합니다. 귀납적 논증을 사용하면 더 작은 그래프의 경우 문제가 이미 해결되었으며 G"에 대한 동기화 색상도 G에 대해 동기화될 것이라고 가정할 수 있습니다.

파벌과 최대 집합

그래프에 있는 정점의 하위 집합 A와 단어 w에 대해 Aw는 A의 모든 정점에서 시작하여 단어 w 다음에 도달하게 될 정점 집합을 나타냅니다. 일반적으로 그래프의 모든 정점에서 시작하면 이를 Gw로 표시합니다. 이 표기법에서 동기화 색상은 Gw가 하나의 요소 집합인 w가 있음을 의미합니다.

정점 집합 A가 일부 w에 대해 Gw 형식을 갖고 A의 두 정점이 적이라면, 즉 결코 수렴하지 않을 것입니다. A를 호출합시다 도당. 클릭이 존재하는 이유는 우리가 항상 전체 G로 시작하여 한 쌍의 친구 정점을 취하고 이를 연결하는 w를 탐색하고 정점 수를 하나씩 줄일 수 있기 때문입니다. 적만 남거나 정점이 하나만 남을 때까지 이 방법을 계속합니다. 이 경우에도 파벌은 간단합니다.

A가 파벌이라면 어떤 단어 w Aw도 파벌입니다. 적들은 여전히 ​​적으로 남아 있기 때문에 이것은 분명합니다. x가 그래프의 정점이면 x를 포함하는 파벌이 있습니다. 이는 일종의 파벌 A가 있다는 사실에서 비롯됩니다(이전 단락 참조). p가 정점이면 p에서 x로 이어지는 단어 w가 있습니다. 연결된 그래프; 그러면 Aw는 x를 포함하는 파벌입니다.

클릭은 안정된 친구들과의 색칠이 있음을 증명하는 데 도움이 될 것입니다. 이전 섹션에 따르면 이것은 정리를 증명하기에 충분합니다. 이 섹션 전체에서 우리는 두 개의 클릭 A와 B가 있고 그 안에 있는 모든 정점이 A와 B의 하나를 제외하고 공통이라면 이 두 정점은 안정적인 친구라는 것을 증명할 것입니다. 따라서 문제는 파벌 A와 B를 포함하는 색상을 찾는 것으로 줄어듭니다.

클릭이 어떻게 작동하는지 더 잘 이해하려면 그래프의 정점에 가중치를 할당하는 것이 유용합니다. 각 정점 x에 양의 가중치 w(x)를 할당하는 방법이 있음을 보여드리겠습니다. x에 모서리가 있는 모든 꼭지점의 가중치를 합산합니다., 그러면 d*w(x)를 얻습니다. 여기서 d는 각 꼭지점의 모서리 수입니다. 이는 선형 대수학에서 나온 것이며 고유값이 무엇인지 모른다면 이 단락의 나머지 부분을 건너뛰고 그러한 w(x)의 존재를 당연하게 여기십시오. M이 그래프 G의 행렬인 경우(셀 (i,j)에 모서리 i->j가 있으면 1이 있고 그러한 모서리가 없으면 0이 있습니다), 앞서 설명한 대로 w(x)가 됩니다. 그것들은 고유벡터의 요소입니다. 왼쪽이 행렬은 고유값 d를 갖습니다. d가 고유값이기 때문에 그러한 벡터가 존재한다는 것을 알 수 있습니다. d는 사소한 고유벡터를 갖습니다. 오른쪽에(1,1,...1) - 이는 정확히 d개의 모서리가 각 꼭지점에서 나온다는 사실에서 즉시 나타납니다.

A가 정점 집합인 경우 w(A)는 A의 모든 정점 가중치의 합을 나타냅니다. w(G)는 그래프에 있는 모든 정점의 가중치의 합입니다. 또한 s가 임의의 단어인 경우 As -1은 s를 따라 "반대 방향"으로 이동하는 경우 A에서 오는 정점 집합을 나타내고 각 단계에서 각 정점을 해당 정점(있는 경우)으로 대체합니다. 적절한 색상으로 그녀에게 전달됩니다.

이제 한 점으로 모일 수 있는 모든 정점 집합을 고려해 보겠습니다. 일부 w Aw에 대해 단 하나의 정점만 포함하는 A입니다. 이러한 모든 집합 중에서 최대 가중치 w(A)를 갖는 집합 A를 최대 집합이라고 합니다. 색상이 동기화되면 전체 그래프 G는 최대 집합(고유)이지만 그렇지 않으면 그렇지 않습니다.

A가 임의의 정점 집합인 경우 α가 모든 d 색상에 걸쳐 실행되는 모든 w(Aα -1)의 합은 d*w(A)와 같습니다. 이는 단순히 가중치의 주요 속성을 일반화한 것입니다. 하나의 정점을 정점 집합 A로 변환합니다. 또한 이 경우 A가 최대 집합인 경우 w(Aα -1) 각각은 w(A)보다 클 수 없습니다. 왜냐하면 이러한 집합도 하나의 정점으로 축소되기 때문입니다. . 그리고 이 가중치의 합 d는 d*w(A)와 같으므로 각각은 w(A)와 같고 이 모든 집합도 최대값임을 알 수 있습니다. A가 최대값이면 Aw -1도 임의의 단어 w에 대해 최대값이 됩니다.

최대 집합은 분리된 인스턴스가 전체 그래프를 포괄할 수 있기 때문에 유용합니다. 그것을 증명해 봅시다.

쌍으로 서로 분리되어 있고 동일한 단어 w에 의해 단일 정점 a 1 ...an으로 축소된 최대 집합 A 1 ...A n 의 집합을 가정합니다(초기 경우 n=1이고 하나만 있을 것입니다) 쉽게 시작할 수 있도록 설정하세요). 모든 a 1 ...an 이 서로 다르다는 것은 분명합니다. 그렇지 않으면 동일한 최종 정점을 가진 다른 요소로 인해 최대 집합을 더 확장하는 것이 가능하기 때문입니다. 모든 A i 가 아직 G의 모든 꼭지점을 모두 소진하지 않았다고 가정하고 x를 모든 A i 외부의 꼭지점이라고 가정합니다. 그래프가 연결되어 있으므로 a 1에서 x까지의 경로 h가 있습니다. 그런 다음 n 최대 세트 A i h -1 w -1은 단어 whw에 따라 최종 정점 a 1 ...an으로 이동하고 최대 세트 A 1은 일부 정점 Awhw = (Aw)hw = (a 1 h)로 이동합니다. w = xw. 이 정점 xw는 또한 모든 a 1 ...an 과 달라야 합니다. 그렇지 않으면 최대 집합 A i 가 요소 x로 보완될 수 있기 때문입니다. 그리고 이 모든 n+1 세트(모든 A i h -1 w -1 더하기 A 1)는 서로 다른 꼭지점으로 이동하므로 모두 쌍으로 분리되어 있습니다. 세트 외부에 정점이 하나도 남지 않을 때까지 이 확장을 계속할 것입니다.

따라서 우리는 서로소 최대 집합으로 전체 그래프 G를 다룰 수 있습니다. 최대값이기 때문에 모두 동일한 전체 w max 를 가지므로 적용 범위의 수는 N max = w(G)/w max 입니다.

이제 쌍으로 구성된 적들로 구성된 집합 A를 생각해 보세요. 예를 들어, 파벌(clique)은 그러한 집합의 예입니다(또한 Gw 형식을 가집니다). 최대 세트는 한 쌍의 적을 포함할 수 없습니다. 왜냐하면 수렴할 수 없기 때문입니다. 이는 N max 최대 세트의 범위에서 각각 최대 하나의 멤버 A를 포함하므로 A의 크기는 최대 N max임을 의미합니다. 구체적으로 말하면 모든 파벌의 규모에 대한 상한선입니다.

A를 Gw 형식의 파벌이라고 가정합니다. 여기서 w는 단어입니다. 그러면 G = Aw -1이고 따라서 w(G)는 합 w(aw -1)과 같습니다. 여기서 a는 A의 모든 정점을 통과합니다. 이전 단락에 따르면 항의 수는 다음을 넘지 않습니다. N max 및 각 세트 aw -1은 한 지점(단어 w가 있는 a 지점)으로 축소될 수 있으므로 해당 가중치는 최대 w max보다 크지 않습니다. 전체 합은 w(G) = N max *w max 와 같으므로 항의 개수는 N max 와 정확히 같고 각 항은 w max 와 정확히 같다고 결론을 내립니다. 우리는 모든 파벌이 동일한 크기, 즉 정확히 N개의 최대 요소를 갖는다는 것을 증명했습니다.

두 파벌 A와 B가 있다고 가정하면 A 내부의 모든 요소는 하나만 제외하고 B와 공유됩니다. |A| - |A∩B| = 1.

A와 B의 크기가 동일하므로 |B|도 있습니다. - |A∩B| = 1, 즉 A와 B는 A에 하나의 정점 p와 B에 하나의 정점 q를 제외하고 모든 요소를 ​​공통으로 갖습니다. 우리는 이 정점 p,q가 안정 친구임을 증명하고 싶습니다. 그렇지 않다면 어떤 단어 w가 그들을 적으로 만듭니다. pw와 qw는 적입니다. 위에서 보듯이 Aw와 Bw도 파벌이며, 적군 pw와 qw를 제외하고는 다시 모든 요소를 ​​공통적으로 갖고 있음이 분명합니다. 그런 다음 집합 Aw ∪ Bw는 쌍별 적의 집합입니다. 실제로 그 안에서 Aw의 모든 요소는 한 쌍의 적입니다. 왜냐하면 그것은 파벌이기 때문입니다. Bw 요소의 경우에도 마찬가지입니다. pw,qw 쌍만 남았고 적들도 남았습니다. 그러나 이 세트에는 N 최대 +1 요소가 있으며 위에서 우리는 쌍으로 된 적 세트가 N 최대 요소보다 많을 수 없음을 보여주었습니다. 이는 모순이므로 pw와 qw는 어떤 w의 적이 될 수 없습니다. 즉, p와 q는 안정적인 친구입니다.

스패닝 그래프 및 파벌

주어진 그래프 G에서 모든 꼭지점을 취하고, 각 꼭지점에서 하나의 나가는 간선만 선택해 보겠습니다. 이 선택은 우리가 호출하는 하위 그래프를 결정합니다. 스패닝 그래프(스패닝 그래프). 다양한 스패닝 그래프가 있을 수 있지만, 그래프가 어떻게 보이는지 조금 생각해 보겠습니다. 특정 스패닝 그래프 R이 있다고 가정합니다. 그 안에 정점 x를 가져와 그 가장자리를 따라가기 시작하면 매번 단일 선택을 하게 됩니다. 왜냐하면 R에는 각 정점에서 나오는 가장자리가 하나만 있기 때문입니다. 나중에 사이클을 종료하겠습니다. 아마도 이 주기는 x에서 닫히지 않지만 "더 먼" 어딘가에서 닫힐 것입니다(예: x-->y-->z-->s-->y). 그런 다음 이 사이클의 "꼬리"는 x에서 시작됩니다. 만약 우리가 다른 꼭지점에서 시작한다면, 우리는 또한 분명히 순환(이것 또는 다른 것)으로 끝날 것입니다. 모든 정점 R은 순환(여러 개가 있을 수 있음)에 있거나 순환으로 이어지는 "꼬리"의 일부인 것으로 나타났습니다. 이는 R이 다음과 같다는 것을 의미합니다. 특정 수의 사이클과 특정 수의 "역전된" 트리가 그 위에 구축됩니다. 각 트리는 시작되지 않고 사이클 중 하나에 있는 "루트"에서 끝납니다.

그래프의 각 정점에 할당할 수 있습니다. 수준, 주어진 확장 그래프 R에서 사이클까지의 거리에 해당합니다. 사이클에 있는 정점은 레벨 0을 가지며, 사이클에 연결된 트리에 있는 정점은 트리에서 루트까지의 거리와 동일한 레벨을 받습니다. ” 사이클에 누워. 그래프의 일부 정점에는 최대 레벨 L이 있습니다. 아마도 0과 같을 수도 있습니다. 나무는 없고 순환만 있을 뿐입니다. 아마도 그것은 0보다 크고, 이 최대 레벨의 정점은 다른 사이클이나 하나에 연결된 모든 종류의 다른 트리에 있습니다.

우리는 다음과 같은 스패닝 그래프 R을 선택하고 싶습니다. 최대 레벨의 모든 정점은 동일한 트리에 위치. 직관적으로 이것이 가능하다고 믿을 수도 있습니다. 왜냐하면 그렇지 않은 경우, 예를 들어 그들은 여러 곳에 흩어져 있기 때문입니다. 다른 나무- 그런 다음 최대 정점 x 중 하나를 선택하고 x로 가는 일부 가장자리를 R에 연결하여 레벨을 높일 수 있습니다. 그런 다음 다른 갈비뼈를 버려야 할 것입니다. 이것이 다른 것에 해를 끼치 지 않는다는 것은 사실이 아닙니다 ... 그러나 이것은 나중에 논의 될 기술적인 문제입니다. 직관적으로 그다지 복잡해 보이지는 않는다는 점을 말씀드리고자 합니다.

지금은 최대 레벨의 모든 정점이 동일한 트리에 위치하도록 R을 선택할 수 있다고 가정해 보겠습니다. 이 트리는 사소하지 않은 것으로 가정됩니다. 최대 레벨 L > 0. 이 가정을 바탕으로 우리는 착색을 구성할 것이며 그 안에는 이전 섹션의 조건을 충족하는 파벌 A와 B가 있으며 이는 이 착색에 안정적인 쌍이 있음을 증명할 것입니다. 친구.

색상은 다음과 같습니다. α 색상을 선택하고 그래프 R의 모든 가장자리를 이 색상으로 색칠하고 그래프 G의 다른 모든 가장자리를 어떤 식으로든 다른 색상으로 색칠합니다(색상이 하나만 있는 경우 R G 와 일치하므로 문제가 없습니다). 따라서 색상 α로 구성된 단어는 트리를 따라 R의 정점을 순환 방향으로 "밀어낸 다음" 순환을 통해 정점을 구동합니다. 이것이 우리에게 필요한 유일한 단어입니다.

x를 R에서 최대 레벨 L의 정점으로 하고 K를 x를 포함한 임의의 클릭으로 놓습니다. 우리는 그러한 파벌이 존재한다는 것을 알고 있습니다. K가 최대 레벨 L의 다른 꼭지점을 포함할 수 있나요? 우리의 가정에 따르면 이러한 모든 정점은 x와 동일한 트리에 있습니다. 이는 α L이라는 단어가 정점을 x와 동일한 위치, 즉 순환에 있는 이 트리의 루트로 가져간다는 것을 의미합니다. 이는 모든 정점이 x의 친구이므로 x와 동일한 도당에 속할 수 없음을 의미합니다. 따라서 K는 x 외에 더 낮은 수준의 정점만 포함할 수 있습니다.

집합 A = Kα L-1을 살펴보겠습니다. 이것은 또한 파벌이며 x를 제외한 모든 정점은 R에서 일종의 순환에 도달했습니다. 왜냐하면 x를 제외한 A의 모든 정점은 L보다 낮은 수준을 갖기 때문입니다. x만 사이클 외부에 남아 있습니다. 사이클의 루트까지 정확히 1의 거리입니다. 이제 R의 모든 사이클 길이의 배수인 숫자 m을 선택해 보겠습니다. 예를 들어 모든 사이클 길이의 곱입니다. m에는 정점 y가 R의 순환에 있는 경우 α m이라는 단어가 이를 해당 위치(yα m = y)로 반환하는 기능이 있습니다. B = Aα m 도당을 살펴보겠습니다. x를 제외한 A의 모든 정점은 순환에 있으므로 B에 남아 있습니다. 그리고 오직 x만이 마침내 그 주기에 들어가 그곳 어딘가에 정착했습니다. 이는 A와 B의 교차점에 |A|를 제외한 A의 모든 정점이 포함된다는 의미입니다. - |A∩B| = 1. 그러나 이는 이전 섹션에 따르면 우리의 색상이 안정적인 쌍을 가지고 있다는 것을 의미하며, 이는 우리가 증명해야 하는 것입니다.

최대 레벨 구축.

중요한 최대 레벨 L > 0을 갖고 이 레벨의 모든 정점이 동일한 트리에 놓이도록 스패닝 그래프 R을 선택하는 것이 항상 가능하다는 것을 증명하는 것이 남아 있습니다.

이 증명의 일부는 다소 지루하고 기술적인 보조정리입니다. 읽고 확인했지만 반복하지는 않겠습니다. 관심 있는 분들을 위해 기사의 어디에 있는지만 말씀드리겠습니다. 하지만 이 보조정리에 도달하는 방법을 알려 드리겠습니다.

그래프 G에 부과할 수 있는 두 가지 제한이 필요합니다. 먼저 G에 루프가 없다고 가정해 보겠습니다. 꼭지점에서 같은 꼭지점까지의 가장자리. 요점은 그래프에 루프가 있으면 다른 방법으로 동기화 색상을 찾는 것이 매우 쉽다는 것입니다. 이 루프를 α 색상으로 색칠한 다음 이 꼭지점에서 "화살표 반대" 반대 방향으로 이동하여 색상 α가 항상 이 꼭지점으로 연결되도록 가장자리를 색칠해 보겠습니다. 그래프가 연결되어 있기 때문에 정렬하기 쉽고 루프는 어느 정도 α가 전체 그래프를 이 꼭지점으로 축소하도록 보장합니다.

다음으로, 어떤 꼭지점 p에서 모든 d 모서리가 동일한 꼭지점 q로 이어진다고 잠시 가정해 보겠습니다. 이는 조건에 따라 허용되지만 이 경우에는 이 모서리 세트를 호출합니다. 다발. 두 번째 제약은 다음과 같습니다. 서로 다른 정점 p와 q의 두 링크가 연결되는 정점 r이 없습니다. 왜 우리는 그것을 부과할 수 있는가? 왜냐하면 p와 q로부터 r에 연결이 있다면, p,q 착색첫 번째 색상 이후 꼭지점 r에 수렴하므로 안정적인 친구입니다. 따라서 이 경우에는 스패닝 그래프와 클릭의 모든 구성이 필요하지 않으며 즉시 안정적인 친구를 얻습니다. 그러므로 우리는 이것이 사실이 아니라고 가정할 수 있습니다.

마지막으로 우리는 모든 정점이 순환에 있지는 않지만 일부 중요하지 않은 트리가 있는 스패닝 그래프 R이 항상 존재한다는 것을 증명합니다. 일부 R을 선택하고 모든 정점이 순환에 있다고 가정해 보겠습니다. 그래프 G의 모든 간선이 연결된 경우, 즉 항상 동일한 정점을 떠나는 모든 d 가장자리는 동일한 정점으로 이어집니다. 그러면 R을 선택하면 각 링크에서 하나의 가장자리만 선택하게 됩니다. 이 경우 R에는 단 하나의 사이클만 있을 수 있습니다(결국 R의 여러 사이클은 연결된 그래프 G에서 서로 연결될 수 없습니다. G의 모든 가장자리는 R의 가장자리와 동일한 정점에만 연결됩니다. 이것은 연결이기 때문에 G는 연결되어 있기 때문에 불가능합니다. G의 모든 사이클은 단순히 이 사이클의 연결에서 다른 가장자리를 선택하지만 본질적으로 동일한 사이클, 동일한 길이입니다. 그러나 이는 G의 모든 사이클의 길이가 이 길이로 나누어질 수 있음을 의미하며 이는 G의 비주기성과 정확히 모순됩니다. 따라서 G의 모든 모서리가 링크 위에 있을 수는 없습니다. 이는 두 개의 모서리가 있음을 의미합니다. R의 p-->q, R 외부의 p-->s(p의 일부 가장자리가 스패닝 그래프에 있을 뿐만 아니라 다른 정점 s로 이어진다는 것을 증명하기 위해 연결에 대한 긴 인수가 필요했습니다). 그런 다음 p-->q를 p-->s로 바꾸면 순환이 "깨져" 일종의 꼬리가 생성됩니다. 이 꼬리는 새 그래프에 중요한 트리를 제공합니다.

이제 우리는 중요하지 않은 트리를 포함하는 모든 스패닝 그래프 R에서 사이클의 최대 정점 수를 갖는 일부 R을 선택할 수 있습니다. 그건 사이클에 없는 정점이 있지만 이러한 제한 외에도 사이클에 있는 정점의 수가 최대화됩니다. 이 그래프에는 최대 레벨 L의 정점이 몇 개 있으며, 이들이 다른 루트로 이어지는 트리에 있다고 가정할 수 있습니다. 그렇지 않으면 이미 필요한 것을 달성했습니다. 꼭지점 x 중 하나를 선택해 보겠습니다. 우리는 이 정점이 L보다 긴 트리에서 더 긴 경로의 일부가 되고 다른 트리는 변경되지 않도록 그래프를 변경하고 최대 레벨은 우리가 원하는 하나의 트리에만 있도록 하고 싶습니다. 다음 세 가지 방법으로 그래프를 변경할 수 있습니다.

a) 일부 가장자리 y-->x를 가져와 R에 추가하고 기존 가장자리 y-->z를 삭제합니다.
b) x에서 해당 사이클(사이클의 r)까지 경로의 마지막 가장자리인 b-->r을 가져와서 버리고 다른 b-->z를 추가합니다.
c) 사이클의 일부인 가장자리 c-->r을 가져와서 버리고 다른 c-->z를 추가합니다.

Trakhtman 논문의 Lemma 7은 이러한 변경 중 하나(또는 어떤 경우에는 두 개)가 원하는 결과를 가져온다는 것을 자세히 증명합니다. 프로세스는 R의 최대성(일부 변화로 인해 R보다 주기에 더 많은 수의 정점이 있는 그래프가 발생하는 경우 이는 최대성과 모순됨)과 두 링크가 연결되는 정점이 없다는 위에서 정의된 조건을 모두 사용합니다. 결과적으로 어쨌든 우리는 최대 레벨의 모든 정점이 하나의 중요하지 않은 트리에 있는 그래프 R을 얻습니다.

일주일 후 업데이트:그럼에도 불구하고 나는 이 항목을 완전히 자급자족하도록 만들고 이전 단락에서 언급한 보조정리의 증명을 다시 말하기로 결정했습니다. 도표로 하면 더 좋겠지만, 그림으로 그리거나 기사에서 찢고 싶지는 않아서 말로 해보도록 하겠습니다. 따라서 우리가 사소하지 않은 트리가 있고 그 안에 그러한 모든 그래프가 있는 스패닝 그래프 R이 있다고 상상해보십시오. 최대 금액꼭지점은 순환에 있습니다. 우리는 R을 최대 레벨의 모든 정점이 동일한 트리에 있는 스패닝 그래프로 변환하는 것을 목표로 합니다. 시도하는 과정에서 이러한 그래프를 얻자마자 우리는 즉시 종료합니다(그리고 사이클의 정점 수 측면에서 그래프의 최대치가 손실될 수 있다는 점은 신경 쓰지 않습니다. 이는 우리에게 중요하지 않습니다. 그 자체는 프로세스에서만 사용됩니다). x를 최대 레벨 L의 꼭지점, T를 해당 트리가 있는 트리, r을 T가 끝나는 주기 C의 꼭지점, b-->r을 x에서 주기 C까지의 경로에서 r 앞의 마지막 가장자리로 둡니다. 우리는 이 사이클에 합류하는 다른 트리나 레벨 L의 정점을 갖는 다른 트리가 있다고 가정할 수 있습니다. 그렇지 않으면 모든 것이 이미 완료되었습니다. 따라서 T에서 L보다 더 큰 요소를 가진 트리를 얻을 수 있고 다른 트리를 확장하지 않으면 작업이 완료됩니다.

먼저 위의 a) 작업을 수행해 보겠습니다. G에서 y-->x 모서리를 취합니다. 존재하기 때문에 존재합니다. 그래프는 연결되어 있고 루프가 없으며 R에 있지 않습니다. x 최대 레벨. R에 추가하고 이전에 있던 y-->z를 버립니다. y가 트리 T에 있으면 y-->x는 새 주기를 닫고 새 그래프에서 더 많은 정점이 주기에 있으며 여전히 중요하지 않은 트리(적어도 R에 있던 다른 트리)가 있습니다. R의 최대성과 모순됩니다. y가 T에 있지 않고 y-->z가 주기 C의 일부가 아닌 경우 y-->z를 제거해도 이 주기가 중단되지 않지만 y-->x를 추가하면 최대값이 확장됩니다. 트리 T의 레벨을 최소한 1만큼 높이고 나머지는 트리가 늘어나지 않으므로 끝났습니다. 이제 중단된 주기 C에 y-->z가 놓여 있고 새로운 주기가 형성되었을 때 옵션이 남아 있습니다. 즉, r에서 y로, 그 다음 y-->x로, 그런 다음 x에서 r로 이어집니다. 이전 나무. 이 주기의 길이는 l(ry)+1+L이고, 이전 주기 C의 길이는 l(ry)+1+l(zr)입니다. 새로운 주기는 이전 주기보다 길 수 없습니다. 이는 R의 최대값과 모순되므로 L ≤ l(zr), 즉 다음과 같습니다. 이전 루프에서 z에서 r까지의 경로 길이. 반면에 새 그래프에서 정점 z는 이제 최소한 l(zr)의 레벨을 가지며, 이것이 L보다 크면 작업이 완료된 것입니다. 따라서 l(zr)=L이라고 가정할 수 있습니다. 요약하자면, a)가 작동하지 않는다고 가정하고 y-->z가 사이클 C, l(zr) = L에 있다는 것을 알고 있습니다.

이제 b) 작업을 시도해 보겠습니다. 가장자리 b-->r을 다른 가장자리 b-->d로 바꿉니다. 새로운 정점 d가 어디에 있는지 봅시다. 트리 T에 있는 경우 이전 순환을 깨지 않고 새 주기를 생성하고 R의 최대값이 반증되었음을 증명합니다. 다른 트리에 있는 경우 x를 포함한 T의 최대 정점은 이제 L보다 큰 수준을 갖게 됩니다. 다른 나무는 그렇지 않으며 우리는 끝났습니다. C가 아닌 다른 사이클에 있다면 이제 b)도 a)와 함께 수행할 것입니다. y-->z가 C에 있다는 것을 알고 있으므로 이 작업은 C를 분할하지만 새로운 사이클은 분할하지 않습니다. 이제 연결된 트리 T가 있고 이 트리에는 L보다 더 큰 레벨의 정점이 있으며 다시 완료됩니다.

나머지 옵션은 b-->d가 r이 아닌 다른 위치 또는 동일한 위치에서 d=r인 사이클 C에도 연결되는 경우입니다. b-->r을 b-->d로 바꾼 후 처음과 동일한 상황(트리 T, 레벨 L의 정점 x 등)이 발생했습니다. - 이제 트리만 정점 d를 통해 순환에 연결됩니다. 이제 연산 a)를 고려하면, 이전에 l(zr) = L이라고 결론지었던 것처럼 l(zd) = L이라고 결론을 내립니다(작동하지 않는다고 가정). 그러나 l(zd) = l(zr), 즉 z에서 사이클을 따른 거리는 d와 r과 동일하며, 이는 동일한 정점입니다: d=r. 따라서 b)가 작동하지 않으면 b의 모든 간선은 r로 이어져야 합니다. 즉, b의 가장자리는 링크를 형성합니다.

마지막으로, 사이클 C에 있는 가장자리 c-->r을 고려하십시오. b의 모든 가장자리가 r로 이어지는 링크에 있다고 가정할 수 있으므로 위에서 언급한 두 개의 링크가 있을 수 없다는 제약 조건을 부과할 수도 있습니다. 하나의 꼭지점, c의 모든 가장자리가 r로 이어지는 것은 아니지만 일부 가장자리 c-->e가 있습니다. c-->r을 c-->e로 바꾸겠습니다. 꼭지점 e는 어디에 놓일 수 있나요? 트리 T에는 없습니다. 왜냐하면 R의 최대값과 모순되어 주기 C를 "확장"하기 때문입니다. 따라서 e는 다른 트리나 다른 주기, 심지어 동일한 주기 C에 있지만 정점 r에는 없습니다. 그런 다음 트리 T는 루프에 합류하기 전에 이제 r에서 나오는 최소한 하나의 가장자리로 확장되고 아마도 그 이상으로 확장됩니다(e가 r 바로 뒤에 있고 c-->e가 루프 C를 다시 닫는 경우 하나만 확장됩니다. 그것으로부터 r만 파생됨). 이는 정점 x와 기타 최대 정점 T가 이제 L+1 이상의 레벨을 가지며 다른 트리는 길어지지 않았으며 다시 필요한 것을 얻었음을 의미합니다.