이번 글에서는 그래프(Graph)라는 자료구조를 활용한 정렬 알고리즘 가운데 하나인 Topological sort 기법을 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님과 역시 같은 대학의 김선욱 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

concept

Topogical Sort란 Directed Acyclic Graph(방향을 가지면서 사이클이 없는 그래프)를 활용해 노드들 사이에 선후관계를 중심으로 정렬하는 알고리즘입니다. 이때 사용되는 기법이 깊이우선탐색(DFS)입니다. 옷입기 예시를 보겠습니다. 우선 아래 그래프를 깊이우선탐색으로 모든 노드를 탐색하고, 노드들에 방문시점/방문종료시점을 기록해 둡니다.

이후 방문종료시점의 내림차순으로 정렬합니다.

Topological Sort의 계산복잡성은 깊이우선탐색에 비례합니다. 따라서 $O($|$V$|$+$|$E$|$)$가 됩니다.

DAG 최단거리

Topological Sort와 edge relaxation 기법을 활용해 Directed Acyclic Graph(DAG)의 최단거리를 구할 수 있습니다. 그 과정은 다음과 같습니다.

• 주어진 DAG에 대해 Topological Sort를 수행한다.
• 시작노드를 0, 나머지의 거리를 무한대로 초기화한다.
• 각 노드별 모든 엣지에 대해 edge relaxation을 수행한다.

이번 글에서는 그래프(Graph)라는 자료구조를 순회하는 알고리즘 가운데 깊이우선탐색(Depth First Search) 기법을 살펴보도록 하겠습니다. 파이썬 코드는 이곳을 참고하였습니다. 이 글은 고려대 김황남 교수님과 역시 같은 대학의 김선욱 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

concept

깊이우선탐색이란 더 이상 나아갈 엣지가 없을 때까지 깊이 탐색하는 그래프 순회(traverse) 기법입니다. 깊이우선탐색을 도식화한 그림은 다음과 같습니다.

파이썬 구현

깊이우선탐색을 파이썬으로 구현한 코드는 다음과 같습니다. 알고리즘에서 쓰이는 변수는 다음과 같습니다.

• 그래프 : Graph (각 노드에는 값과 엣지뿐 아니라 방문시간 time, 색상 Color 정보도 들어 있음)
• 시작노드 : startVertex
• 시작노드와 이웃한 노드 : nextVertex
• 색상 : 아직 방문하지 않았다면 white(defalut), 이미 방문했다면 black, 방문 여부를 검토(processing)하고 있다면 gray
• 방문시간 : 최초 방문(discovery)한 시간, 방문을 마친(finish) 시간 두 가지로 나뉨

from pythonds.graphs import Graph
class DFSGraph(Graph):
    def __init__(self):
        super().__init__()
        self.time = 0
	
    def dfs(self):
        # 모든 노드의 색상을 white,
        # 부모노드 정보를 -1로 초기화
        for aVertex in self:
            aVertex.setColor('white')
            aVertex.setPred(-1)
        for aVertex in self:
          	# 임의의 노드가 아직 방문하지 않은(white)
            # 노드라면 해당 노드에 대해 dfsvisit 호출
            # dfsvisit은 더 이상 나아갈 엣지가 없을 때까지 
            # 재귀적으로 수행, 수행 후에도 white인 노드가 있으면
            # 해당 노드를 시작노드로 해서 dfsvisit 반복 수행
            if aVertex.getColor() == 'white':
                self.dfsvisit(aVertex)

    def dfsvisit(self,startVertex):
      	# processing이라는 의미로
        # 시작노드의 색상을 gray로 변경
        startVertex.setColor('gray')
        # 방문시간에 1을 더함
        self.time += 1
        # 시작노드를 발견한 시점을 기록
        startVertex.setDiscovery(self.time)
        # 시작노드에 인접한 모든 이웃노드들에 대해
        for nextVertex in startVertex.getConnections():
            # 해당 노드가 아직 방문하지 않은(white) 노드라면
            if nextVertex.getColor() == 'white':
              	# 해당 노드의 부모를 시작노드라고 기록
                nextVertex.setPred(startVertex)
                # 해당 노드를 시작노드로 해서 dfsvisit 호출
                self.dfsvisit(nextVertex)
        # 이렇게 모든 이웃노드들에 대해 탐색이 끝나면
        # 시작노드 방문을 마쳤다는 의미로 black으로 변경
        startVertex.setColor('black')
        # 방문시간에 1을 더함
        self.time += 1
        # 시작노드 processing을 끝낸 시점을 기록
        startVertex.setFinish(self.time)

순회 예시

(a)와 같은 그래프를 깊이우선탐색 방식으로 순회해보겠습니다. 시작노드 startVertex를 $u$로 두겠습니다. 그러면 우선 시작노드 발견시점을 1로 적어두고, processing하고 있다는 의미로 색상을 gray로 바꿉니다. 이후 dfsvisit 함수가 재귀적으로 세 번 호출되면서 $v$, $y$, $x$ 노드에 대해 같은 작업이 진행돼 전체적으로는 (b), (c), (d) 같은 모습을 띄게 됩니다.

이번엔 (f)를 봅시다. (f)에서는 $x$를 시작노드로 하는 재귀함수 dfsvisit이 수행되고 있습니다. $x$의 이웃노드 가운데 white인 노드가 없어서 더 이상 깊이우선탐색이 불가능합니다. $x$의 processing이 완료되었다는 의미로 색상을 black으로 바꾸고 종료시점(5)을 기록하고 재귀함수 호출을 종료합니다.

(g)를 봅시다. (g)에서는 $y$를 시작노드로 하는 재귀함수 dfsvisit이 수행되고 있습니다. $y$의 이웃노드 가운데 white인 노드가 없어서 더 이상 깊이 우선 탐색이 불가능합니다. $y$의 processing이 완료되었다는 의미로 색상을 black으로 바꾸고 종료시점(6)을 기록하고 재귀함수 호출을 종료합니다.

