[DataStruct 09.16] 4. 정리 넷째날-그래프!!ㅋㅋ

1. 그래프의 정의
  Graph G=(V,E)
     V(G) : 공집합이 아닌 정점(vertex)들의 유한 집합
     E(G) : 간선(edge)의 집합 집합 (정점의 쌍)

1.1 무방향 그래프 (Undirected Graph)

  (v1,v2)=(v2,v1) : 무순서
1.2 방향성 그래프 (Directed Graph)

  <v1,v2> <v2,v1> :순서
       tail : 첫번째 끝 v2와 두번째 끝 v1은 같지 않기에 다른 그래프이다.
       head : 위와 마찬가지로 시작점은 첫번째는 v1이고 두번째는 v2이기에 시작점이 다르므로 다른 그래프이다

1.3 루프(self loop)
 왼쪽은 무방향성이고 오른쪽은 무방향성의 루프를 나타낸 그림이다.

1.4 다중 그래프(Multi graph)

  간선을 여러 개 가진 그래프

1.5 완전 그래프(complete graph)

  무방향성
     정점의 수 : n
     간선의 수 : n(n-1)/2
  방향성
     전체간선의 수 : n(n-1)
1.6 부분 그래프
    G=(V,E)ㅇ[ 데히야 
      V(S1)은 V(G)가 포함하거나 같고 E(S1)은 E(G)가 포함하거나 같다. 
      뭐 쉽게 말하면 완전 그래프를 분해 해놓은 것을 부분 그래프라고 한다.

1.7 용어
  정점에 대한 용어
  

인접하다(adjacent)	정점에서 간선으로 연결된 다른 정점
부속하다(incident)	정점에 연결된 간선
차수(degree)	정점에 부속되어 있는 간선의 개수       진입차수 : 정점이 머리가 되는 간선의 수       진출차수 : 정점이 꼬리가 되는 간선의 수

경로(path)	임의의 정점으로 부터 다른 정점 까지 이르는 간선들의 집합
단순경로(Simple path)	모든 정점이 다른 경로일 때
경로의 길이 (length of path)	경로 상에 존재하는 간선의 수
사이클 (cycle)	첫 번째 정점과 마지막 정점이 동일한 단순 경로
비순환 그래프(acyclic graph)	어떤 사이클도 포함하지 않는 그래프 루프와 중복된 간선을 허용하지는 않는다.

2. 그래프 표현 방법
  2.1 인접 행렬 (adjacency matrices)
       각 정점들간의 연결을 행렬로 표현한 것
       인접행렬(i,j)에 대해 그래프에서 vi와 vj사이가 1이면 인접, 0이면 인접하지 않은 것 
       n(n-1)개의 간선 표현
       행렬의 문제점
              저장공간의 낭비
  2.2 인접 리스트 (adjacency lists)
       각각의 정점에 대해 인접한 정점들을 연결 리스트로 표현한 것
       장점 : 인접리스트는 연결되어있는 노드만 리스트로 관리하기 때문에 기억장소를 낭비하지 않는다. 
       단점 : 인접 리스트는 하나의 연결을 표시하기 위해 정점의 정보뿐 아니라 링크 정보까지 사용되므로 간선의 수가 많은 
                경우 인접행렬은 사용할 때 보다 기억장소 낭비가 심해질 수 있다.
      인접 다중 리스트(adjacency multilists)