갈래는 있어도 고리는 없다
가운데 정점 하나를 여러 바깥 정점과 연결한 별 모양은 트리가 될 수 있다. 두 정점 사이를 잇는 길은 있어야 하지만 돌아서 같은 연결을 우회하는 순환은 없어야 한다.
간선을 제거하면
트리의 간선 하나를 제거하면 그 양쪽 정점 사이의 연결이 끊어진다. 다른 경로가 있었다면 제거 전 그래프에 순환이 있었을 것이기 때문이다.
간선을 추가하면
트리의 서로 다른 두 정점 사이에 새 간선을 하나 추가하면 원래의 유일한 경로와 새 간선이 순환을 만든다. 이 성질은 연결성을 유지하면서 불필요한 간선을 줄이는 문제와 관련된다.
자료 구조와 비교
자료 구조의 트리는 루트와 부모·자식 관계를 정해 다루는 경우가 많다. 그래프 이론의 트리는 처음부터 특정 루트를 가져야 하는 것은 아니다. 루트를 고르는 것과 트리라는 연결 구조는 구별한다.
관련 문서
경로 그래프 / 순환 그래프 / 연결 그래프 / 단순 그래프 / 이진 트리 / 그래프 (자료 구조) / 간선 (그래프 이론)