스패닝 트리
한 가지 간단한 정의는 트리가 순환과 관련이 없는 연결된 그래프라는 것입니다. 여기서 순환은 간선을 반복하지 않고 노드에서 자체로 이동합니다.
연결된 그래프 G에 대한 스패닝 트리는 G의 모든 정점을 포함하는 트리로 정의됩니다.
스패닝 트리는 종종 인터넷 라우팅 알고리즘을 위해 구현됩니다. 인터넷에서 컴퓨터(노드)는 종종 많은 중복 물리적 연결로 연결됩니다.
그래프의 총 스패닝 트리 수입니다. 그래프가 n이 없는 완전한 그래프인 경우 정점의 수, 스패닝 트리의 총 수는 n(n-2)
여기서 n은 그래프의 노드 수로 표시됩니다. 완전한 그래프에서 작업은 Cayley의 공식을 갖는 n개의 노드가 있는 서로 다른 레이블이 지정된 트리를 계산하는 것과 같습니다.
연결성
수학과 컴퓨터 과학에서 연결성은 그래프 이론의 기본 개념 중 하나입니다.
나머지 노드를 분리된 하위 그래프로 분리하기 위해 제거해야 하는 요소(노드 또는 가장자리)의 최소 수를 필요로 합니다.
네트워크 흐름 문제 이론과 밀접한 관련이 있습니다.
이 그래프는 점선이 제거되면 연결이 끊어집니다.
정점 연결. 그래프의 정점 연결은 삭제로 인해 연결이 끊긴 노드의 최소 수입니다.
정점 연결은 때때로 "포인트 연결" 또는 간단히 "연결"로 표시됩니다.
엣지 커넥티비티. 그래프에서 삭제된 모서리의 연결이 끊어지는 최소한도 수로, 선 연결이라고도 합니다.
연결이 끊긴 그래프의 에지 연결은 0이고 그래프 브리지와 연결된 연결된 그래프의 에지 연결은 1입니다.
거리
두 노드 사이의 거리는 가장 낮은 공통 조상으로 계산할 수 있습니다. 다음은 공식입니다.
Dist(d1, d2) = Dist(root, d1) + Dist(root, d2) - 2*Dist(root, lca) 'd1' and 'd2' are the two given keys 'root' is root of given Binary Tree. 'lca' is lowest common ancestor of d1 and d2 Dist(d1, d2) is the distance between d1 and d2.