[그래프] 그래프 7/4

* 특징
 - 객체 사이의 연결관계를 표현하는 자료구조
 - 표현 능력 우수 > 현실세계의 다양한 문제를 효과적으로 모델링 가능
 - 선형구조, 계층구조도 아닌 순환이 존재

* 개념
 - 그래프 = 노드 + 간선 / G = (V(G),E(G)) = (V,E)
  > 노드 : 일반적으로 모델링하려는 스스템을 구성하는 객체
  > 간선 : 객체 사이의 관계를 정의

* 그래프의 종류
 ⓐ 간선의 특성에 따른 그래프의 종류
  1) 무방향 그래프
   - 두 노드를 연결하는 간선 방향이 없는 그래프
    ex)

무방향 그래프 G1
G1의 노드 : V(G1) = {1,2,3,4}
G1의 간선 : E(G1) = {(1,3), (1,2), (2,4), (2,4)}





  2) 방향 그래프 = 다이그래프
   - 두 노드를 연결하는 간선에 방향이 있는 그래프
   - 시스탬 구성에서 객체간 연결관계가 비대칭적이고, 노드사이에 방향성이 있을시 사용
   ex)

방향 그래프 G2
G2의 노드 : V(G2) = {1,2,3,4}
G2의 간선 : E(G2) = {<1,2>, <1,3>, <2,1>, <2,3>, <2,4>, <3,4>}
※ <1,2>의 의미 : 1에서 3으로 방향이 향한다 
                          <1,2>와 <2,1>은 다른의미
※ 간선 <1,2>에서 1은 꼬리(Tail), 0은 머리(Head)라 부른다.



  3) 가중 그래프
   - 노드를 연결하는 간선에 가중치가 할당된 그래프
    > 가중치 : 노드사이의 거리, 이용시 필요한 비용 등의 다양한 속성을 가지고 있다.
   ex)

 ⓑ 구조에 따른 그래프 종류
  1) 완전 그래프
   - 모든 노드가 1:1로 구성되있는 그래프
   - 연결 가능한 최대 간선수를 가진 그래프
   - 간선의 개수
    > 무방향그래프 m = n(n-1)/2     m : 간선의 개수
    > 방향 그래프   m = n(n-1)         n : 노드의 개수
   ex)

  2) 부분 그래프
   - 본래의 그래프의 일부로, 본래의 그래프에서 노드or 간선을제외하여 만든 그래프
   - G의 부분그래프 G' = (V(G'),E(G'))
   ex)

  
  3) 다중 그래프
   - 중복된 간선을 포함하는 그래프
   ex)

다중 그래프 G8









* 그래프 용어 설명
 - 인접 : 두 노드간 간선이 존재하면 두개의 노드는 "인접"했다고 한다.
 - 부속 : 특정 노드에 연결된 간선을 "특정 노드에 부속 되 있다"고 한다.
 - 차수 : 노드에 부속된(연결된) 간선의 개수
            방향 그래프의 경우에는 노드로 들어오는 "진입차수"와 노드에서 나가는 "진출 차수"로 나눠본다.
 - 경로 : 특정 노드 A에서 B까지의 이동 가능한 경로
   ※ 단순경로 : 경로에 한개의 노드가 딱 한번만 나오는 경우
   ex)

 


 ② 노드와 인접한 노드 = { 1, 3, 4 }
 ④ 의 부속 = {(2,4)}
 ① 의 차수 = 2
 ①에서 ④까지의 단순 경로 = 2개
  1>3>2>4  /  1>2>4

  - 루프 : 특정 노드에서 자기 자신으로 돌아오는 경로