logo

TechCodeview

스패닝 트리

이번 포스팅에서는 스패닝 트리와 최소 스패닝 트리에 대해 알아보겠습니다. 하지만 스패닝 트리로 직접 이동하기 전에 먼저 그래프와 해당 유형에 대한 간략한 설명을 살펴보겠습니다.

그래프

그래프는 정점과 정점을 연결하는 간선의 그룹으로 정의할 수 있습니다. 그래프 유형은 다음과 같습니다.

    무방향 그래프:무방향 그래프는 모든 간선이 특정 방향을 가리키지 않는 그래프입니다. 즉, 단방향이 아닙니다. 그들은 양방향입니다. 또한 V 정점 집합과 E 가장자리 집합이 있는 그래프로 정의할 수도 있으며, 각 가장자리는 두 개의 서로 다른 정점을 연결합니다.연결된 그래프:연결 그래프(connected graph)는 한 꼭지점에서 다른 꼭지점까지 경로가 항상 존재하는 그래프입니다. 어느 방향으로든 간선을 따라가면 다른 꼭지점에서 어떤 꼭지점에 도달할 수 있으면 그래프가 연결됩니다.방향성 그래프:유향 그래프는 digraph라고도 합니다. 그래프의 정점이나 노드 사이에 존재하는 모든 간선이 방향을 향하거나 정의된 방향을 갖는 경우 그래프는 유향 그래프(또는 유향 그래프)입니다.

이제 토픽 스패닝 트리로 이동해 보겠습니다.

스패닝 트리란 무엇입니까?

스패닝 트리는 방향이 없는 연결 그래프의 하위 그래프로 정의될 수 있습니다. 여기에는 가능한 최소한의 가장자리 수와 함께 모든 정점이 포함됩니다. 꼭지점이 누락되면 스패닝 트리가 아닙니다. 스패닝 트리는 순환이 없는 그래프의 하위 집합이며 연결을 끊을 수도 없습니다.

스패닝 트리는 (n-1)개의 모서리로 구성됩니다. 여기서 'n'은 정점(또는 노드)의 수입니다. 스패닝 트리의 가장자리에는 가중치가 할당될 수도 있고 할당되지 않을 수도 있습니다. 주어진 그래프 G에서 생성된 모든 가능한 스패닝 트리는 동일한 수의 정점을 갖지만 스패닝 트리의 간선 수는 주어진 그래프의 정점 수에서 1을 뺀 것과 같습니다.

완전한 무방향 그래프는 다음을 가질 수 있습니다. Nn-2 스패닝 트리의 수 N 그래프의 정점 수입니다. 가정해보자. n = 5 , 가능한 최대 스패닝 트리 수는 다음과 같습니다. 55-2= 125.

스패닝 트리의 응용

기본적으로 스패닝 트리는 그래프의 모든 노드를 연결하는 최소 경로를 찾는 데 사용됩니다. 스패닝 트리의 일반적인 응용 프로그램 중 일부는 다음과 같습니다.

  • 클러스터 분석
  • 민간 네트워크 계획
  • 컴퓨터 네트워크 라우팅 프로토콜

이제 예제를 통해 스패닝 트리를 이해해 보겠습니다.

스패닝 트리의 예

그래프가 다음과 같다고 가정합니다.

스패닝 트리

위에서 설명한 것처럼 스패닝 트리에는 그래프와 동일한 수의 정점이 포함되어 있으며 위 그래프의 정점 수는 5입니다. 따라서 스패닝 트리에는 5개의 정점이 포함됩니다. 스패닝 트리의 가장자리는 그래프의 정점 수에서 1을 뺀 것과 같습니다. 따라서 스패닝 트리에는 4개의 가장자리가 있습니다.

위 그래프에서 생성될 수 있는 스패닝 트리 중 일부는 다음과 같습니다.

스패닝 트리

스패닝 트리의 속성

