가지 종류, 간선 종류

(2022-02-10)

연결선 종류


1. 간선 / 연결선 / 가지의 종류                       ☞ 노드가지 참조
   
  ㅇ 연결선의 방향(direction) 여부               ☞ 그래프 종류 (방향 그래프, 무방향 그래프)
     - 방향 간선 (Directed Edge) 
        . 순서가 정해진 두 정점의 쌍
        . 표기 : 방향 있는 두 정점 v,u 사이의 연결선을 < v, u >로 표시
        . 例) 일방통행 도로

     - 무 방향 간선 (Undirected Edge)
        . 순서 없는 두 정점의 쌍
        . 표기 : 방향 없는 두 정점 v,u 사이의 연결선을 ( v, u )로 표시
        . 例) 기차의 철로

  ㅇ 연결선의 가중치(weight) 여부                ☞ 그래프 종류 (가중치 그래프, 비 가중치 그래프)
     - 연결선에 가중치(거리,시간,비용 등)를 부여할 수 있음
        . 例) 도시들 간의 거리, 지점 간의 파이프 용량, 공항 간의 비행 시간(비용),
              사람 간 친밀도 등

     - [참고용어]
        . 경로 (Path) : 어떤 정점에서 시작하여 특정 정점으로 끝나는 순회/방문/여정
        . 경로 표현 : 두 정점 간을 잇는 간선 또는 정점들을 순서대로 나열하게됨 (중간에 비면 안됨)
        . 경로 길이 (Path Length)  :  떨어져 있는 두 정점 사이(경로)의 연결선 가중치들의 합
        . 최단 경로 (Shortest Path)  :  모든 가능한 경로 중 최소 경로 길이를 갖는 경로

그래프 용어
   1. 그래프 용어   2. 노드, 가지   3. 가지 종류   4. 인접   5. 차수   6. 경로   7. 루프  


Copyrightⓒ written by 차재복 (Cha Jae Bok)               기술용어해설 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"