그래프

공집합이 아닌 정점(vertex or node)의 집합 V와 서로 다른 정점의 쌍(vᵢ, vⱼ)을 연결하는 변 또는 연결선(edge)의 집합 E로 구성되는 구조 G

• G = (V, E)
• V = {v₁, v₂, … , vₙ}
• E = {e₁, e₂, … ,eₘ} = {(vᵢ, vⱼ}, … }

용어

그래프 G = (V, E)에서 정점 u, v를 연결한 변 e가 있을 때

• 인접(adjacent) : 정점 u, v의 관계
• 근접(incident) : 변 e와 정점 u, v의 관계
• 루프(loop) : 근접하는 점이 같은 점인 변 e
• 경로(path) : 모든 edge가 존재할 때 정점의 열, v₁, v₂, v₃,…. vₖ → 경로의 길이는 k-1
  • 단순경로 : 같은 연결선 두 번 포함하지 않는 경로
  • 기본경로 : 어떤 정점들도 두 번 만나지 않는 경로
• 사이클(cycle), 순회(circuit) : v₁ = vₖ (k =! 1)이면
  • 단순 사이클 : 같은 연결선 반복하지 않는 사이클
  • 기본 사이클 : 시작점 제외한 어떠한 정점도 반복하여 방문하지 않는 사이
• 길이(length) : 경로 도는 사이클을 구성하는 변의 수
• 무방향 그래프 : 방향 없는 그래프, 특별한 언급 없으면 무방향 그래프
  • 연결 그래프 : 그래프의 모든 정점이 연결되어 있는 그래프
    • 모든 정점 간 경로가 존재
• 방향 그래프 : 방향 있는 그래프, 연결선을 화살표로 표시하여 방향 나타냄
  • ex) a→b : a에서 b는 연결성 있음, b에서 a는 연결성 없음
  • 강한 연결 그래프 : 방향그래프에서만 모든 두 정점 a와 b에 대해서 a → b, b → a 둘이 있는 그래프
  • 약한 연결 그래프 : 방향그래프에서만 모든 정점이 연결이 돼있으면
• 단순 그래프 : 한 쌍의 정점 사이에 연결선 한 개
• 멀티 그래프 : 한쌍의 정점 사이에 연결선 여러