그래프 이론-기본 속성

그래프에는 구조에 따라 그래프의 특성화에 사용되는 다양한 속성이 있습니다. 이러한 속성은 그래프 이론의 영역과 관련된 특정 용어로 정의됩니다. 이 장에서는 모든 그래프에서 공통적 인 몇 가지 기본 속성에 대해 설명합니다.

두 정점 사이의 거리

정점 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 } 인 무 방향 그래프 이면

n Σ i = 1 deg (V i ) = 2 | E |

Corollary 1

G = (V, E) 정점이 V = {V 1 , V 2 ,… V n } 인 유 방향 그래프 이면

n Σ i = 1도 + (V i ) = | E | = n Σ i = 1도 − (V i )

Corollary 2

방향이없는 그래프에서 홀수 차수가있는 정점의 수는 짝수입니다.

Corollary 3

무 방향 그래프에서 각 꼭지점의 차수가 k이면

k | V | = 2 | E |

Corollary 4

무 방향 그래프에서 각 꼭지점의 차수가 k 이상이면

k | V | ≤ 2 | E |

| Corollary 5

무 방향 그래프에서 각 꼭지점의 차수가 최대 k이면

k | V | ≥ 2 | E |