맨위로가기

그래프 이론 용어

"오늘의AI위키"는 AI 기술로 일관성 있고 체계적인 최신 지식을 제공하는 혁신 플랫폼입니다.
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.

1. 개요

그래프 이론 용어는 그래프와 관련된 다양한 개념과 정의를 설명한다. 그래프는 꼭짓점과 변으로 구성되며, 꼭짓점의 차수는 연결된 변의 수이다. 그래프는 무향 및 유향 그래프로 구분되며, 유향 그래프는 방향성을 갖는 간선을 사용한다. 그래프의 종류로는 완전 그래프, 이분 그래프, 정규 그래프, 트리 등이 있으며, 경로, 순환, 오일러 경로, 해밀턴 경로 등 그래프 내의 연결성과 관련된 용어가 존재한다. 또한 부분 그래프, 유도 부분 그래프, 클릭, 독립 집합과 같은 그래프의 부분 구조를 설명하는 용어와 오일러 지표, 종수와 같은 위상수학적 개념도 포함한다. 그래프의 크기를 나타내는 거리, 이심률, 지름 등의 척도도 정의하며, 가중 그래프는 변에 가중치가 할당된 그래프이다.

더 읽어볼만한 페이지

  • 그래프 이론 - 다이어그램
    다이어그램은 2차원 기하학적 기호를 사용하여 정보를 시각적으로 표현하는 기술로, 과학, 공학, IT, 비즈니스 등 다양한 분야에서 활용되며 정보를 간략하게 나타내고 시각적 사고를 돕는다.
  • 그래프 이론 - 쾨니히스베르크의 다리 문제
    쾨니히스베르크의 다리 문제는 프레겔 강에 놓인 7개의 다리를 한 번씩만 건너 출발점으로 되돌아올 수 있는지 묻는 문제로, 오일러에 의해 그래프 이론적으로 분석되어 해결되었으며 그래프 이론의 탄생에 기여했다.
그래프 이론 용어
그래프 이론 용어
그래프 이론 기본
그래프정점과 간선으로 이루어진 수학적 구조
정점 (꼭짓점)그래프를 구성하는 기본 요소, 노드라고도 함
간선정점 쌍을 연결하는 선, 방향이 있을 수도 있음
인접두 정점이 간선으로 연결된 경우 "인접하다"고 함
차수정점에 연결된 간선의 수
그래프 종류
방향 그래프간선에 방향이 있는 그래프
무방향 그래프간선에 방향이 없는 그래프
완전 그래프그래프 내 모든 정점 쌍이 간선으로 연결된 그래프
이분 그래프정점 집합을 두 개의 분리된 집합으로 나눌 수 있고, 모든 간선이 서로 다른 집합의 정점을 연결하는 그래프
트리사이클이 없는 연결 그래프
연결되지 않은 트리들의 집합
가중 그래프각 간선에 가중치 (비용, 거리 등)가 부여된 그래프
평면 그래프간선의 교차 없이 평면에 그릴 수 있는 그래프
그래프 표현
인접 행렬정점 간의 연결 관계를 행렬로 표현
인접 리스트각 정점에 연결된 정점들을 리스트로 표현
그래프 탐색
깊이 우선 탐색 (DFS)한 분기를 깊게 탐색하는 방법
너비 우선 탐색 (BFS)인접한 정점부터 탐색하는 방법
그래프 알고리즘
최소 신장 트리 (MST)그래프의 모든 정점을 연결하는 최소 가중치 간선들의 트리
최단 경로 알고리즘두 정점 사이의 최단 경로를 찾는 알고리즘 (다익스트라 알고리즘, 벨만-포드 알고리즘, 플로이드-워셜 알고리즘 등)
위상 정렬방향 그래프의 정점을 방향에 거스르지 않도록 나열하는 방법
네트워크 흐름네트워크에서 최대한 많은 양의 흐름을 보내는 방법을 찾는 알고리즘
기타 용어
사이클시작 정점과 끝 정점이 같은 경로
해밀턴 경로그래프의 모든 정점을 정확히 한 번씩 방문하는 경로
오일러 경로그래프의 모든 간선을 정확히 한 번씩 통과하는 경로
클리크그래프에서 모든 정점이 서로 인접한 부분 그래프
독립 집합그래프에서 서로 인접하지 않은 정점들의 집합
색칠 문제그래프의 정점에 색을 칠할 때, 인접한 정점은 서로 다른 색을 사용하도록 하는 문제

