그래프 용어 정리

그래프 용어 정리

방향 그래프(directed graph): ‘유향 그래프’ 라고도 함 말 그대로 방향이 있다.

무향 그래프(undirected graph): 방향이 없다. 연결만 되어 있으면 어디로든지 갈 수 있다.

가중치 그래프(weighted graph): 각 간선들은 가중치를 갖는다.

다중 그래프(multigraph): 두 정점 간에 간선이 두 개 이상 있는 그래프

단순 그래프(simple graph): 두 정점 사이에 최대 한 개의 간선만 있는 그래프

루트 없는 트리(unrooted tree): 부모 자식 관계만 없을 뿐 연결 관계만 보면 트리와 같음

이분 그래프(bipartite graph): 그래프의 정점들을 겹치지 않는 두 개의 그룹으로 나눠서                                                                      서로 다른 그룹에 속한 정점들 간에만 간선이 존재하는 그래프

(이분 그래프)

사이클 없는 방향 그래프(directed acyclic graph): 줄여서 ‘DAG’라고 부름. 한 점에서 출발해
                                                              다시 자기 자신으로 돌아오는 경우가 없는 그래프를 말한다.

단순 경로(simple path): 경로 중 한 정점을 최대 한 번만 지나는 경로를 단순 경로라고 한다.

희소 그래프(sparse graph): 간선의 수가 |V|2에 비해 적은 그래프

 

밀집 그래프(dense graph): 간선의 수가 |V|2에 비례하는 그래프

의존성 그래프(dependency graph): 어떤 일의 의존 관계를 표현한 그래프