[개념정리] 그래프 용어, 종류

[YubinShin]

그래프란?

현실 세계의 사물이나 개념 간의 연결 관계를 수학적 모델로 단순화 하여 표현한 것
ex ) 도로망, 가계도(트리), 웹 링크 연결 관계

그래프 용어

무향간선 (Undirected Edge)

• 정점을 연결하는 간선에 방향이 존재하지 않는다.
• 임의의 간선(a, b)에 대해서 (a, b) = (b, a)

유향간선 (Directed Edge)

• 정점을 연결하는 간선에 방향이 존재한다.
• 임의의 간선(a, b)에 대해서 (a, b) != (b, a)
  

인접 (Adjacent)

• 정점 a, b 에 대해서 간선(e)가 존재한다.
• 거쳐가는 거 없이 다이렉트로 선이 있다.
• 정점들의 관점에서 "나는 a 와 인접해~!" | "나는 b 와 인접해~!"

부속 (Incident)

• 점 a, b 에 대해서 간선(e)가 존재한다.
• 간선(e) 의 관점에서 "나는 a, b 에 부속 되어 있어~!"

차수 (Degree)

• 정점에 부속된 간선의 수

in-degree : 유향 간선 그래프에서 정점에 들어 오는 간선의 수
out-degree : 유향 간선 그래프에서 정점에 나가는 간선의 수

다중 간선

• 정점 a, b 에 대해서 간선 e1= e2 = (a, b)

Self-loop

• 정점 a 에 대해 간선 e = (a, a) 가 존재한다.
• "어떤 경로를 중복해서 지나갈 수 없다." 하는 문제에서 자주 나옴.

경로 (Path)

• 정점과 간선이 교대로 구성된 시퀀스를 말함
• 단순 경로(Simple Path) : 정점과 간선이 중복되지 않는 경로

회로 (Cycle)

• 시작 정점과 끝 정점이 같은 경로(Path)를 뜻 함.

연결(Connected)

• 정점 a 에서 정점 b 로의 경로가 존재하면, a 와 b 는 연결(Connected) 되어 있다고 한다.

그래프 종류

무향 그래프

• 무향 간선으로 존재하는 그래프
• 화살표가 없다.

유향 그래프

• 유향 간선으로 존재하는 그래프
• 화살표가 있다.

가중치 그래프(Weighted Graph)

• 가중치(or 비용(Cost))를 가지는 간선으로 이루어진 그래프
• 톨게이트 비용으로 비유할 수 있다.

정규 그래프(Regular Graph)

• 모든 정점이 동일한 차수를 가지는 그래프

완전 그래프(Complete Graph)

그래프를 구현하는 법

자료구조에 그래프를 적절하게 담는 법을 알아야 합니다.

Edge List