스패닝 트리의 일부 속성은 다음과 같습니다.

  • 연결된 그래프 G에는 두 개 이상의 스패닝 트리가 있을 수 있습니다.
  • 스패닝 트리에는 순환이나 루프가 없습니다.
  • 스패닝 트리는 최소한으로 연결되어 있고, 따라서 트리에서 가장자리 하나를 제거하면 그래프 연결이 끊어집니다.
  • 스패닝 트리는 최대 비순환성, 따라서 트리에 가장자리 하나를 추가하면 루프가 생성됩니다.
  • 최대값이 있을 수 있습니다. Nn-2 완전한 그래프에서 생성할 수 있는 스패닝 트리의 수입니다.
  • 스패닝 트리에는 n-1 여기서 'n'은 노드 수입니다.
  • 그래프가 완전한 그래프인 경우 최대(e-n+1)개의 모서리를 제거하여 스패닝 트리를 구성할 수 있습니다. 여기서 'e'는 모서리 수이고 'n'은 정점 수입니다.

따라서 스패닝 트리는 연결된 그래프 G의 하위 집합이고, 연결되지 않은 그래프에는 스패닝 트리가 없습니다.

최소 스패닝 트리

최소 스패닝 트리는 간선의 가중치 합이 최소가 되는 스패닝 트리로 정의할 수 있습니다. 스패닝 트리의 가중치는 스패닝 트리의 가장자리에 부여된 가중치의 합입니다. 실제 세계에서 이 가중치는 거리, 교통량, 혼잡도 또는 임의의 값으로 간주될 수 있습니다.

최소 스패닝 트리의 예

예제를 통해 최소 스패닝 트리를 이해해 봅시다.

스패닝 트리

위 그래프의 모서리의 합은 16입니다. 이제 위 그래프에서 생성 가능한 스패닝 트리 중 일부는 다음과 같습니다.

스패닝 트리

따라서 주어진 가중치 그래프에 대해 위 스패닝 트리 중에서 선택된 최소 스패닝 트리는 다음과 같습니다.

스패닝 트리

최소 스패닝 트리의 응용

최소 스패닝 트리의 적용은 다음과 같습니다.

  • 최소 스패닝 트리는 물 공급 네트워크, 통신 네트워크 및 전력망을 설계하는 데 사용될 수 있습니다.
  • 지도에서 경로를 찾는 데 사용할 수 있습니다.

최소 스패닝 트리 알고리즘

최소 스패닝 트리는 아래에 주어진 알고리즘을 사용하여 가중치 그래프에서 찾을 수 있습니다.

  • 프림의 알고리즘
  • 크루스칼의 알고리즘

위에 나열된 두 알고리즘에 대한 간략한 설명을 살펴보겠습니다.

프림의 알고리즘 - 빈 스패닝 트리로 시작하는 그리디 알고리즘입니다. 그래프에서 최소 스패닝 트리를 찾는 데 사용됩니다. 이 알고리즘은 간선 가중치의 합이 최소화될 수 있도록 그래프의 모든 꼭지점을 포함하는 간선의 하위 집합을 찾습니다.

사자는 호랑이에 비해

prim의 알고리즘에 대해 자세히 알아보려면 아래 링크를 클릭하세요. https://www.javatpoint.com/prim-algorithm

크루스칼의 알고리즘 - 이 알고리즘은 연결된 가중치 그래프의 최소 스패닝 트리를 찾는 데에도 사용됩니다. 크루스칼의 알고리즘 역시 전역적 최적해에 초점을 맞추는 대신 모든 단계에서 최적해를 찾는 탐욕적 접근방식을 따른다.

prim의 알고리즘에 대해 자세히 알아보려면 아래 링크를 클릭하세요. https://www.javatpoint.com/kruskal-algorithm

이것이 기사의 전부입니다. 이 기사가 귀하에게 도움이 되고 유익한 정보가 되기를 바랍니다. 여기에서는 스패닝 트리와 최소 스패닝 트리의 속성, 예제 및 응용 프로그램에 대해 논의했습니다.