(h)를 봅시다. (h)에서는 $v$를 시작노드로 하는 재귀함수 dfsvisit이 수행되고 있습니다. $v$의 이웃노드 가운데 white인 노드가 없어서 더 이상 깊이 우선 탐색이 불가능합니다. $v$의 processing이 완료되었다는 의미로 색상을 black으로 바꾸고 종료시점(7)을 기록하고 재귀함수 호출을 종료합니다.

(m)을 봅시다. (m)에서는 $u$를 시작노드로 하는 재귀함수 dfsvisit이 수행되고 있습니다. $u$의 이웃노드 가운데 white인 노드가 없어서 더 이상 깊이 우선 탐색이 불가능합니다. $u$의 processing이 완료되었다는 의미로 색상을 black으로 바꾸고 종료시점(8)을 기록하고 재귀함수 호출을 종료합니다.

이로써 dfs에서의 dfsvisit 재귀함수 호출이 종료됐습니다. 그런데 아직 아래의 반복문은 계속 돌고 있으므로, 나머지 노드 가운데 아직 방문하지 않은(white) 노드가 있다면 해당 노드들에 대해서도 dfsvistit을 수행해 줍니다.

    for aVertex in self:
        if aVertex.getColor() == 'white':
            self.dfsvisit(aVertex)

(m)을 다시 봅시다. $w$를 시작노드로 dfvisit을 수행합니다. $w$ 발견시점을 9로 하고 processing하고 있다는 의미로 색상을 gray로 바꿉니다. 이후 $w$의 이웃노드인 $z$를 시작노드로 dfvisit을 재귀적으로 수행합니다. $z$ 발견시점을 10으로 하고 processing하고 있다는 의미로 색상을 gray로 바꿉니다.

(o)를 봅시다. (o)에서는 $z$를 시작노드로 하는 재귀함수 dfvisit이 수행되고 있습니다. $z$의 이웃노드 가운데 white인 노드가 없어서 더 이상 깊이 우선 탐색이 불가능합니다. $z$의 processing이 완료되었다는 의미로 색상을 black으로 바꾸고 종료시점(11)을 기록하고 재귀함수 호출을 종료합니다.

(p)를 봅시다. (p)에서는 $w$를 시작노드로 하는 재귀함수 dfvisit이 수행되고 있습니다. $w$의 이웃노드 가운데 white인 노드가 없어서 더 이상 깊이 우선 탐색이 불가능합니다. $w$의 processing이 완료되었다는 의미로 색상을 black으로 바꾸고 종료시점(12)을 기록하고 재귀함수 호출을 종료합니다.

(p)까지 수행이 끝나면 그래프 전체에서 white인 노드가 없게 됩니다. 이로써 dfs의 반복문도 종료됩니다.

깊이우선탐색 그래프의 특성

위 예시에서 깊이우선탐색이 종료된 그래프의 모습은 다음과 같습니다.

깊이우선탐색으로 그래프를 순회한 결과로 부모-자식노드가 도출됩니다. 예컨대 위 그림에서는 $u$와 $v$, $w$와 $b$가 그러한 관계를 갖습니다. 부모에서 자식노드로 향하는 엣지를 Tree edge/Discover edge라고 합니다. 반대로 자식에서 부모노드로 향하는 엣지를 Back edge라고 합니다. 위 그림 기준으로는 음영표시된 엣지가 tree edge, B라고 표시된 엣지가 back edge입니다. 무방향그래프(undirected graph)에서는 Tree edge와 Back edge만 존재합니다.

Tree edge가 아닌 엣지 가운데 자손노드로 향하는 노드를 Forward edge라고 합니다. Cross edge는 이 세 가지 경우를 제외한 모든 종류의 엣지를 나타냅니다. 위 그림 기준으로는 F가 forward edge, B가 back edge입니다. back edge가 존재한다는 말은 사이클(cycle)이 존재한다는 말과 같습니다.

위 여섯개 노드를 발견시점과 탐색종료시점 순으로 나열하면 다음과 같습니다. 자식노드의 발견시점과 탐색종료시점은 부모노드의 부분집합이 됩니다. 이같은 구조를 parenthesis structure라고 합니다.

뿐만 아니라 어떤 임의의 노드가 있고, 이 경로상에 존재하는 white 노드들은 깊이우선탐색 기준 해당 노드의 자식노드가 됩니다. 이를 white path theorem이라고 합니다.

깊이우선탐색의 계산복잡성

깊이우선탐색은 모든 노드와 엣지에 대해 한번씩은 탐색하게 되므로 전체적인 계산복잡성은 $O($|$V$|$+$|$E$|$)$가 됩니다.

이번 글에서는 그래프(Graph)라는 자료구조를 순회하는 알고리즘 가운데 너비우선탐색(Breath First Search) 기법을 살펴보도록 하겠습니다. 파이썬 코드는 이곳을 참고하였습니다. 이 글은 고려대 김황남 교수님과 역시 같은 대학의 김선욱 교수님 강의와 위키피디아를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

concepts

그래프 순회(traverse)란 그래프 내 모든 노드를 한번씩 모두 방문하는 걸 말합니다. 너비우선탐색이란 시작 노드를 방문한 후 시작 노드에 인접한 모든 노드를 우선 방문하는 그래프 순회 기법입니다. 더 이상 방문할 인접 노드가 없을 경우 그 다음 가까운 인접노드를 우선 방문합니다. 이 때 쓰는 자료구조가 바로 큐(queue)입니다. 너비우선탐색을 도식화한 그림은 다음과 같습니다.

파이썬 코드

너비우선탐색을 파이썬으로 구현한 코드는 다음과 같습니다. 알고리즘에서 쓰이는 변수는 다음과 같습니다.

• 그래프 : g (각 노드에는 값과 엣지뿐 아니라 거리 Distance, 색상 Color 정보도 들어 있음)
• 시작노드 : start
• 현재 분석 대상 노드 : currentVert
• currentVert와 이웃한 노드 : nbr
• 너비우선탐색을 위한 큐 자료구조 : vertQueue
• 색상 : 아직 방문하지 않았다면 white(defalut), 이미 방문했다면 black, 방문 여부를 검토하고 있다면 gray

