Undirected 그래프

  • Vertex를 연결하는 edge에 순서가 없는 pair로 표현되는 edge들로 이루어져있다.
  • {v1,v2}를 edge라고 표현한다.
  • 예를 들어 v1,v2,v3,v4,v5,v6,v7,v8,v9의 vertex가 있을 때 {v1,v2},{v3,v5},{v4,v7},{v4,v7}의 edge가 있으면 4개의 edge가 있다고 표현한다.
  • 방향이 없기 때문에 v1에서 v2로 가는 edge, v2에서 v1로 가는 edge모두 있다고 본다.
  • 자기 자신에서 자기 자신으로 가는 edge는 없다.
  • V개의 vertext가 있는 방향이 없는 그래프에서 최대한 많은 edge의 갯수는 조합(combination)으로 구한다.(vC2)
  • 트리와 마찬가지로 그래프의 degree도 자신의 이웃개수를 dgree로 정의한다.

서브 그래프

  • 원본 그래프에서 추출한 edge와 vertex를 이용해 만든 그래프를 서브 그래프라고 한다.
  • 종속 관계기 때문에 서브 그래프에 있는 모든 edge와 vertex는 오리지널 그래프에 존재해야만 한다.

경로

  • vertex의 인접한 시퀀스 두개 사이에서는 반드시 edge가 존재해야 한다.
  • 경로의 길이는 거쳐간 edge의 개수다. 즉, 경로의 길이가 되는것이다.
  • Trivial path : 자기 자신에 머물러 있는 것. 길이가 0인 것.
  • Simple path : 경로상의 처음과 마지막을 제외한 경로에서 중복이 없는 경로.
  • Simple cycle : simple path면서 처음과 끝이 같은 vertex인 경로

Weighted 그래프

  • 엣지의 연결성만 의미하는게 아니라 edge의 value를 부여한 것을 이야기 한다.
  • 예를 들어 서울과 대구의 거리, 대구와 부산의 거리, 부산에서 대구로 가는데 얼마나 걸리는가 등.
  • 여기에 방향이 없므녀 weighted undirected 그래프 라고 한다
  • weight값들은 edge의 옆에다가 작성한다.

경로

  • weighted 그래프에서 경로의 길이는 edge의 weight값으로 표현한다.
  • 경로 길이의 차이

똑같이 A에서 G로 가더라도 A-D-G로 가는 것과 A-C-F-G로 가는 것은 당연히 경로의 길이가 다르다.

  • 최단경로는 많은 vertex를 거치더라도 weight를 최소화 시키면 된다.

트리와의 상관관계

  • 트리도 그래프의 한 종류다.
  • 어떤 그래프가 트리가 되려면 connected상태여야 하고 vertex 경로가 유일해야 한다.
  • 트리에서 엣지의 개수는 노드의 개수보다 한 개 적다.
  • 트리는 사이클이 존재하지 않는다.

Forest

  • 트리의 집합이다.
  • vertex의 개수가 edge개수보다 항상 많다.
  • 트리의 개수 = vertex 개수 - edge 개수
  • forest 에서 한 개의 edge를 제거하면 트리를 한개 더 만들게 된다.

Directed 그래프

  • {v1,v2} 그래프가 있을때 v1에서 v2로 갈 수 있지만 v2에서 v1로 갈수는 없는 방향성이 부여된다.
  • in_degree : 나에게 들어오는 incomming edge 개수를 의미한다
  • out_degree : 나로부터 출발하는 out goining edge 개수를 의미한다.

Source

  • in degree가 0인 vertex를 source vertex라고 한다

Sinks

  • out degree가 0인 vertex를 sinks vertex라고 한다.

Strongly connected

  • 모든 vertex pair간에 방향성이 있는 경로가 존재할때 strongly connected라고 한다.

Weakly connected

  • 방향성을 무시하고 연결만 되어있다면 weakly connected라고 한다.

Weighted directed graphs

DAG; Directed acycle graphs

  • 방향이 있으나 사이클이 존재하지 않는 그래프
  • 순서를 정할때 많이 사용되는 형태다.

표현 방법

Binary-relation list

  • edge의 목록을 나열해놓은 것
  • {(1,2),(1,4),(3,5)...}
  • edge개수만큼 메모리가 필요하다.
  • vertex사이 연결성을 위해서 모든 원소를 검사해야한다.
  • 한개의 vertex에 대한 관계를 찾을때도 모든 원소를 검사해야한다.

Adjacency matrix

  • 메모리를 가장 많이 쓰는 표현법
  • 2차원 배열을 놓고 원소간의 연결관계를 boolean으로 표현한다.
  • 그래서 V^2만큼 사용한다.

Weighted 그래프의 adjacency matrix 예

Adjacency list

  • 일반적인 알고리즘에서 가장 많이 사용하는 그래프 표현법
  • linkedlist형태의 자료구조

Comments