밍의 기록들😉

[그래프] 그래프의 기본 본문

자료구조, 알고리즘/기본다지기

[그래프] 그래프의 기본

민쓰 2018. 9. 8. 19:46

그래프(Graph)

  • 자료구조의 일종
  • 정점(Node, Vertex)
  • 간선(Edge) : 정점간의 관계를 나타냄
  • G = (V,E)로 나타냄

경로(Path)
  • 정점 A에서 B로 가는 경로
  • A-> C -> D -> E -> B
  • A -> B
  • A -> C -> B
  • A -> C -> E -> B

사이클(Cycle)
  • 정점 A에서 다시 A로 돌아오는 경로
  • A-> C -> B -> A
  • A -> C -> E -> B -> A
  • A -> C -> D -> E -> B -> A

단순 경로와 단순 사이클
  • 경로/사이클에서 같은 정점을 두 번 이상 방문하지 않는 경로/사이클
  • 특별한 말이 없으면, 일반적으로 사용하는 경로와 사이클은 단순 경로/사이클을 말함

방향 있는 그래프
  • A -> C와 같이 간선에 방향이 있음
  • A -> C는 있지만, C-> A는 없음

방향 없는 그래프
  • A -C와 같이 간선에 방향이 없음
  • A- C는 A->C와 C->A를 나타냄
  • 양방향 그래프라고도 함

루프(Loop)

  • 간선의 양 끝 점이 같은 경우가 있음
  • A-> A

가중치(Weight)

  • 간선에 가중치가 있는 경우 ex) 이동하는데 필요한 시간, 이동하는데 드는 비용
  • 가중치가 없는 경우에는 1

차수(Degree)
  • 정점과 연결되어 있는 간선의 개수
  • A의 차수는 2
  • C의 차수는 4

그래프에 관한 수학적 지식

  • 간선의 개수는 정점의 제곱보다 작거나 같음 ()
  • 각 정점의 차수의 합은 간선의 개수의 2배와 같음 (차수의 합을 구할 때, 각 간선을 두번씩 셈)



Comments