알고리즘은 다음과 같이 동작합니다.

from pythonds.graphs import Graph, Vertex
from pythonds.basic import Queue

# g와 s를 입력으로 받습니다
def bfs(g,start):
  # 시작노드의 거리를 0으로 초기화
  start.setDistance(0)
  # 시작노드의 부모는 None으로 초기화
  start.setPred(None)
  # vertQueue 선언
  vertQueue = Queue()
  # 시작노드 enqueue
  vertQueue.enqueue(start)
  # vertQueue 원소가 하나도 없을 때까지 반복
  while (vertQueue.size() > 0):
    # 큐에서 원소를 꺼내 currentVert에 저장
    # 처음 시작할 경우 시작노드가 이것이 됨
    currentVert = vertQueue.dequeue()
    # currentVert에 인접한 노드(nbr)들을 하나씩 분석
    for nbr in currentVert.getConnections():
      # nbr이 아직 방문 안한 노드라면
      if (nbr.getColor() == 'white'):
        # 일단 분석 중이라는 의미로 gray로 색칠
        nbr.setColor('gray')
        # nbr의 거리, 부모 정보 업데이트
        nbr.setDistance(currentVert.getDistance() + 1)
        nbr.setPred(currentVert)
        # nbr를 enqueue
        vertQueue.enqueue(nbr)
    # currentVert의 모든 이웃 분석이 끝나면
    # currentVert를 이미 방문했다는 의미로 black으로 색칠
    currentVert.setColor('black')

순회 예시1

하단 좌측 그림과 같은 그래프 g를 너비우선탐색 방식으로 순회해보겠습니다. 시작노드 start는 1이라고 두겠습니다. 우선 시작노드의 거리를 0으로 초기화한 뒤 시작노드를 큐에 집어 넣습니다. 하단 우측그림과 같습니다.

dequque를 합니다. 1이 나옵니다. 1(currentVert)의 이웃노드들(3, 6)을 차례대로 돌면서 그 색상을 gray로 색칠해 두고, 거리와 부모 정보를 업데이트 한 뒤 큐에 집어 넣습니다. 이렇게 이웃노드들을 모두 돌면 1의 색상을 black으로 색칠해 둡니다. 이렇게 한 결과가 하단 좌측 그림입니다.

dequque를 합니다. 이번엔 3이 나옵니다. 3의 이웃노드들(1, 2, 4, 5)을 차례로 돌면서 그 색상을 gray로 색칠해 두고, 거리와 부모 정보를 업데이트 한 뒤 큐에 집어 넣습니다. 그런데 1은 white가 아니므로 이러한 처리에서 제외합니다. 어쨌든 이렇게 이웃노드들을 모두 돌면 3의 색상을 black으로 색칠해 둡니다. 이렇게 한 결과가 하단 우측 그림입니다.

한편 아래 그림에서 $d=1,2,2,2$라는 얘기는 시작노드와 노드6 사이의 거리가 1, 노드2, 노드4, 노드5와는 각각 2라는 뜻입니다.

dequeue를 합니다. 이번엔 6이 나옵니다. 6의 이웃노드들(1, 5)을 차례로 돌면서 같은 방식으로 처리하려고 했더니 1, 5 모두 white가 아닌 것을 알 수 있습니다. 처리할 것이 없으므로 6의 색상을 black으로 칠해둡니다. 이렇게 한 결과가 하단 우측 그림입니다.

그런데 여기에서 6과 5 사이의 엣지가 사라진 것이 의아할 수 있습니다. 조금 이따가 너비우선트리(Breadth-first-tree)를 설명하려고 이렇게 그림을 그린 것입니다. 그래프 구조가 바뀐 것은 아니니 신경 안쓰고 넘어가셔도 됩니다.

dequeue를 합니다. 이번엔 2가 나옵니다. 2의 이웃노드들(3)을 차례로 돌면서 같은 방식으로 처리하려고 했더니 3이 white가 아닌 것을 알 수 있습니다. 처리할 것이 없으므로 2의 색상을 black으로 칠해둡니다. 이렇게 한 결과가 하단 좌측 그림입니다. 마찬가지로 4와 5에 대해서도 수행하면 너비우선탐색이 종료됩니다.

시작노드 중심으로 너비우선탐색으로 부모-자식 관계를 만들어 나타낸 그래프를 너비우선트리(Breath First Tree)라고 합니다. 다음과 같습니다.

순회예시2

또다른 예시입니다. 다음과 같습니다.

계산복잡성

변수초기화 부분은 $O(1)$이므로 whle 반복문이 전체 계산량을 좌우합니다. 큐에 한번 넣었다가 큐에서 빼는 걸 모든 노드에 대해 수행하므로 $O($|$V$|$)$의 계산복잡성이 소요됩니다. 그런데 currentVert의 모든 인접노드에 대해 색상, 거리, 부모 정보를 업데이트하고, 이는 곧 그래프의 모든 엣지를 스캔한다는 의미이므로 for 반목문 안의 계산복잡성은 $O($|$E$|$)$가 됩니다. 따라서 전체적인 계산복잡성은 $O($|$V$|$+$|$E$|$)$가 됩니다.

이번 글에서는 그래프(Graph)라는 자료구조의 정의와 관련 용어들에 대해 살펴보도록 하겠습니다. 이 글은 고려대 김황남 교수님과 역시 같은 대학의 김선욱 교수님 강의와 위키피디아를 참고했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

graph

그래프란 일련의 노드(node, vertex, 정점, 꼭지점) 집합 $V$와 엣지(edge, 간선, 변) 집합 $E$로 구성된 자료구조의 일종입니다. 일반적으로 노드엔 데이터, 엣지엔 노드와 노드 사이의 관계 정보가 포함되어 있습니다. 이를 그림으로 나타내면 다음과 같습니다.

sparse/dense graph

sparse graph란 하단 좌측 그림처럼 노드의 수보다 엣지 수가 적은 그래프를 가리킵니다. 반대로 dense graph란 하단 우측 그림처럼 노드 수보다 엣지 수가 큰 그래프입니다.

incident/adjacent