2. 그래프의 기본 정의

6개의 꼭짓점 7개의 변을 가지는 그래프. 6번 꼭짓점의 차수는 1이고, 5번 꼭짓점의 차수는 3이다.


'''그래프'''는 '''꼭짓점'''(vertex영어, node영어)과 '''변'''(邊, edge영어, link영어, line영어, 간선)으로 이루어져 있다. 유향 그래프와 구별하기 위하여, "무향 그래프"로 부르기도 한다. 꼭짓점의 '''차수'''(次數, degree영어)는 그 꼭짓점에 연결되어 있는 변의 개수이다.

'''차수'''(degree영어)는 한 꼭짓점에 이어져 있는 변의 수이다. 두 개의 꼭짓점 사이에 변이 존재한다면, 이 두 꼭짓점들이 '''인접'''(adjacent영어)한다고 한다.

유향 그래프에서는 다음과 같은 용어를 사용한다.

  • '''입력 차수'''(入力次數, in-degree영어): 한 꼭짓점으로 들어오는 변의 개수
  • '''출력 차수'''(出力次數, out-degree영어): 한 꼭짓점에서 나가는 변의 개수


변에 가중치가 부여된 그래프를 가중 그래프라고 한다.

2. 1. 무향 그래프



'''그래프'''는 꼭짓점(vertex영어, node영어)과 변(邊, edge영어, link영어, line영어, 간선)으로 이루어져 있다. 유향 그래프와 구별하기 위하여, "무향 그래프"로 부르기도 한다. 꼭짓점의 '''차수'''(次數, degree영어)는 그 꼭짓점에 연결되어 있는 변의 개수이다.

  • '''차수'''(degree영어): 한 꼭짓점에 이어져 있는 변의 수.
  • '''인접'''(adjacent영어): 두 개의 꼭짓점 사이에 변이 존재한다면, 이 두 꼭짓점들이 '''인접'''한다고 한다.

2. 2. 유향 그래프

다음은 유향 그래프에 대한 설명이다.

  • '''입력 차수'''(入力次數, in-degree영어): 한 꼭짓점으로 들어오는 변의 개수이다.
  • '''출력 차수'''(出力次數, out-degree영어): 한 꼭짓점에서 나가는 변의 개수이다.
  • '''흡수 집합''': 유향 그래프 G의 흡수 집합 AG \setminus A의 임의의 정점 v에 대해 A의 정점으로 향하는 간선이 존재하도록 하는 정점 집합이다.
  • '''비순환''': 그래프에 사이클이 없으면 비순환이다. 컴퓨터 과학에서는 유향 사이클이 없는 유향 그래프인 비순환 유향 그래프를 종종 유향 비순환 그래프라고 한다.[2]
  • '''아보레센스'''(arborescence): 루트가 지정된 유향 트리의 동의어이다. 트리를 참조한다.
  • '''호'''(arc영어): 간선을 참조한다.
  • '''화살표'''(arrow영어): 정점의 순서쌍으로, 예를 들어 유향 그래프간선을 의미한다. 화살표 는 tail영어 , head영어 , direction영어 를 갖는다. 는 의 직접 후계자라고 하며, 는 의 직접 선행자라고 한다. 화살표 는 화살표 의 반전 화살표이다.
  • '''반사슬''': 유향 비순환 그래프에서 쌍으로 비교할 수 없는 정점의 부분 집합 이다. 즉, 에서 x \leq y 인 경우, 에서 로 또는 에서 로의 유향 경로가 없다. 부분 순서 집합반사슬 개념에서 영감을 받았다.

2. 3. 가중 그래프

변에 가중치가 부여된 그래프를 가중 그래프라고 한다.

그래프의 가장자리에 가중치가 있는 경우, 가중 지름은 경로를 따라 가장자리 가중치의 합으로 경로 길이를 측정하고, 가중치가 없는 지름은 가장자리 수로 경로 길이를 측정한다.

