그래프 이론 용어사전

위키백과, 우리 모두의 백과사전.
이동: 둘러보기, 검색

그래프 이론에서 사용하는 많은 용어들에 대해서 정리한다. 그래프 이론은 오랫동안 연구되어 왔고 지금도 활발하게 연구되고 있기 때문에 그래프 이론에서 사용하는 모든 용어를 일목요연하게 완벽히 정리하기는 사실상 불가능하다. 여기에 정리한 내용은 그래프 이론과 관련한 기본적인 내용만을 포함한 것이며, 자세한 내용은 관련 교과서를 참고해야 한다.

기본정의[편집]

6개의 꼭지점과 7개의 변을 가지는 그래프

그래프(graph)는 꼭지점(vertex 혹은 node)과 (邊, edge 혹은 link, line)으로 이루어져 있다. 꼭지점의 차수(次數, degree)는 그 꼭지점에 연결되어 있는 변의 개수이다. 오른쪽의 그래프를 예로 들어서 설명하면, 이 그래프는 6개의 꼭지점을 가지고 있고, 7개의 변을 가지고 있다. '6'번 꼭지점의 차수는 1이고, '5'번 꼭지점의 차수는 3이다.

용어[편집]

  • 부분그래프({{llang|en|subgraph|서브그래프) - 어떤 그래프의 꼭지점 집합의 부분집합과 그에 속한 변으로 이루어진 그래프, 혹은 어떤 그래프의 변 집합의 부분집합과 그에 속한 꼭지점으로 이루어진 그래프
    • (어떤 속성에 대한) 최대 부분그래프(maximal subgraph with regard to a property) - 서브그래프가 그 속성을 유지하고 다른 꼭지점이나 변이 그 서브그래프에 첨가되면 그 속성을 유지하지 못하는 서브그래프
  • 차수(degree) - 무향 그래프에서, 한 꼭지점에 이어져있는 변의 개수
    • 입력차수(內-, in-degree) - 유향 그래프에서, 한 꼭지점으로 들어오는 변의 개수
    • 출력차수(外-, out-degree) - 유향 그래프에서, 한 꼭지점에서 나가는 변의 개수
  • 인접(adjacent) - 두 개의 꼭지점이 변으로 이어져있을 때, 이 꼭지점들은 인접해있다고 한다.
  • 보행(영어: walk 워크[*]) - 꼭지점과 변이 교대로 나타나는 열(sequence)이면서, 각 변의 앞과 뒤에 위치한 꼭지점을 그 변의 양끝점으로 갖는 열
    • 닫힌 보행(closed walk) - 시작점과 도착점이 같은 워크
      • 회로(cycle) - 시작점과 도착점 외에는 어떤 꼭지점도 반복되지 않는 닫힌 워크
      • 투어(tour) - 모든 변이 최소한 한 번씩 반복된 닫힌 워크
  • 트레일(trail) - 변이 중복되지 않는 워크
    • 닫힌 트레일(closed trail) - 시작점과 도착점이 같은 트레일
      • 오일러 트레일(Eulerian trail) - 모든 변이 정확히 한 번씩 포함된 닫힌 트레일. 이름은 오일러 경로에서 유래
  • 경로(path) - 꼭지점이 중복되지 않는 트레일, 혹은 변과 꼭지점이 모두 중복되지 않는 워크
  • 연결그래프(영어: connected graph) - 어떤 그래프에 속한 임의의 두 꼭지점에 대해 각 꼭지점을 양 끝점으로 하는 경로가 존재할 경우, 그 그래프를 연결된 그래프라고 함.
    • 비연결그래프(영어: disconnected graph) - 연결되어 있지 않은 그래프
    • 연결성분(영어: (connected) component) - 어떤 그래프의 연결 속성에 대한 최대 부분그래프
  • 거리(distance) - 시작점과 도착점 사이의 가능한 경로 중 최소의 변 수. 연결되어 있지 않은 두 꼭지점 사이의 거리는 무한대 혹은 정의되어 있지 않음으로 정의
    • 이심(eccentricity) - 한 꼭지점에서 다른 모든 꼭지점 사이의 거리들 중 가장 큰 거리
      • 지름(diameter) - 그래프의 최대 이심


같이 보기[편집]

바깥고리[편집]

  • (한국어) 그래프 이론 용어사전
  • (영어) Wasserman, Stanley and Faust, Katherine. Social Network Analysis. Cambridge University Press. NY:1994.