임의의 두 노드가 하나의 엣지로 연결돼 있을 경우, 이 노드들은 서로 인접(adjacent)해 있다고 합니다. 같은 경우에 이 엣지는 두 노드에 부속(incident)한다고 합니다.

degree

한 노드의 차수(degree)란 해당 노드에 연결된 엣지의 수(혹은 엣지 가중치의 합)를 가리킵니다.

loop/isolated

다음 그림과 같이 한 엣지가 같은 노드에 부속해 있을 때 loop이라고 합니다.

이와 반대로 임의의 한 노드에 부속해 있는 엣지가 전혀 없을 때 해당 노드를 isolated vertex라고 합니다.

isomorphic

한 그래프의 두 노드를 연결하는 엣지가 하나이고, 다른 그래프에서 그에 대응하는 노드를 연결하는 엣지가 하나뿐일 때 두 그래프는 동형(同型, isomorphic)이라고 합니다. 쉽게 말해 두 그래프는 생김새만 다르게 생길 뿐 본질적으로는 구조가 같다는 이야기입니다. 다음 그림과 같습니다.

subgraph

임의의 그래프 $G=(V,E)$가 주어졌을 때 다음을 만족하는 $G’=(V’,E’)$는 $G$의 부분그래프(subgraph)라고 합니다.

• $E’$는 $V’$에만 부속(=$V’$에 속한 모든 엣지가 $G’$에 있어야 함)되어 있으며 $E$의 부분집합이다.
• $V’$는 $V$의 부분집합이다.

이 가운데 $V=V’$를 만족하는 부분그래프를 spanning subgraph라고 합니다. 쉽게 말해 원 그래프와 노드는 같고 일부 엣지만 포함된 부분그래프를 가리킵니다. 이 부분그래프가 트리을 만족할 경우 spanning tree라고 합니다. 하단 좌측과 우측의 그림이 원 그래프와 spanning subgraph를 예로 든 것입니다.

원 그래프를 spanning subgraph로 표현하면 노드 간 불필요한 관계 정보 처리를 생략할 수 있게 돼 효율성을 도모할 수 있다고 합니다.

complete graph/multigraph

모든 노드들이 엣지로 연결돼 있어, 엣지의 수가 최대인 그래프(하단 좌측)를 완전그래프(complete graph)라고 합니다. 노드 수가 4개라면 기호로 $K_4$라고 표시합니다. 반면 노드 사이를 잇는 엣지가 하나 이상일 경우 해당 엣지를 transitive하다고 하며, 이 그래프를 multigraph라고 합니다(하단 우측).

모든 노드들이 엣지로 연결된 부분그래프를 클리크(clique)라고 합니다. 아래 예시의 경우 클리크는 다음 여섯가지입니다.

• $a,b$
• $a,c,d$
• $b,g$
• $c,d,e,f$
• $c,f,h$
• $f,g$

이 가운데 노드의 수가 가장 많은 클리크($c,d,e,f$)를 maximum clique라고 합니다.

directed graph

방향그래프(directed graph, digraph)란 엣지가 순서가 있는 쌍으로 표현된 그래프의 일종입니다. 다시 말해 엣지가 방향성을 가집니다. 아래 그림처럼 $V_2$에서 $V_1$으로 향하는 엣지 $e_1$가 있다면, $V_2$를 predecessor/source, $V_1$을 successor/sink라고 부릅니다. 이 때 $e_1$을 $V_2$의 outgoing edge, $V_1$의 incoming edge라고 합니다.

방향그래프에서 한 노드의 차수(degree)는 incoming degree와 outgoing degree로 나뉩니다. 다시 말해 어떤 한 노드를 기준으로 들어오는 엣지 수(혹은 가중치의 합), 나가는 엣지 수(혹은 가중치의 합)이 바로 그것입니다. 아래 방향그래프에서 $V_1$의 incoming degree는 $e_1$, outgoing degree는 $e_2$, $e_3$가 됩니다.

$V_1$에서 $V_2$, $V_2$에서 $V_3$으로 각각 outgoing edge가 존재한다면, $V_1,V_2,V_3$를 체인(chain)이라고 합니다.

weighted graph

가중치그래프(weighted graph)란 엣지에 가중치 내지 우선순위 정보가 추가된 형태의 그래프입니다. 이 때 함수 $g$는 엣지를 가중치로 매핑하는 역할을 합니다.

물론 방향그래프 또한 가중치를 가질 수 있습니다. 이글 방향가중치그래프(directed weighted graph)라고 합니다.

path

그래프에서 경로(path)란 인접한 노드들로 구성된 시퀀스(1개 이상)를 가리킵니다. 엣지가 겹치지 않는 경로를 simple하다고 하고, 노드가 겹치지 않는 경로를 elementary하다고 합니다. 경로의 길이(length)는 경로 내 존재하는 엣지의 수를 나타냅니다. 다음과 같은 그래프의 노드 시퀀스가 있다고 칩시다.

• $[v_1, v_2, v_3, v_4, v_5, v_3, v_4, v_5]$
• $[v_1, v_2, v_3, v_4, v_5, v_8, v_6, v_4, v_7]$

위 예시에서 첫번째 노드 시퀀스는 인접한 노드들로 구성돼 있기 때문에 경로라고 할 수 있습니다. 그러나 엣지도, 노드도 겹치기 때문에 simple하지도, elementary하지도 않습니다.

두번째 노드 시퀀스는 인접한 노드들로 구성돼 있기 때문에 경로라고 할 수 있습니다. 엣지가 겹치지 않기 때문에 simple하다고 말할 수 있습니다. 하지만 노드가 겹치기 때문에 elementary하지는 않습니다.

cycle

사이클(cycle)이란 한 노드에서 시작해 해당 노드에서 끝나는 경로를 가리킵니다. 사이클(cycle) 또한 엣지가 겹치지 않는 경우 simple하다고 하고, 노드가 겹치지 않을 경우 elementary하다고 합니다. 위 그래프를 기준으로 아래의 두 개 노드 시퀀스를 보겠습니다.

