그래프 이론의 응용
평면 그래프
그래프 G는 꼭짓점이 모두 별개의 점이고 가장자리가 단순한 곡선이며 터미널을 제외한 두 가장자리가 서로 만나지 않는 방식으로 평면에 표현 될 수있는 경우 평면이라고합니다. 예를 들어, 4 개의 정점에 대한 전체 그래프 인 K 4 는 평면입니다 (그림 4A 참조).
에지의 세분화에 의해 동일한 그래프로부터 둘 다를 얻을 수 있다면 2 개의 그래프는 동종 이형이라고한다. 예를 들어,도 4A 및도 4B의 그래프는 동종 이형이다.
K m, n 그래프는 꼭짓점 세트가 두 개의 부분 집합으로 나뉘어 질 수있는 그래프입니다. 동일한 부분 집합의 두 정점은 인접하지 않지만 다른 부분 집합의 두 정점은 인접합니다. 1930 년 폴란드의 수학자 카 지미 에르 즈 쿠라 토프 스키는 다음과 같은 유명한 정리를 증명했습니다.
그래프 G가 평면이되기 위해 필요하고 충분한 조건 은 그림 5에 표시된 K 5 또는 K 3,3의 동종 모형을 포함하지 않는 것 입니다.
그래프 G의 기본 수축은 G를 새로운 그래프 G 1 로 변환 한 것으로, G의 인접한 두 정점 u와 υ는 G 1 의 새로운 정점 w로 대체되고 w는 G 1의 모든 정점에 인접 합니다. U 또는 υ는 G에 인접 해있다. 그래프 G *는 일련의 기본 수축에 의해 G로부터 G *를 얻을 수 있다면 G의 수축이라고한다. 다음은 1937 년 독일 수학자 K. 바그너 (K. Wagner)로 인한 평면 그래프의 또 다른 특징입니다.
그래프가 K 5 또는 K 3,3으로 수축 할 수없는 경우에만 평면 입니다.
4 색지도 문제
1 세기 이상 4 색지도 문제의 해결책은 그것을 시도한 모든 분석가를 피했다. 이 문제는 모 비우스의 관심을 끌었을 수도 있지만, 1852 년 프란시스 구스 리가 그의 동생 인 아우구스투스 드 모건의 학생에게 보낸 서한 인 것 같습니다.
문제는 평면지도, 즉 평면을 세밀한 곡선으로 둘러싸인 겹치지 않는 영역으로 세분화하는 것입니다. 지리적 인지도에서 경험적으로 관찰 된 바와 같이 많은 특별한 경우에, 공통 경계를 공유하는 2 개의 영역이 항상 다르게 색을 입히도록 영역을 착색하기 위해 최대 4 개의 색이 필요하다는 것이 경험적으로 관찰되었다 경우에 따라 4 가지 이상의 색상이 필요합니다. 미국의 콜로라도 및 애리조나 주와 같은 특정 지점에서만 만나는 지역은 공통 경계를 갖는 것으로 간주되지 않습니다. 이 경험적 관찰의 공식화는 소위“4 색 정리”를 구성합니다. 문제는 이것이 모든 평면 맵의 경우라는 주장을 증명하거나 반증하는 것입니다. 1890 년에 영국의 수학자 PJ Heawood가 5 가지 색상으로 충분하다고 증명 한 반면, 5 가지 색상으로 충분하다고 입증되었습니다.
1879 년 영국인 AB Kempe는 4 가지 색 문제에 대한 해결책을 제안했습니다. Heawood는 Kempe의 주장에 결함이 있음을 보여 주었지만, 그 중 두 가지 개념은 이후 조사에서 유익한 것으로 판명되었습니다. 불가피성이라고 불리는 이들 중 하나는 네 가지 구성 중 하나가없는 맵을 구성 할 수 없다는 것을 정확하게 나타냅니다 (이러한 구성은 이웃이 2 개, 지역이 1 개, 3 개, 4 개, 5 개). 감소라는 두 번째 개념은 최소한 5 가지 색상이 필요하고 4 개 (또는 3 개 또는 2 개)의 이웃이있는 지역이 포함 된지도가 5 개가 필요한지도가 있어야한다는 Kempe의 유효한 증거에서 이름을 얻습니다. 더 적은 수의 영역에 대한 색상. 켐프는 5 명의 이웃이있는 지역을 포함하는지도의 축소 가능성을 증명하려는 시도가 잘못되었지만 미국의 케네스 아펠 (Kenneth Appel)과 볼프강 하켄 (Wolfgang Haken)이 1976 년에 발표 한 증거로 수정되었습니다. 그들의 증거는 각각 500,000 개의 논리 연산을 포함하는 1,936 개의 별개의 사례에 대한 평가가 필요했기 때문에 약간의 비판을 불러 일으켰습니다. Appel, Haken 및 공동 작업자는 대형 디지털 컴퓨터에서 이러한 세부 사항을 처리 할 수있는 프로그램을 고안했습니다. 컴퓨터는 작업을 수행하는 데 1,000 시간 이상이 필요했으며 결과적으로 정식 증거는 수백 페이지입니다.
Eulerian주기와 Königsberg 교량 문제
멀티 그래프 G는 비어 있지 않은 정점의 V (G) 집합과 각 쌍에 주파수 f ≥ 1이 첨부 된 V (G)의 개별 요소의 정렬되지 않은 쌍의 집합의 하위 집합 E (G)로 구성됩니다. 주파수가 f 인 쌍 (x 1, x 2)이 E (G)에 속하는 경우 정점 x 1 및 x 2 는 f 모서리로 연결됩니다.
다중 그래프 G의 Eulerian주기는 각 모서리가 정확히 한 번 나타나는 닫힌 체인입니다. 오일러는 멀티 그래프가 (격리 된 점과는 별개로) 연결되어 있고 홀수도의 정점 수가 0 또는 2 인 경우에만 유 레리 안주기를 가짐을 보여주었습니다.
이 문제는 먼저 다음과 같은 방식으로 발생했습니다. 두 지점의 합류로 형성된 Pregel River는 Königsberg 마을을지나 Kneiphof 섬의 양쪽으로 흐릅니다. 도 6A에 도시 된 바와 같이, 7 개의 브릿지가 있었다. 마을 사람들은 한 번만 걸어 다닐 수 있고 다리를 건너는 것이 가능한지 궁금했습니다. 이것은 그림 6B의 다중 그래프에 대한 Eulerian주기를 찾는 것과 같습니다. 오일러는 홀수의 정점이 4 개이기 때문에 불가능하다는 것을 보여주었습니다.