3. 그래프의 표현

그래프 이론에서 그래프를 표현하는 방법은 여러 가지가 있다.


  • '''인접 행렬''': 그래프의 정점을 기준으로 행과 열을 구성하고, 두 정점이 인접하면 1, 그렇지 않으면 0으로 표시하는 행렬이다.
  • '''인접 리스트''': 각 정점에 연결된 정점들을 리스트 형태로 나타낸다.
  • '''변 목록''': 변을 중심으로 표현하며, 각 변은 끝점이라고 하는 두 정점을 연결한다.

3. 1. 인접 행렬

그래프의 인접 행렬은 그래프의 정점으로 인덱싱된 행과 열을 가진 행렬이며, 정점 와 가 인접할 때 행 와 열 의 셀에 1이 있고, 그렇지 않으면 0이 있다.[4]

3. 2. 인접 리스트

그래프 이론에서 인접 리스트는 각 꼭짓점에 연결된 꼭짓점들을 리스트로 표현하는 방식이다.

4. 그래프의 종류

그래프는 그 형태와 특징에 따라 여러 종류로 나뉜다.


  • 비순환 그래프: 사이클이 없는 그래프이다. 무방향 비순환 그래프는 숲과 같다.[2] 컴퓨터 과학에서는 유향 사이클이 없는 유향 그래프를 유향 비순환 그래프라고 부르기도 한다.[2]
  • 유향 그래프: 간선이 방향성을 가지는 그래프이다.
  • 연결 그래프: 임의의 두 정점 사이에 경로가 존재하는 그래프이다.
  • 혼합 그래프: 방향 간선과 무방향 간선을 모두 포함할 수 있는 그래프이다.
  • 가중 그래프: 간선에 가중치가 할당된 그래프이다. 가중치는 거리, 비용 등 다양한 의미를 가질 수 있다.
  • 단순 그래프: 루프(한 정점에서 출발하여 같은 정점으로 돌아오는 간선)나 다중 간선(같은 두 정점을 잇는 여러 간선)이 없는 그래프이다.
  • 멀티그래프: 다중 간선 및 루프를 허용하는 그래프이다.
  • 하이퍼그래프: 각 간선(이 경우 하이퍼에지라고 함)이 둘 이상의 정점을 연결할 수 있는 그래프이다.

4. 1. 완전 그래프

Complete graph영어는 모든 꼭짓점 쌍 사이에 변이 존재하는 그래프이다.

4. 2. 이분 그래프

그래프 이론에서 이분 그래프는 꼭짓점 집합을 두 개의 서로소 집합으로 나눌 수 있으며, 같은 집합 내의 꼭짓점끼리는 서로 연결되지 않는 그래프를 말한다.

4. 3. 정규 그래프

모든 꼭짓점의 차수가 같은 그래프를 정규 그래프라고 한다.

4. 4. 트리

사이클이 없는 연결 그래프이다.[2] 비순환 무방향 그래프는 숲과 같다.[2]

4. 5. 평면 그래프

평면 그래프는 변들이 서로 교차하지 않도록 평면에 그릴 수 있는 그래프이다.

5. 그래프의 경로와 순환

여기서 그래프는 무향 그래프로 간주한다. 유향 그래프의 경우 이들 용어는 방향을 준수해야 한다.


  • '''경로'''(path|패스영어): 꼭짓점이 중복되지 않는 트레일(trail)이다.
  • '''닫힌 보행'''(closed walk영어): 시작점과 끝점이 같은 보행(walk)이다.
  • '''닫힌 트레일'''(closed trail영어): 시작점과 끝점이 같은 트레일(trail)이다.
  • '''순환'''(cycle|사이클영어): 닫힌 경로(path)이다. 일부 저자들은 닫힌 트레일을 '''회로'''(circuit영어) 또는 '''여행'''(tour|투어영어)이라고도 한다.


보행, 트레일, 경로, 닫힌 보행, 닫힌 트레일, 순환의 관계는 다음 표와 같다.