• $[v_1, v_2, v_3, v_4, v_5, v_8, v_6, v_5, v_9, v_1]$
• $[v_1, v_2, v_3, v_4, v_5, v_9, v_1]$

첫번째 노드 시퀀스는 인접한 노드들로 구성돼 있고 $v_1$으로 시작해 $v_1$으로 끝났으므로 사이클입니다. 엣지가 겹치지 않기 때문에 simple하다고 말할 수 있습니다. 하지만 노드가 겹치기 때문에 elementary하지는 않습니다.

두번째 노드 시퀀스는 인접한 노드들로 구성돼 있고 $v_1$으로 시작해 $v_1$으로 끝났으므로 사이클입니다. 엣지도, 노드도 겹치지 않기 때문에 각각 simple하고, elementary하다고 말할 수 있습니다.

만약 $n$개의 노드가 사이클을 이루고 있을 경우 이를 기호로 $C_n$이라고 표시합니다. 다음 그림과 같이 사이클이 없는 그래프를 acyclic하다고 합니다.

connected

임의의 두 노드가 연결되었다(connected)는 것은 두 노드 사이에 경로가 존재한다는 이야기입니다. 이와 관련해 다음과 같이 정의됩니다.

• 모든 노드쌍 사이에 경로가 존재하는 무방향그래프는 연결되었다고 말한다.
• 임의의 방향그래프에서 방향을 무시하고 보면 연결되어 있을 경우, 해당 방향 그래프는 연결되었다고 말한다.
• 방향그래프의 임의의 노드쌍 $a$, $b$에 대해 $a$에서 $b$로 가는 경로, $b$에서 $a$로 가는 경로가 존재한다면, 해당 방향그래프는 강연결(strongly connected)되었다고 말한다.

아래 방향그래프에서 방향을 무시하고 보면 이 그래프 내 임의의 노드쌍 사이에 모두 경로가 존재함을 알 수 있습니다. 따라서 아래 방향그래프는 connected graph입니다. 하지만 $v_1$에서 $v_3$로 가는 경로는 존재($v_1, v_2, v_3, v_9, v_3$)하나, 반대로 $v_3$에서 $v_1$으로 가는 경로는 존재하지 않는다는 점에서 strongly conntected graph는 아닙니다.

connected component

원 그래프 $G$에서 노드와 엣지가 서로 겹치지 않는(independent) 부그래프를 $G$의 요소(component)라고 합니다. 이들 요소 가운데 요소 내 모든 노드쌍에 대해 경로가 존재하는 부그래프 $S$를 $G$의 연결요소(connected component)라고 합니다. 그 정의상 연결그래프(connected graph)는 하나의 연결요소만을 가집니다.

원 그래프의 부분그래프들 사이에 겹치는 요소가 없고, 부분그래프의 합집합이 원 그래프를 이룰 때 이들 부분그래프를 파티션(partition)이라고 합니다. 아래 그림에서 15개 노드와 모든 엣지를 $G$로 본다면 $G$의 연결요소는 두 개이며, 이 연결요소는 $G$의 파티션입니다.

연결요소 가운데 노드 수가 가장 많은 연결요소를 최대연결요소(maximal connected component)라고 합니다.

Vertex/edge-cut

원그래프에서 어떤 노드를 제거해 부분그래프로 나누는 것을 vertex-cut이라고 합니다. 엣지를 제거해 부분그래프로 나누는 과정을 edge-cut이라고 합니다. 아래 예시에서 노드 $e$를 제거하면 vetex-cut, 노드 $e$와 노드 $x$를 잇는 엣지를 제거하면 원그래프가 두 개 부분그래프로 분리되면서 각각 vetex-cut, edge-cut이 됩니다.

가중치무방향그래프에서 제거 대상 엣지의 가중치가 최대가 되도록 하는 edge-cut 기법을 MaxCut, 최소로 하는 기법을 MinCut이라고 합니다.

Join

새로운 노드 $X$가 추가돼 기존 그래프 $V$의 모든 노드와 연결될 경우 조인(Join)이라고 합니다. 이때 기호로는 $V+X$라고 표기합니다.

edge complement

다음과 같은 관계를 지니는 두 그래프를 edge complement라고 합니다. 노드는 서로 같고 엣지 존재 양상이 정반대인 경우에 해당합니다.

releative complement

아래 그림과 같이 $H$는 $G$의 부그래프이고, $H$에 속한 모든 엣지를 제거한 그래프를 relative complement라고 합니다. 기호로는 $G-H$라고 씁니다.

graph representation

그래프를 컴퓨터가 처리하게 만드려면, 그래프를 적절한 자료구조로 변환해 주어야 합니다. 크게 두 가지 방식이 있는데요. 인접행렬(adjacency matrix)과 인접리스트(adjacency list)입니다. 각각 행렬과 연결리스트(linked list)로 구현합니다.

가중치가 없는 방향그래프를 인접행렬로 표현하는 방식을 도식화한 그림은 다음과 같습니다.

가중치가 없는 방향그래프를 인접리스트로 표현하는 방식을 도식화한 그림은 다음과 같습니다.

가중치가 있는 무방향그래프를 인접행렬로 표현하는 방식을 도식화한 그림은 다음과 같습니다. $∞$는 두 노드 사이에 엣지가 있고 가중치가 0인 경우와 대비하기 위해 만든 표지입니다.

가중치가 있는 무방향그래프를 인접리스트로 표현하는 방식을 도식화한 그림은 다음과 같습니다.

시간복잡성

우선 전체 노드 수가 $V$개, 엣지 수가 $E$개일 때 시간복잡성을 따져보겠습니다. 분석 대상 연산은 (1) 임의의 두 노드($i, j$)가 주어졌을 때 인접해 있는지 여부(operation 1) (2) 임의의 한 노드($i$)가 주어졌을 때 인접해 있는 모든 노드를 찾기(operation 2) 등 두 가지입니다.

먼저 인접행렬의 경우입니다.

