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형태의 자료구조