용어v_0=v_n (시작점과 끝점이 같음)변 중복 허용 여부꼭짓점 중복 허용 여부
보행×××
트레일××
경로×
닫힌 보행××
닫힌 트레일×
순환


5. 1. 보행 (Walk)

'''보행'''(walk|워크영어)은 꼭짓점과 변이 교대로 나타나는 열(sequence)이며, 각 변의 앞과 뒤에 위치한 꼭짓점을 그 변의 양끝점으로 갖는 열이다.[1]

꼭짓점 v_0, v_1, \dots, v_n으로 구성된 보행은 그 성질에 따라서 다음과 같이 분류된다. (꼭짓점이 겹칠 수 없다면, 변 또한 겹칠 수 없다.)

용어v_0=v_n변이 겹칠 수 없음꼭짓점이 겹칠 수 없음
보행×××
트레일××
경로×
닫힌 보행××
닫힌 트레일×
순환


5. 2. 트레일 (Trail)

변이 중복되지 않는 보행을 trail|트레일영어이라고 한다.

5. 3. 경로 (Path)

경로는 꼭짓점이 중복되지 않는 트레일(trail)이다. 이는 변과 꼭짓점이 모두 중복되지 않는 보행(walk)과 같다.

다음은 꼭짓점 v_0, v_1, \dots, v_n으로 구성된 보행의 성질에 따른 분류를 나타낸 표이다.

용어v_0=v_n변이 겹칠 수 없음꼭짓점이 겹칠 수 없음
보행×××
트레일××
경로×
닫힌 보행××
닫힌 트레일×
순환


5. 4. 순환 (Cycle)

닫힌 경로는 순환(cycle|사이클영어)이라고 한다. 일부 저자들은 닫힌 트레일을 회로(circuit영어) 또는 여행(tour|투어영어)이라고도 한다.[1]

즉, 꼭짓점 v_0,v_1,\dots,v_n으로 구성된 보행은 성질에 따라서 다음과 같이 분류된다. (꼭짓점이 겹칠 수 없다면, 물론 변 또한 겹칠 수 없다.)

용어v_0=v_n변이 겹칠 수 없음꼭짓점이 겹칠 수 없음
보행×××
트레일××
경로×
닫힌 보행××
닫힌 트레일×
순환


5. 5. 오일러 경로/회로

오일러 경로(Eulerian trail)는 그래프의 모든 변을 정확히 한 번씩 지나는 트레일(trail, 같은 변을 두 번 지나지 않는 경로)이다. "오일러 경로"라고도 불리지만, 엄밀히 말하면 경로(path, 같은 꼭짓점을 두 번 지나지 않는 경로)는 아닐 수 있다. 즉, 꼭짓점이 중복될 수 있다.

5. 6. 해밀턴 경로/순환

해밀턴 경로(Hamiltonian path영어)는 그래프의 모든 꼭짓점을 정확히 한 번씩 지나는 경로이다. 시작점과 끝점이 같은 해밀턴 경로를 해밀턴 순환(Hamiltonian cycle영어)이라고 한다.[1]

6. 그래프의 연결성

무향 그래프는 세포 복합체로서, 자연스럽게 위상 공간의 구조를 갖는다. 따라서 위상수학적 용어를 적용할 수 있다.


  • '''오일러 지표'''(Euler characteristic영어) 및 '''호몰로지''' 역시 세포 복합체로 여겨 정의할 수 있다. 물론, 이 경우 H_0H_1만이 존재한다. 오일러 지표가 \chi=2-2g라면, g를 '''종수'''(genus영어)라고 한다. 종수가 0인 그래프를 '''평면 그래프'''라고 한다.
  • '''흡수 집합''': 유향 그래프 G의 흡수 집합 AG \setminus A의 임의의 정점 v에 대해 A의 정점으로 향하는 간선이 존재하도록 하는 정점 집합이다.
  • '''절단점'''(cut vertex영어): 연결 그래프에서 제거하면 그래프를 분리하는 정점.
  • '''정점 컷'''(vertex cut영어): 그래프에서 제거하면 그래프연결이 끊어지는 정점의 집합. 하나의 정점 컷은 절단점이라고 한다.

6. 1. 연결 그래프