• operation 1 : 인접행렬에서 $i$행, $j$열을 참조하면 됩니다. 행렬의 한 원소를 액세스하는 데엔 $O(1)$의 시간복잡성이 듭니다.
• operation 2 : 인접행렬에서 $i$행 전체에 대해 조사하면 됩니다. 노드 전체를 따져봐야 하므로 $O($|$V$|$)$만큼의 시간복잡성이 듭니다.

인접리스트의 경우입니다.

• operation 1 : 인접리스트(연결리스트)에서 $i$번째 버킷에 속한 요소 가운데 $j$가 있는지 탐색(search)하려면 우선 전체 버킷 가운데 $i$번째 버킷을 찾은 뒤 이 버켓 내에 $j$가 있는지 따져야 합니다. $i$번째 노드의 차수를 $d$라고 할 때 $O(d)$의 시간복잡성이 듭니다. 참고로 전체 노드의 평균 차수는 |$E$|/|$V$|입니다.
• operation 2 : 인접리스트에서 $i$번째 버킷에 속한 모든 요소를 순회(traverse)하면서 출력합니다. 따라서 operation 1과 본질적으로 다르지 않습니다. $O(d)$만큼의 시간복잡성이 듭니다.

공간복잡성

이번엔 두 연산의 공간복잡성을 따져보겠습니다. 먼저 인접행렬의 경우입니다.

• operation 1 : 노드 수 × 노드 수만큼의 행렬이 필요합니다. 따라서 $O($|$V$|$^2)$만큼의 공간복잡성이 듭니다.
• operation 2 : 버킷은 전체 노드 수만큼 필요합니다. 각 노드를 잇는 포인터는 전체 엣지의 수만큼(무방향그래프의 경우 전체 엣지의 두 배) 필요합니다. 따라서 $O($|$V$|$+$|$E$|$)$만큼의 공간복잡성이 듭니다.

자료구조의 선택

‘노드와 엣지가 어떻게 구성되어 있는가’가 인접행렬 혹은 인접리스트를 택하는 데 중요한 요인이 됩니다. 예컨대 노드 수보다 엣지 수가 많은 dense graph의 경우 인접행렬을 쓰는 것이 좋습니다. 반대로 노드 수보다 엣지 수가 적은 sparse graph의 경우 인접리스트를 쓰는 것이 좋습니다.

이번 글에서는 양태(modality) 개념과 한국어에서 양태가 문법적으로 어떻게 실현되고 있는지 살펴보겠습니다. 이번 글 역시 고려대 정연주 선생님 강의를 정리했음을 먼저 밝힙니다. 그럼 시작하겠습니다.

개념

양태란 절이나 문장이 나타내는 명제 혹은 사태에 대한 주관적 태도, 판단을 나타내는 의미 범주입니다. 예컨대 다음 문장과 같습니다. 양태는 단일 어미로 실현될 수도, 어미 등 여러 형태소가 함께 쓰여(우언적 구성) 실현될 수도, 부사/용언 등 단일 어휘로도 실현될 수도 있습니다.

• 한라산 설경이 아름다워.
• 비교적 확실한 추측 : 한라산 설경이 아름답겠다, 한라산 설경이 아름다울 것이 확실하다
• 가능성 : 한라산 설경이 아름다울 수(도) 있다. 아마도 한라산 설경이 아름다울 거야

양태가 화자의 주관적 태도/판단을 나타내는 의미 범주라면 서법(mood)은 문법 범주라고 할 수 있겠습니다. 즉 양태적 의미가 어미 등 문법적 장치를 통해 나타내면 서법이라고 할 수 있습니다. 따라서 위 예문의 경우 -겠-, -을 수 있- 같은 구성이 서법, 추측 혹은 가능성에 해당하는 의미가 양태입니다. 확실하다, 아마도와 같이 양태 의미를 드러내는 어휘를 양태어휘라고 부르기도 합니다.

유형

양태에는 크게 인식양태, 당위양태, 동적양태, 감정양태 등 네 가지로 하위 유형이 있습니다. 차례대로 살펴보겠습니다.

인식양태

인식양태(epstemic modality)란 명제의 확실성에 대한 화자의 판단, 믿음의 정도를 나타냅니다. 문장에 표현된 명제가 확실하게 참이라든지(확실성), 확실하지는 않지만 참일 확률이 제법 높다든지(추측), 거짓일 확률보다는 참일 확률이 높다든지(개연성), 참일 확률이 0보다는 높다든지(가능성) 등을 나타냅니다. 인식양태 각각의 종류에 해당하는 한국어 문법 요소와 그 예시는 다음 표와 같습니다.

당위양태

당위양태(deontic modality)란 사태의 바람직함에 대한 화자의 판단을 나타냅니다. 의무, 허락/허용 등이 있습니다.

• 의무(-어야 하-) : 이제 집에 가야 한다.
• 허락(-어도 되-) : 이제 집에 가도 된다.

동적양태

동적양태(dynamic modality)란 사태의 발생 가능성을 좌우하는 원인이 사태 내부의 참여자에게 있음을 나타냅니다. 능력, 의도, 바람 등이 있습니다.

• 능력(-을 수 있-) : 진이는 수영을 할 수 있다.
• 능력(-을 줄 알-) : 진이는 수영을 할 줄 안다.
• 의도(-겠-) : 나는 꼭 1등을 하겠어.
• 의도(-을 것이-) : 나는 꼭 1등을 할 것이다.

감정양태

감정양태(emotive modality)란 명제에 대한 화자의 감정적 태도를 나타냅니다. 놀라움, 유감스러움, 아쉬움, 후회, 다행으로 여김, 두려움, 경계심 등이 있습니다.

• 경계심/경고(-을라) : 조심해. 다칠라.
• 후회(-을걸) : 조금만 더 일찍 일어날걸.

한국어에서는 다양한 조사와 어미로 다양한 감정을 표시할 수 있습니다. 다음 예문과 같습니다.

