1. 나무와 숲이란 무엇인가?
나무
- 그래프 이론에서는 나무 이다 무방향, 연결 및 비순환 그래프 . 즉, 단 하나의 순환도 포함하지 않는 연결된 그래프를 트리라고 합니다.
- 트리는 계층 구조를 그래픽 형식으로 나타냅니다.
- 트리의 요소를 노드(node)라고 하고 트리의 가장자리를 가지(branch)라고 합니다.
- n개의 정점을 가진 트리에는 (n-1)개의 모서리가 있습니다.
- 나무는 컴퓨터 과학의 데이터 구조에서 가계도만큼 단순한 것에서부터 나무만큼 복잡한 것까지 많은 유용한 응용 프로그램을 제공합니다.
- ㅏ 잎 트리에는 1차 정점이 있거나 자식이 없는 정점을 리프라고 합니다.
예
위의 예에서 모두 정점이 6개 미만인 트리입니다.
숲
그래프 이론에서는 숲 ~이다 방향이 없고 단절된 비순환 그래프 . 즉, 분리된 나무들의 집합을 숲이라고 합니다. 포리스트의 각 구성 요소는 트리입니다.
예
위 그래프는 두 개의 하위 그래프처럼 보이지만 연결이 끊어진 단일 그래프입니다. 위 그래프에는 사이클이 없습니다. 그러므로 숲이다.
2. 나무의 성질
- 최소한 두 개의 꼭지점을 가진 모든 나무에는 최소한 두 개의 잎이 있어야 합니다.
- 나무에는 많은 특성이 있습니다.
T를 n개의 꼭짓점을 가진 그래프라고 하면 다음 명령문은 동일합니다.- T는 나무이다.
- T에는 사이클이 없으며 n-1개의 간선이 있습니다.
- T는 연결되어 있고 (n -1)개의 가장자리를 갖습니다.
- T는 연결된 그래프이고 모든 모서리는 절단 모서리입니다.
- 그래프 T의 두 정점은 정확히 하나의 경로로 연결됩니다.
- T에는 사이클이 없으며 새로운 간선 e에 대해 그래프 T+ e에는 정확히 하나의 사이클이 있습니다.
- 나무의 모든 모서리는 절단 모서리입니다.
- 트리에 하나의 간선을 추가하면 정확히 하나의 주기가 정의됩니다.
- 연결된 모든 그래프에는 스패닝 트리가 포함되어 있습니다.
- 모든 트리에는 2차 꼭지점이 2개 이상 있습니다.
3. 스패닝 트리
ㅏ 스패닝 트리 연결된 그래프에서 G는 G의 모든 정점을 포함하는 G의 하위 그래프 H이며 트리이기도 합니다.
예
다음 그래프 G를 고려하십시오.
위의 그래프 G에서 우리는 다음과 같은 세 개의 스패닝 트리 H를 구현할 수 있습니다.
스패닝 트리를 찾는 방법
다음 두 가지 방법 중 하나를 사용하여 스패닝 트리를 체계적으로 찾을 수 있습니다.
- 절단 방법
- 구축 방법
1. 절단방법
- 그래프 G에서 임의의 사이클을 선택하십시오.
- 사이클의 가장자리 중 하나를 제거합니다.
- 더 이상 사이클이 남지 않을 때까지 이 과정을 반복합니다.
예
- 그래프 G를 생각해 보세요.
- 위 그래프에서 사이클 a-d-c-a를 파괴하는 모서리 ac를 제거하면 다음 그래프가 나타납니다.
- 위 그래프에서 사이클 a-d-c-b-a를 파괴하는 모서리 cb를 제거하면 다음 그래프가 나타납니다.
- 위 그래프에서 사이클 d-e-c-d를 파괴하는 에지 ec를 제거하면 다음과 같은 스패닝 트리를 얻을 수 있습니다.
2. 구축방법
- 그래프 G의 가장자리를 한 번에 하나씩 선택합니다. 그런 식으로 사이클이 생성되지 않습니다.
- 모든 정점이 포함될 때까지 이 과정을 반복합니다.
예
다음 그래프 G를 고려하십시오.
img CSS 정렬
- 가장자리를 선택하세요 ab ,
- 가장자리를 선택하세요 ~의 ,
- 그 후 가장자리를 선택하십시오. 에크 ,
- 다음으로 가장자리를 선택하세요. CB , 마지막으로 다음과 같은 스패닝 트리를 얻습니다.
서킷랭크
스패닝 트리를 얻기 위해 G에서 삭제해야 하는 모서리 수입니다.
스패닝 트리 G = m-(n-1) , 이는 서킷 랭크 G의
Where, m = No. of edges. n = No. of vertices.
예
위 그래프에서 모서리 m = 7, 꼭짓점 n = 5
그러면 서킷랭크는,
G = m - (n - 1) = 7 - (5 - 1) = 3