그래프 이론-동형
그래프는 동일한 수의 꼭지점, 가장자리 및 동일한 가장자리 연결을 갖는 다른 형태로 존재할 수 있습니다. 이러한 그래프를 동형 그래프라고합니다. 이 장에서는 주로 그래프를 참조하고 서로 인식 할 목적으로 그래프에 레이블을 지정합니다.
동형 그래프
두 그래프 G 1 및 G 2 는 다음과 같은 경우 동형이라고합니다.
구성 요소 (정점 및 모서리)의 수는 동일합니다.
에지 연결이 유지됩니다.
Note-간단히 말해서, 두 개의 동형 그래프 중 하나는 다른 하나의 수정 된 버전입니다. 레이블이없는 그래프도 동형 그래프로 생각할 수 있습니다.
There exists a function ‘f’ from vertices of G1 to vertices of G2
[f: V(G1) ⇒ V(G2)], such that
Case (i): f is a bijection (both one-one and onto)
Case (ii): f preserves adjacency of vertices, i.e., if the edge {U, V} ∈ G1, then the
edge {f(U), f(V)} ∈ G2, then G1 ≡ G2.Note
G 1 ≡ G 2 다음-
| V (G 1 ) | = | V (G 2 ) |
| E (G 1 ) | = | E (G 2 ) |
G 1 과 G 2 의 차수 시퀀스 는 동일합니다.
정점 {V 1 , V 2 , .. Vk}가 G 1 에서 길이 K의주기를 형성 하면 정점 {f (V 1 ), f (V 2 ),… f (Vk)}가주기를 형성해야합니다. 길이 K in G 2 .
위의 모든 조건은 그래프 G 1 및 G 2 가 동형이 되려면 필요하지만 그래프가 동형임을 증명하는 데 충분하지 않습니다.
(G 1 ≡ G 2 ) (G 1 − ≡ G 2 −) 여기서 G 1 과 G 2 가 단순한 그래프 인 경우에만 .
(G 1 ≡ G 2 ) G 1 과 G 2 의 인접 행렬 이 같은 경우.
(G 1 ≡ G 2 ) G의 대응하는 서브 그래프 만하고 있으면 1 및 G 2 (G1 일부 정점 그래프 G에서의 이미지 삭제함으로써 얻어지는 2 ) 동형이다.
Example
다음 중 동형 그래프는 무엇입니까?
그래프 G 3 에서 정점 'w'는 차수가 3 뿐인 반면 다른 모든 그래프 정점은 차수가 2입니다. 따라서 G3은 G 1 또는 G 2 와 동형이 아닙니다 .
G 1 과 G 2 를 보완 하면-
여기에서 (G 1 -≡ G 2- ), 따라서 (G 1 ≡ G 2 ).
평면 그래프
그래프 'G'는 두 모서리가 정점이 아닌 점에서 서로 교차하지 않도록 평면이나 구에 그릴 수 있으면 평면이라고합니다.
Example
지역
모든 평면형 그래프는 평면을 영역이라고하는 연결된 영역으로 나눕니다.
Example
경계 영역의 정도 r = deg(r) = 영역을 둘러싸는 가장자리 수 r.
deg(1) = 3
deg(2) = 4
deg(3) = 4
deg(4) = 3
deg(5) = 8
무한 영역의 정도 r = deg(r) = 영역을 둘러싸는 가장자리 수 r.
deg(R1) = 4
deg(R2) = 6평면 그래프에서 다음 속성은 양호합니다.
'n'꼭지점이있는 평면 그래프에서 모든 꼭지점의 각도 합계는 다음과 같습니다.
에 따르면 Sum of Degrees of Regions/ 정리, 'n'영역이있는 평면 그래프에서 영역의 합은 다음과 같습니다.
위의 정리를 바탕으로 다음과 같은 결론을 내릴 수 있습니다.
평면 그래프에서
각 영역의 차수가 K이면 영역의 차수의 합은-
각 영역의 차수가 K (≥ K) 이상이면
각 영역의 차수가 기껏해야 K (≤ K)이면
Note − 모든 지역의 차수가 같다고 가정합니다.
에 따르면 Euler’s Formulae 평면형 그래프에서
그래프 'G'가 연결된 평면형이면
'K'성분이 포함 된 평면형 그래프의 경우
여기서 | V | 정점의 수, | E | 은 모서리의 수이고 | R | 지역 수입니다.
가장자리 정점 부등식
'G'가 각 영역의 정도가 'K'이상인 연결된 평면 그래프이면,
| E | ≤ k / (k-2) {| v | -2}
알다시피 | V | + | R | = | E | + 2
K. | R | ≤ 2 | E |
K (| E |-| V | + 2) ≤ 2 | E |
(K-2) | E | ≤ K (| V |-2)
| E | ≤ k / (k-2) {| v | -2}
'G'가 단순 연결된 평면 그래프 인 경우
|E| ≤ 3|V| − 6
|R| ≤ 2|V| − 4deg (V) ≤ 5 인 꼭지점 V • ∈ G가 하나 이상 있습니다.
'G'가 단순 연결된 평면 그래프 (최소 2 개의 모서리 포함)이고 삼각형이없는 경우
|E| ≤ {2|V| – 4}Kuratowski의 정리
그래프 'G'는 'G'에 K 5 또는 K 3,3 동종인 부분 그래프가있는 경우에만 비평면 입니다.
동형
G의 일부 모서리를 더 많은 꼭짓점으로 나누어 동일한 그래프 'G'에서 각 그래프를 얻을 수있는 경우 두 그래프 G 1 및 G 2 는 동형이라고합니다. 다음 예를 살펴보십시오-
하나의 정점을 추가하여 가장자리 'rs'를 두 개의 가장자리로 나눕니다.
아래에 표시된 그래프는 첫 번째 그래프와 동형입니다.
G 1 이 G 2 에 대해 동형 인 경우 G는 G2에 대해 동형이지만 그 반대가 사실 일 필요는 없습니다.
꼭지점이 4 개 이하인 모든 그래프는 평면입니다.
모서리가 8 개 이하인 모든 그래프는 평면입니다.
완전한 그래프 K n 은 n ≤ 4 인 경우에만 평면입니다.
완전한 이분 그래프 K m, n 은 m ≤ 2 또는 n ≤ 2 인 경우에만 평면입니다.
최소 정점 수가있는 단순한 비평면 그래프는 완전한 그래프 K 5 입니다.
최소 간선 수가있는 단순 비평면 그래프는 K 3, 3 입니다.
다면체 그래프
단순 연결된 평면 그래프는 각 꼭지점의 차수가 ≥ 3, 즉 deg (V) ≥ 3 ∀ V ∈ G 인 경우 다면체 그래프라고합니다.
3 | V | ≤ 2 | E |
3 | R | ≤ 2 | E |