어떤 그래프에 속한 임의의 두 꼭짓점에 대해 각 꼭짓점을 양 끝점으로 하는 경로가 존재할 경우, 그 그래프를 '''연결된''' 그래프라고 한다. 세포 복합체로 간주하였을 때, 연결 공간인 것이다.[1]

  • '''비연결 그래프'''(disconnected graph영어): 연결되어 있지 않은 그래프[1]
  • '''연결 성분'''((connected) component영어): 어떤 그래프의 연결 속성에 대한 최대 부분 그래프. 이는 세포 복합체로 간주하였을 때, 일반위상수학에서의 연결 성분과 같다.[1]

6. 2. 연결 요소

무향 그래프는 세포 복합체로서, 자연스럽게 위상 공간의 구조를 갖는다. 따라서 위상수학적 용어를 적용할 수 있다.

  • '''연결 성분'''(connected component영어): 어떤 그래프에서 연결 속성에 대한 최대 부분 그래프이다. 이는 세포 복합체로 간주하였을 때, 일반위상수학에서의 연결 성분과 같다.

6. 3. 절단점 (Cut Vertex)

연결 그래프에서 제거하면 그래프의 연결 요소 수를 증가시키는 정점.

6. 4. 절단선 (Bridge)

그래프에서 제거하면 연결 요소의 개수가 증가하는 이다.

7. 그래프의 부분 그래프

부분 그래프(subgraph|서브그래프영어)는 어떤 그래프의 일부분을 이루는 그래프이다.


  • 어떤 그래프의 꼭짓점 집합의 부분집합과 그에 속한 변으로 이루어진 그래프.
  • 어떤 그래프의 변 집합의 부분집합과 그에 속한 꼭짓점으로 이루어진 그래프.[1]


(어떤 속성에 대한) '''최대 부분 그래프'''(maximal subgraph with regard to a property)는 그 부분 그래프가 해당 속성을 유지하면서, 다른 꼭짓점이나 변이 추가되면 그 속성을 유지하지 못하는 부분 그래프를 의미한다.

7. 1. 부분 그래프 (Subgraph)

'''부분 그래프'''(subgraph|서브그래프영어)는 어떤 그래프의 꼭짓점 집합의 부분집합과 그에 속한 변으로 이루어진 그래프, 혹은 어떤 그래프의 변 집합의 부분집합과 그에 속한 꼭짓점으로 이루어진 그래프이다.[1]

7. 2. 유도 부분 그래프 (Induced Subgraph)

주어진 원본 소스에는 "유도 부분 그래프 (Induced Subgraph)"에 대한 직접적인 정의나 설명이 없으므로, 주어진 소스만을 사용하여 해당 섹션의 내용을 작성하는 것은 불가능합니다. 따라서 이전 출력과 동일하게 유지합니다.

7. 3. 클릭 (Clique)

그래프 이론에서 '''클릭'''(clique영어)은 모든 꼭짓점 쌍이 서로 연결된 부분 그래프이다.

7. 4. 독립 집합 (Independent Set)

독립 집합은 주어진 그래프에서 서로 연결되지 않은 정점들의 집합이다. 어떤 두 꼭짓점도 서로 연결되지 않은 부분 그래프를 의미한다. 세 개의 정점으로 이루어진 독립 집합은 반삼각형이라고 불리며, 이는 삼각형의 여집합이다. 그래프 G에서 독립 집합의 크기는 독립수 (alpha영어, 그리스 문자 알파 사용)로 표현된다.[3]

8. 그래프의 위상수학적 성질

무향 그래프는 세포 복합체로서, 자연스럽게 위상 공간의 구조를 갖는다. 따라서 위상수학적 용어를 그래프에 적용할 수 있다.


  • '''연결 그래프'''(connected graph영어): 그래프에 속한 임의의 두 꼭짓점을 잇는 경로가 존재하면, 그 그래프는 '''연결된''' 그래프이다. 즉, 세포 복합체로 간주하면 연결 공간이 된다.
  • '''비연결 그래프'''(disconnected graph영어): 연결되어 있지 않은 그래프이다.
  • '''연결 성분'''((connected) component영어): 어떤 그래프에서 연결 속성을 가지는 최대 부분 그래프이다. 세포 복합체로 간주하면, 일반위상수학에서의 연결 성분과 같다.

