내가 공부하기 위한 공간 - [수학] 2 - 그래프와 트리

[그래프]

물리 구조를 타나낼 수 있는 비선형 네트워크

정점과 간선으로 이루어져 있음

 

<용어>

정점 : 고정된 점, 꼭짓점

간선 : 정점을 있는 선

차수 : 정점에 연결된 간선의 수

인접 정점 : 연결된 정점은 서로 인접

경로 : 임의 정점에서 다른 임의 정점까지 인접 정점 순서

경로 길이 : 경로 간선의 수

단순 경로 : 모두 다른 정점으로 이뤄진 경로

사이클 : 첫 정점과 마지막 정점이 같은 경로

진입 차수 : 방향 그래프에서 정점을 머리로하는 간선 수

진출 차수 : 방향 그래프에서 정점을 꼬리로하는 간선 수

방향 그래프 : 간선에 방향이 있는 그래프

무방향 그래프 : 간선에 방향이 없는 그래프

연결 그래프 : 임의 노드에 대해 다른 모든 노드들에 대한 경로가 있음

비연결 그래프 : 하나라도 단절이 있는 그래프

완전 그래프 : 가능한 최대 간선 수를 가진 그래프

부분 그래프 : 어떤 그래프에서 일정 노드나 간선으로 이뤄진 그래프

가중 그래프 : 간선에 가중치가 할당된 그래프

 

 

[트리]

나무처럼 연결된 유한한 데이터인 비선형 계층

노드와 에지로 이뤄짐

트리는 높이를 아래로 확장

모든 노드는 에지로 연결돼야 함

루프가 없어야 함

 

<용어>

노드 : 지점

에지 : 두 노드를 연결하는 선

루트 노드 : 트리 최상위에 위치한 하나의 지정된 노드

레벨 : 루트 레벨을 0이라 하면 높이가 확장될 수록 1씩 늘어남(같은 높이의 노드들은 같은 레벨)

깊이 : 트리의 가장 높은 레벨

부모 노드 : 다음 레벨 노드와의 에지가 있는 노드

형제 노드 : 동일 부모노드를 가진 노드

자식 노드 : 상위 레벨 노드와 에지가 있는 노드

리프 노드 : 자식 노드가 없는 노드

내부 노드 : 리프 노드가 아닌 노드

노드의 크기 : 자신을 포함한 모든 자식 노드의 개수

노드의 차수 : 에지로 연결된 자식 노드의 수

트리의 차수 : 트리의 가장 높은 노드의 차수

 

<이진트리>

각 노드는 최대 2개의 자식을 갖는 트리

왼쪽 자식과 오른쪽 자식을 구별함

 

포화 이진트리 : 모든 레벨에서 노드들이 모두 채워진 이진 트리

완전 이진트리 : 마지막 레벨을 제외하고 노드가 모두 채워진 이진 트리