그래프 이론-예

이 장에서는 이전 장에서 이미 논의한 개념을 보여주는 몇 가지 표준 예제를 다룰 것입니다.

예 1

Find the number of spanning trees in the following graph.

해결책

위 그래프에서 얻은 스패닝 트리의 개수는 3 개입니다.

이 세 가지는 주어진 그래프에 대한 스패닝 트리입니다. 여기서 그래프 I와 II는 서로 동형입니다. 분명히 비 동형 스패닝 트리의 수는 2 개입니다.

예 2

How many simple non-isomorphic graphs are possible with 3 vertices?

해결책

3 개의 꼭지점으로 가능한 4 개의 비 동형 그래프가 있습니다. 아래에 나와 있습니다.

예제 3

Let ‘G’ be a connected planar graph with 20 vertices and the degree of each vertex is 3. Find the number of regions in the graph.

해결책

학위 정리의 합으로,

20 Σ i = 1 deg (Vi) = 2 | E |

20 (3) = 2 | E |

| E | = 30

오일러의 공식에 따르면

| V | + | R | = | E | + 2

20+ | R | = 30 + 2

| R | = 12

따라서 지역 수는 12 개입니다.

예 4

What is the chromatic number of complete graph Kn?

해결책

완전한 그래프에서 인접한 각 정점은 남아있는 (n-1) 정점입니다. 따라서 각 정점에는 새로운 색상이 필요합니다. 따라서, K 색 번호 N = N.

예 5

What is the matching number for the following graph?

해결책

정점 수 = 9

8 개의 정점 만 일치시킬 수 있습니다.

일치하는 숫자는 4입니다.

예제 6

What is the line covering number of for the following graph?

해결책

정점 수 = | V | = n = 7

라인 커버링 번호 = (α 1 ) ≥ [n / 2] = 3

α 1 ≥ 3

3 개의 모서리를 사용하여 모든 정점을 덮을 수 있습니다.

따라서 선을 덮는 숫자는 3입니다.