어떤 모서리도 교차하지 않도록 평면에 그릴 수 있는 그래프를 평면형 그래프라고 합니다.

예: 그림에 표시된 그래프는 평면 그래프입니다.

크루스칼 알고리즘'

그래프 영역: 평면 그래프 G=(V,E)를 생각해 보세요. 영역은 가장자리로 둘러싸여 있고 더 이상 세분화될 수 없는 평면 영역으로 정의됩니다. 평면 그래프는 계획을 하나 이상의 지역으로 나눕니다. 이 영역 중 하나는 무한합니다.

유한 영역: 영역의 면적이 유한하면 해당 영역을 유한 영역이라고 합니다.

무한 지역: 영역의 면적이 무한하다면 그 영역을 무한 영역이라고 합니다. 평면 그래프에는 무한 영역이 하나만 있습니다.

예: 그림에 표시된 그래프를 고려하십시오. 영역 수, 유한 영역 및 무한 영역을 결정하십시오.

해결책: 위 그래프에는 5개의 영역이 있습니다. 즉, r₁,아르 자형₂,아르 자형_삼,아르 자형₄,아르 자형₅.

그래프에는 4개의 유한 영역이 있습니다. 즉, r₂,아르 자형_삼,아르 자형₄,아르 자형₅.

단 하나의 유한 영역, 즉 r이 있습니다.₁

평면 그래프의 속성:

1. 연결된 평면 그래프 G에 e개의 간선과 r개의 영역이 있으면 r ≤ 그것은.
2. 연결된 평면 그래프 G에 e개의 모서리, v개의 꼭지점, r개의 영역이 있는 경우 v-e+r=2입니다.
3. 연결된 평면 그래프 G에 e개의 모서리와 v개의 꼭짓점이 있으면 3v-e≧6입니다.
4. 완전한 그래프 K_Nn이 평면인 경우에만<5.< li>
5. 완전한 이분 그래프 K_백만m3이 평면인 경우에만 가능합니다.

예: 완전한 그래프 K를 증명하라₄평면적이다.

해결책: 완전한 그래프 K₄꼭지점 4개와 모서리 6개를 포함합니다.

우리는 연결된 평면 그래프의 경우 3v-e≧6이라는 것을 알고 있습니다. 따라서 K에 대한 것입니다.₄, 우리는 속성 (3)을 만족하는 3x4-6=6을 가집니다.

검색 알고리즘

따라서 K₄평면 그래프이다. 따라서 입증되었습니다.

비평면 그래프:

어떤 모서리도 교차하지 않도록 평면에 그릴 수 없는 그래프를 비평면형 그래프라고 합니다.

예: 그림에 표시된 그래프는 비평면 그래프입니다.

이 그래프는 모서리가 교차하지 않도록 평면에 그릴 수 없으므로 비평면 그래프입니다.

비평면 그래프의 속성:

그래프가 K와 동형인 부분 그래프를 포함하는 경우에만 그래프는 비평면입니다.₅또는 K_3.3

a b c 숫자

예1: K를 보여주세요₅비평면적입니다.

해결책: 완전한 그래프 K₅5개의 꼭지점과 10개의 모서리를 포함합니다.

이제 연결된 평면 그래프의 경우 3v-e≧6입니다.

따라서 K의 경우₅, 3 x 5-10=5(6보다 크거나 같아야 하기 때문에 속성 3을 충족하지 않음)가 있습니다.

따라서 K₅비평면 그래프이다.

예2: K와 동형인 하위 그래프를 찾아 그림에 표시된 그래프가 비평면임을 보여줍니다.₅또는 K_3.3.

해결책: 모서리를 제거하면(V₁,안에₄),(안에_삼,안에₄)와 (V₅,안에₄) 그래프 G₁,K와 동형이 된다₅.따라서 비평면적입니다.

모서리 V를 제거하면_2,V7) 그래프 G₂K와 동형이 된다_3.3.따라서 비평면입니다.

그래프 색상:

G= (V,E)가 다중 간선이 없는 그래프라고 가정합니다. G의 정점 컬러링은 인접한 정점이 서로 다른 색상을 갖도록 G의 정점에 색상을 할당하는 것입니다. M-Color를 사용하는 G의 채색이 존재하는 경우 그래프 G는 M-Colorable입니다.

적절한 색칠: 인접한 두 정점 u와 v가 서로 다른 색상을 가지면 색칠이 적절하며, 그렇지 않으면 부적절한 색칠이라고 합니다.

예: 다음 그래프와 색상 C={r, w, b, y}를 고려하세요. 모든 색상 또는 더 적은 색상을 사용하여 그래프를 적절하게 색칠하세요.

행과 열

그림에 표시된 그래프는 최소 3색 지정이 가능하므로 x(G)=3입니다.

해결책: 그림은 네 가지 색상을 모두 적절하게 채색한 그래프를 보여줍니다.

그림은 세 가지 색상으로 적절하게 색칠된 그래프를 보여줍니다.

G의 색수: 그래프 G의 적절한 색상을 생성하는 데 필요한 최소 색상 수를 G의 유채색수라고 하며 x(G)로 표시합니다.

예: K의 색수_Nn이다.

해결책: K의 컬러링_N각 정점에 서로 다른 색상을 할당하여 n개의 색상을 사용하여 구성할 수 있습니다. 이 그래프의 두 정점은 모두 인접해 있으므로 두 정점에 동일한 색상을 할당할 수 없습니다. 따라서 K의 색수_N=n.

그래프 채색의 응용

그래프 색상 지정의 일부 응용 프로그램은 다음과 같습니다.

• 등록 할당
• 지도 색칠하기
• 이분 그래프 검사
• 모바일 무선 주파수 할당
• 시간표 작성 등

핸드쉐이킹 정리(Handshaking Theorem)를 진술하고 증명하십시오.

핸드쉐이킹 정리: 그래프 G의 모든 꼭짓점의 각도의 합은 그래프의 간선 수의 두 배와 같습니다.

수학적으로는 다음과 같이 말할 수 있습니다.

∑_v∈V각도(v)=2e

증거: G = (V, E)를 V = {v인 그래프로 설정합니다.₁,안에₂, . . . . . . . . . .}는 꼭짓점 집합이고 E = {e₁,그것은₂. . . . . . . . . .}는 가장자리의 집합입니다. 우리는 모든 가장자리가 두 정점 사이에 있으므로 각 정점에 1차를 제공한다는 것을 알고 있습니다. 따라서 각 모서리는 그래프의 2차에 기여합니다. 따라서 모든 정점의 각도의 합은 G의 모서리 수의 두 배와 같습니다.

따라서 ∑_v∈V각도(v)=2e

평균 대 평균