• 손자 녀석이 축구는 자기가 반에서 제일 {잘한대/잘한다나}.
• 공부도 좀 쉬어 가며 {해라/하렴/하려무나}.
• 그이는 매번 무슨 회의가 {있다고/있답시고} 일요일에도 나가요.
• 너는 여기서 {삼각김밥을/삼각김밥이나} 먹어라.
• 이 나이에 고물 자동차나 끌고 다니니 {한심합니다/*다행입니다}.
• 이 나이에 고물 자동차나마 끌고 다니니 {*한심합니다/다행입니다}.

위 예문에서 -ㄴ다나는 가벼운 경멸, -ㄴ답시고는 비아냥, -이나, -나, -나마는 앞선 말이 하찮음을 나타냅니다. 다만 -나는 부정적인 감정, -나마는 긍정적인 감정을 나타내면서 그 의미 차이를 드러내고 있습니다.

증거성

증거성(evidentiality)이란 문장에 표현된 명제, 정보를 어떠한 경로를 통해 입수했는가를 나타내는 문법 범주입니다. 가령 문장에 표현된 사실을 자신이 직접 감각 경험을 통해 알게 되었는지, 남으로부터 전해 들었는지, 어떤 증거를 바탕으로 하여 자신이 직접 추리한 것인지 등을 나타냅니다. 다음 예문을 보겠습니다.

He must have be in his office.

위 문장은 한국어로 ‘그는 사무실에 있음이 틀림없다’ 정도로 번역됩니다. 위 문장은 명제가 얼마나 확실한지(인식양태)는 물론, 해당 정보를 어떻게 입수했는지(증거성) 또한 드러내고 있습니다. 즉 위 명제는 화자가 여러 사실들을 바탕으로 추리해 도출한 것이며, 그 결과가 거의 사실에 가까울 정도로 확실하다고 판단을 내리고 있는 것입니다.

세계 언어에서 증거성은 이처럼 양태와 동시에 실현되는 경우가 많아서 증거성을 양태의 하위 범주로 다루는 문법 학자들도 많습니다. 증거의 종류는 다음과 같이 6가지로 나눠 생각해볼 수 있습니다.

• 시지각 (visual perception)
• 시각 이외의 지각 (non-visual perception)
• 내적 사유, 성찰 (introspection, endophoric reflection)
• 지각 증거를 바탕으로 한 추리 (inference based on perceptual evidence)
• 일반적 사실을 바탕으로 한 추론 (reasoning based on general assumption, presumptive, assumptive)
• 전문(傳聞, hearsay, quotative)

의외성

의외성(mirativity)이란 문장에 표현된 명제가 화자의 지식 체계에 아직 내면화하지 못한 지식임을 나타내는 문법범주입니다. 한국어에서는 -네, -구나 의미의 핵심이 의외성입니다. 예컨대 다음 예문의 화자는 청자가 집에 이미 갔을 것으로 인식 혹은 기대하고 있었으나 실제로는 그렇지 않았다는 의미로 -네와 -구나를 쓰고 있습니다.

• 아직 집에 {안 갔네/안 갔구나}.

한국어의 문법적 양태

이상 살펴본 여러 가지 개념을 바탕으로 한국어의 문법적 양태를 -겠-, -을 것이-, -더-를 중심으로 살펴 보겠습니다. 세계 여느 언어와 마찬가지로 한국어에서도 하나의 문법 요소에 시제, 상, 양태, 증거성, 의외성 중 둘 이상의 범주에 걸쳐서 복수의 의미 성분을 한꺼번에 가지는 일이 종종 있는데요. 이 세 가지 문법 요소가 바로 이런 경우에 속합니다.

-겠-

-겠-은 ‘추측’이라는 인식 양태의 의미 성분과 ‘추리(지각 정보를 바탕으로 새로운 명제 도출)’라는 증거성의 의미 성분이 결합되어 있습니다.

추측

다음 예문과 같습니다.

• 지금 밖에는 비가 오겠다.

의문문에서는 청자의 판단(추측)을 묻는 데 이용됩니다.

• 네 생각에는 비가 곧 그치겠니?

추측의 -겠-은 여러 시제에 사용될 수 있고 주어 제약도 없습니다.

• 어제는 비가 왔겠다 / 곧 비가 오겠다
• 이러다가 내가 밥을 못 먹겠다 / 이러다가 네가 밥을 못 먹겠다

의도

의도의 -겠-은 화자 자신을 동작주로 하는 사태를 성립시키겠다는 의지를 나타냅니다. 다음 예문과 같습니다.

• 나는 그 사람과 결혼하겠다.

의문문에서는 청자의 의도를 표현하는 데 쓰입니다.

• 너는 그 사람과 결혼하겠느냐?

평서문에서는 1인칭 주어만을, 의문문에서는 2인칭 주어만을 취할 수 있습니다.

• {나는, *너는, *철수는} 무슨 일이 있어도 그 사람과 결혼하겠다.
• {*나는, 너는, *철수는} 그 사람과 결혼하겠느냐?

하지만 1인칭 주어 평서문에서 -겠-이 쓰였다고 해서 모두 의도로 해석되는 것은 아닙니다. 다음 예문은 추측의 의미로 쓰였습니다.

• 내가 오늘 아무래도 학교에 가게 되겠다.

의도의 -겠-은 과거 시제와 결합할 수 없습니다.

• 나는 꼭 대통령이 되겠었다.

계획된 미래

명제 내용이 표상하는 사태가 가까운 미래에 발생함을 의미하되, 그 발생이 계획되어 있음을 함의합니다. 이미 정해진 것으로 불확실한 사실에 대한 추측이라고 보기 어렵습니다. 이와 관련해 중세 국어의 -게 하여 잇-에서 현대 국어의 -겠-으로 변화, 발달하는 과정에서 나타난 의미(-하게 되어 있-)가 일부 문맥에서 드러난 것이라고 해석하는 견해도 있습니다. -겠-이 계획된 미래로 쓰인 예문은 다음과 같습니다.

• 대통령께서 입장하시겠습니다.

기동상

어떤 상태에 막 접어들었음을 표현합니다. 이 역시 -겠-이 발달하는 과정에서 나타난 의미(-게 되었-)가 일부 문맥에서 드러난 것이라고 해석하는 견해도 있습니다. 다음 예문의 -겠-은 ‘아는 상태에 막 접어들었음’을 나타냅니다.

• 내일까지 과제를 제출하셔야 합니다. 예, 알겠습니다.

그렇다면 ‘알겠다’는 표현과 ‘알았다’는 표현은 어떻게 해석해야 할까요? 모국어 화자가 느끼기에 둘 사이에 큰 의미 차이를 인식하기 어렵습니다. 이와 관련해 전자의 -겠-은 ‘아는 상태에 막 접어들었음’을, 후자의 -았-은 ‘깨달은 상태 결과가 지속되고 있음’을 나타낸다고 설명할 수도 있을 것입니다. 후자의 경우 ‘깨닫다’ 정도 의미의 ‘알다’는 끝점을 가지는 유계동사인데, 결과상을 나타내는 -았-이 쓰여 과거 사태의 결과가 지속되는 의미를 표현해주고 있습니다.

-더-

-더-는 상황을 지각한 시간이 발화시 이전이라는 ‘과거’의 의미 성분, 이 정보를 지각/내성/추리를 통해 얻었다는 ‘증거성’의 의미성분, 문장의 표현된 사태가 새로운 정보라는 ‘의외성’의 의미 성분이 결합돼 있습니다. 여기서 -더-는 한국어 주절(모절)에서 쓰이는 것으로 관형사절의 ‘-더-‘와는 구분할 필요가 있습니다.

지각, 내성, 추리

-더-는 직접적인 감각 행위 및 내성, 추리(근거가 분명할 때)를 통해 알게 된 사태에 대해 사용됩니다. 다음 예문과 같이 직접 지각한 행위에 어울립니다.

• 철수가 운동장에서 체조를 하더라.

그러나 다음 예문처럼 직접 경험한 것이 아닌 것에 -더-를 쓰면 비문이 됩니다(증거성 제약).

• *먹어 본 적은 없지만 새로 나온 석류 음료가 맛있더라.

내성, 추리에 쓰인 예문은 다음과 같습니다.

• 어제 너와 얘기할 때는 몰랐는데, 집에 가서 곰곰이 생각해 보니 내 계산이 틀렸더라 : 내성
• 선생님은 벌써 퇴근하셨더라 : 추리(교무실의 선생님 책상이 비어있는 걸 보고)

과거

-더-가 나타내는 과거의 의미 성분은 시제와는 약간 다른 개념입니다. 상황을 지각한 시간이 발화시를 기준으로 했을 때 과거의 어느 한 시점이라는 의미를 나타냅니다. 다음 예문의 경우 실제 사태는 미래 어느 시점에 일어나지만, 해당 사태를 인식한 시점이 과거라는 걸 나타내고 있습니다.

• 내일부터 고속버스 요금이 오르더라.
• 강아지가 집을 잘 지키겠더라.

의외성

지각의 시점을 기준으로 했을 때 그때까지는 알지 못하거나 의식하지 못하던 사실을 새로이 알게 되었을 때 -더-가 사용됩니다.

• 그 사람 알고 보니 영 사람이 덜 되었더라.
• 미국의 수도가 워싱턴이더라.

인칭제약

더-는 인칭제약을 가지고 있습니다. 우선 객관술어가 쓰인 평서문에서는 1인칭 주어와 -더-가 어울리지 않습니다. 여기에서 객관술어란 ‘뛰다’, ‘먹다’처럼 해당 술어가 가리키는 사태가 외부에서 관찰 가능한 경우를 가리킵니다. 예문과 같습니다.

• *나는 옷을 입더라.
• *나는 동생을 찾더라.

객관술어가 쓰인 의문문에서는 2인칭 주어와 -더-가 어울리지 않습니다.

• *네가 밥을 먹더냐?

하지만 이러한 제약이 해소되는 경우도 있습니다. 예문과 같습니다.

• 내가 빨간 옷을 입었더라. (정신 없이 아무 옷이나 입고 나오느라고 그때까지 깨닫지 못했는데, 자기가 빨간 옷을 입었음을 새로이 깨닫게 된 상황)
• 세 사람 중에서 내가 제일 춤을 잘 추더라. (이전에는 몰랐는데 막상 춤을 같이 춰보니 내가 춤을 제일 잘 춘다는 사실을 새로이 깨닫게 된 상황)

이처럼 자신의 일이라도 새로 깨닫게 된 사태에는 -더-가 사용될 수 있습니다. 이러한 인칭 제약의 해소는 ‘의외성’의 의미 속성 때문이라고 설명할 수 있을 것 같습니다. 바꿔 말해 객관술어가 쓰인 평서문의 1인칭 인칭제약은 화자가 자신의 일을 새로이 인식하는 것이 자연스러운 일이 아니기 때문에 발생한다고 볼 수 있다는 것입니다.

이번엔 주관술어 쪽을 보겠습니다. 주관술어란 ‘춥다’, ‘무섭다’처럼 해당 술어가 가리키는 사태가 감정, 감각 등과 관련된 경우를 가리킵니다. 주관술어가 쓰인 평서문에서 1인칭 주어와 -더-가 자연스럽게 어울리고, 2/3인칭 주어와는 어울리지 않습니다. 주관술어가 쓰인 의문문에서는 2인칭 주어와 -더-가 자연스럽게 어울리고, 1/3인칭 주어와는 어울리지 않습니다. 다음 예문과 같습니다.

• 나는 수박이 좋더라. 나는 간밤에 춥더라.
• *어젯밤엔 바람이 불어서 진이가 춥더라.

생리적 혹은 심리적 현상에 대해 우리는 명확한 의식을 가지고 있지 않습니다. 자신과 관련한 사실이 과거의 어느 시점에서 화자의 의식의 표면에 떠오름(의외성)을 표현하기 때문에 주관술어가 쓰인 1인칭 평서문에서 -더-가 자연스럽게 쓰일 수 있습니다. 반면 타인의 내적, 심리적 경험은 지각이나 내성을 통해 파악할 수 없고, 추리를 통해 단언할 수도 없습니다. 이 때문에 주관술어가 쓰인 2/3인칭 평서문에서 -더-가 어울리지 않는다고 설명할 수도 있겠습니다.