그래프 이론-기본 속성
그래프에는 구조에 따라 그래프의 특성화에 사용되는 다양한 속성이 있습니다. 이러한 속성은 그래프 이론의 영역과 관련된 특정 용어로 정의됩니다. 이 장에서는 모든 그래프에서 공통적 인 몇 가지 기본 속성에 대해 설명합니다.
두 정점 사이의 거리
정점 U와 정점 V 사이의 최단 경로에있는 가장자리 수입니다. 두 정점을 연결하는 경로가 여러 개인 경우 가장 짧은 경로가 두 정점 사이의 거리로 간주됩니다.
표기법 − d (U, V)
한 정점에서 다른 정점으로의 경로는 얼마든지있을 수 있습니다. 그중 가장 짧은 것을 선택하면됩니다.
Example
다음 그래프를보세요-
여기서, 꼭지점 'd'에서 꼭지점 'e'또는 단순히 'de'까지의 거리는 그들 사이에 하나의 가장자리가 있기 때문에 1입니다. 꼭지점 'd'에서 꼭지점 'e'까지의 경로가 많이 있습니다.
- da, ab, be
- df, fg, ge
- de (정점 사이의 거리로 간주 됨)
- df, fc, ca, ab, be
- da, ac, cf, fg, ge
꼭지점의 편심
정점에서 다른 모든 정점까지의 최대 거리는 정점의 이심률로 간주됩니다.
표기법 − e (V)
그래프의 특정 정점에서 다른 모든 정점까지의 거리가 취해지며이 거리 중에서 편심이 가장 높은 거리입니다.
Example
위 그래프에서 'a'의 이심률은 3입니다.
'a'에서 'b'까지의 거리는 1 ( 'ab')입니다.
'a'에서 'c'는 1 ( 'ac')입니다.
'a'에서 'd'는 1 ( 'ad')입니다.
'a'에서 'e'는 2 ( 'ab'- 'be') 또는 ( 'ad'- 'de')입니다.
'a'에서 'f'는 2 ( 'ac'- 'cf') 또는 ( 'ad'- 'df')입니다.
'a'에서 'g'는 3 ( 'ac'- 'cf'- 'fg') 또는 ( 'ad'- 'df'- 'fg')입니다.
따라서 이심률은 3으로, 최대 인 'ag'사이의 거리에서 정점 'a'에서 최대 값입니다.
다시 말해,
e (b) = 3
e (c) = 3
e (d) = 2
e (e) = 3
e (f) = 3
예 (g) = 3
연결된 그래프의 반경
모든 정점의 최소 편심은 그래프 G의 반경으로 간주됩니다. 정점과 다른 모든 정점 사이의 모든 최대 거리 중 최소값은 그래프 G의 반경으로 간주됩니다.
표기법 − r (G)
그래프의 모든 정점 편심에서 연결된 그래프의 반경은 모든 편심 중 최소값입니다.
Example
위 그래프에서 r (G) = 2는 'd'의 최소 편심입니다.
그래프 지름
모든 정점의 최대 편심은 그래프 G의 직경으로 간주됩니다. 정점과 다른 모든 정점 사이의 모든 거리 중 최대 값은 그래프 G의 직경으로 간주됩니다.
Notation − d(G) − 그래프의 모든 정점 편심에서 연결된 그래프의 직경은 모든 편심의 최대 값입니다.
Example
위의 그래프에서 d (G) = 3; 이는 최대 편심입니다.
센트럴 포인트
그래프의 이심률이 반경과 같으면 그래프의 중심점이라고합니다. 만약
e (V) = r (V),
'V'는 그래프 'G'의 중심점입니다.
Example
예제 그래프에서 'd'는 그래프의 중심점입니다.
e (d) = r (d) = 2
센터
'G'의 모든 중심점 집합을 그래프의 중심이라고합니다.
Example
예제 그래프에서 { 'd'}는 그래프의 중심입니다.
둘레
그만큼 number of edges in the longest cycle of ‘G’ 'G'의 둘레라고합니다.
Example
예제 그래프에서 원주는 6이며, 가장 긴주기 인 acfgeba 또는 acfdeba에서 파생되었습니다.
테두리
'G'의 가장 짧은주기의 모서리 수를 Girth라고합니다.
Notation: g (G).
Example − 예제 그래프에서 그래프의 둘레는 4이며, 가장 짧은주기 acfda 또는 dfged 또는 abeda에서 파생되었습니다.
정점 차수의 합 정리
G = (V, E) 정점이 V = {V 1 , V 2 ,… V n } 인 무 방향 그래프 이면
Corollary 1
G = (V, E) 정점이 V = {V 1 , V 2 ,… V n } 인 유 방향 그래프 이면
Corollary 2
방향이없는 그래프에서 홀수 차수가있는 정점의 수는 짝수입니다.
Corollary 3
무 방향 그래프에서 각 꼭지점의 차수가 k이면
Corollary 4
무 방향 그래프에서 각 꼭지점의 차수가 k 이상이면
| Corollary 5
무 방향 그래프에서 각 꼭지점의 차수가 최대 k이면