8. 1. 오일러 지표

무향 그래프는 세포 복합체로서, 자연스럽게 위상 공간의 구조를 갖는다. 따라서 위상수학적 용어를 적용할 수 있다.

'''오일러 지표'''(Euler characteristic영어) 및 '''호몰로지''' 역시 세포 복합체로 여겨 정의할 수 있다. 물론, 이 경우 H_0H_1만이 존재한다. 오일러 지표가 \chi=2-2g라면, g를 '''종수'''(genus영어)라고 한다. 종수가 0인 그래프를 '''평면 그래프'''라고 한다.

8. 2. 종수 (Genus)

무향 그래프는 세포 복합체로서, 자연스럽게 위상 공간의 구조를 갖는다. 따라서 위상수학적 용어를 적용할 수 있다. 오일러 지표\chi=2-2g라면, g를 '''종수'''(genus영어)라고 한다. 종수가 0인 그래프를 '''평면 그래프'''라고 한다.

9. 그래프의 크기 척도

가중 그래프는 정점이나 변에 무게(가중치)가 할당된 그래프이다. 정점 가중 그래프는 정점에 무게가 있으며, 변 가중 그래프는 변에 무게가 있다.

9. 1. 거리 (Distance)

두 꼭짓점 v_1, v_2 사이의 '''거리'''(distance영어)는 v_1에서 v_2로 가는 경로 중 가장 짧은 경로의 변의 개수이다. 만약 이러한 경로가 없으면 거리는 무한대이다.

9. 2. 이심률 (Eccentricity)

이심률(eccentricity영어)은 한 꼭짓점에서 다른 모든 꼭짓점 사이의 거리들 중 가장 큰 거리이다.[1]

9. 3. 지름 (Diameter)

그래프의 지름(diameter영어)은 그래프 내의 모든 꼭짓점 쌍 사이의 거리 중 가장 큰 값이다. 다시 말해, 그래프의 최대 이심률[1]이 지름이다. 여기서 이심률(eccentricity영어)은 한 꼭짓점에서 다른 모든 꼭짓점 사이의 거리들 중 가장 큰 거리를 뜻한다.[1]

참조

[1] 논문 Concerning the achromatic number of graphs
[2] 서적 Introduction to Algorithms MIT Press and McGraw-Hill
[3] 논문 Acyclic colorings of planar graphs
[4] 문서 Cormen Leiserson Rivest Stein 2001
[5] 서적 Graph Theory Springer-Verlag
[6] 논문 The Binding Number of a Graph and its Anderson Number
[7] 논문 A polynomial-time algorithm to find a linkless embedding of a graph Elsevier BV 2009-03
[8] 논문 Properly colored and rainbow copies of graphs with few cherries
[9] 웹사이트 depth https://xlinux.nist.[...] NIST
[10] 서적 Graph Classes: A Survey https://archive.org/[...] SIAM Monographs on Discrete Mathematics and Applications
[11] 서적 The Many Facets of Graph Theory (Proc. Conf., Western Mich. Univ., Kalamazoo, Mich., 1968) Springer
[12] 웹사이트 level https://xlinux.nist.[...] NIST
[13] 서적 Combinatorics and Graph Theory https://www.springer[...] Springer-Verlag
[14] 간행물 Collective dynamics of 'small-world' networks 1998-06
[15] 서적 Graph theory and applications (Proc. Conf., Western Michigan Univ., Kalamazoo, Mich., 1972; dedicated to the memory of J. W. T. Youngs) Springer
[16] 서적 Graph Theory http://link.springer[...] Springer Berlin Heidelberg 2017
[17] 웹사이트 Chain - graph theory https://www.britanni[...] 2018-03-25
[18] 문서 HTML 파일이 ANSI로 저장되어 깨진 상태이므로, HTML 페이지를 웹페이지, HTML만 옵션으로 다운로드 후 메모장에서 파일 포맷을 UTF-8로 저장해야 내용을 볼 수 있다.



본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.

문의하기 : help@durumis.com