그래프

참고 자료는 다음과 같습니다.

 

- 파이썬 자료구조와 알고리즘 (한빛미디어, 2019)

 

- 그래프 ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84_%EC%9D%B4%EB%A1%A0_%EC%9A%A9%EC%96%B4

그래프 이론 용어 - 위키백과, 우리 모두의 백과사전

- 평면 그래프

miretia.tistory.com/388

입체도형을 꾹꾹 눌러보자-평면그래프

- 강한 연결

ko.wikipedia.org/wiki/%EA%B0%95%ED%95%9C_%EC%97%B0%EA%B2%B0_%EC%9A%94%EC%86%8C

강한 연결 요소 - 위키백과, 우리 모두의 백과사전

- 트리와 포레스트

slidesplayer.org/slide/16528633/

그래프와 트리 (Graphs and Trees) - ppt download

- 부분 그래프

contents.kocw.or.kr/KOCW/document/2016/duksung/leesangjune/12.pdf

- 인접 리스트

duwjdtn11.tistory.com/515

[Python] 인접 행렬과 인접 리스트

그래프

○ 노드(정점, vertex)들이 간선(변, arc)으로 연결된 추상 네트워크

 

○ 수식 : G = (V,E)

 

○ 그래프 G 예시

  ● 노드 집합 V = {A,B,C}

  ● 간선 집합 E = {{A,B},{B,C},{C,A}}

그림 1. 그래프 G

그래프의 기본 개념

○ 유향 그래프와 무향 그래프로 나뉨

  ● 유향 그래프 : 간선에 방향이 있어 처음과 끝이 존재함. 

  ● 무향 그래프 : 간선에 방향이 없음. 간선으로 연결된 노드는 서로 인접하며 이웃이라 함

 

○ 부분 그래프 : 그래프 G의 정점과 모서리 일부를 제거하여 얻는 그래프.

  ● 유도 부분 그래프 : 그래프 G의 정점과 그것들에 연결된 모서리를 제거하여 얻어진 그래프. 아래 그림 2는 그림 1의 그래프 G의 부분그래프이자 유도 부분 그래프라고 할 수 있음

그림 2. 그래프 G의 유도 부분 그래프

  ● 신장 부분 그래프 : 원본 그래프의 모든 노드를 포함하는 부분 그래프 

 

○ 완전 그래프 : 그래프의 모든 노드가 서로 인접한 그래프

 

○ 차수(degree) : 한 노드에 이어져 있는 간선의 수

 

○ 경로(path) : 같은 꼭짓점을 거듭 거치지 않는 변들의 열

  * 경로나 보행의 길이는 간선의 수와 동일함

 

○ 보행(walk) : 꼭짓점과 변이 교대로 나타나는 열(sequence)이면서, 각 변의 앞과 뒤에 위치한 꼭짓점을 그 변의 양끝점으로 갖는 열

 

○ 순환(cycle) : 경로와 같으나 마지막에 연결된 간선의 노드가 다시 첫 번째 노드에 연결됨

 

○ 가중 그래프 : 간선에 가중치가 있는 그래프

  * 경로나 순환의 가중치는 포함된 간선들의 가중치 총합임

 

○ 평면 그래프 : 간선을 서로 횡단하지 않고 평면에 그릴 수 있는 그래프

  ● 평면 그래프의 오일러 공식 : V - E + F = 2(V : 노드 수, E : 간선 수, F : 면 수)

 

○ 순회(traversal) : 그래프에 연결된 모든 요소를 탐색하는 일

 

○ connected : 모든 노드에서 다른 모든 노드로 가는 경로 존재할 때를 말함

 

○ 연결 요소 : 모든 노드가 연결된 최대 부분 그래프

  =>깊이 우선 탐색, 너비 우선 탐색 같은 순회 알고리즘으로 찾을 수 있음

 

○ strongly connected : 모든 정점이 모든 다른 정점에 대해 도달 가능한 경우를 말함

  ● 강한 연결 요소 : 강하게 연결된 최대 하위 그래프

 

○ 트리, 포레스트

  ● 트리(tree) : 비순환적으로 연결되어 있는 유향 그래프. 두 노드는 하나의 경로로 연결됨. 즉, 임의의 두 노드 간 경로는 유일함

  ● 포레스트(forest) : 1개 이상의 트리로 구성된 그래프

이웃 함수

○ 이웃 함수 : 모든 이웃 V의 컨테이너

  ● 인접 리스트, 인접 행렬 등

 

○ 인접 리스트 : 인접 리스트는 그래프의 연결 관계를 vector의 배열로 나타내는 방식

  ● 각 노드에서 이웃 리스트에 접근 가능

  ● n개 노드 있을 때 각 노드의 인접(이웃) 리스트는 단순한 숫자 리스트임

  ● 장점 : 실제로 연결된 노드에 대한 정보만 저장하므로 모든 벡터들의 원소 개수 합이 간선 개수와 동일하며 인접 행렬에 비해 탐색 비효율성이 적으며, 메모리가 절약됨

  ● 단점 : 노드 i와 j 간 연결 여부를 확인할 때 해당 노드의 모든 원소들을 검사해야 함

    => 시간 복잡도 : O(V)

  ● Python의 셋, 리스트, 딕셔너리를 사용하여 인접 리스트 구현 가능

    □ 셋 : 평균 시간복잡도는 O(1), 최악의 경우 O(n). 그래프에 간선이 많은 경우 셋을 사용하는 것이 좋음

    □ 리스트 : 시간복잡도는 O(n). 이웃 노드를 반복해서 접근하는 경우 리스트를 사용하는게 좋음

    □ 딕셔너리 : 노드가 키가 되고 각 노드를 간선 가중치 등의 값으로 연결 가능

    ex)

    A, B, C, D = range(4)

    G = [{B,C}, {A,C,D}, {A,B}, {B}]      # set으로 표현한 경우. A, B, C, D 순서로 자기와 연결된 원소 표현

    G = {'A':set('BC'), 'B':set('ACD'), 'C':set('AB'), 'D':set('B')}      # dictionary로 표현한 경우

    G = [{B:2,C:4}, {A:2,C:5,D:1}, {A:4,B:5}, {B:1}]      # dictionary로 표현한 경우 + 가중치

그림 3. 예시 그리프 G

○ 인접 행렬

  ● 각 노드의 모든 이웃에 대해 하나의 행을 가짐

  ● 1이면 연결, 0이면 연결 안됨

  ● 대각 요소는 항상 0

  ● 그래프 G를 나타내면 다음과 같음

  ex)

  A,B,C,D,E,F = range(6)

  N = [[0,1,1,0], [1,0,1,1], [1,1,0,0], [0,1,0,0]]

  ● 무향 그래프의 경우 인접 행렬은 대칭임

  ● 간선 찾는 시간복잡도 : O(1) -> 연결이 됐는지 여부

  ● 어떤 노드의 이웃 순회 시간 복잡도 : O(n)