Graph Theory & Modeling

1. Overview

그래프 이론과 모델링(Graph Theory & Modeling, GTM)은 현실 세계의 도로나 사람, 컴퓨터 서버 등 흩어져 있는 무수한 점(Node)들과 그 사이를 잇는 선(Edge)의 관계를 수리적으로 추상화하여, 가장 완벽한 '연결성의 지도'를 그리는 네트워크 위상 공학입니다.

학습자는 무방향/방향, 가중치 여부에 따라 데이터의 흐름을 다르게 통제하는 **그래프의 물리적 표현법(인접 행렬 vs 인접 리스트)**을 뜯어보고, 모든 네트워크 장비의 길찾기(Routing) 뼈대가 되는 최단 경로(Shortest Path) 물리를 해부합니다. 나아가 인터넷 봇(Bot)이나 검색 엔진이 웹페이지를 기어 다니는 **순회 알고리즘(DFS/BFS)**의 메모리 스택/큐 역학과, 순환(Cycle)이 없는 완벽한 계층 구조인 **트리(Tree)**의 수리적 특성을 통달하여, 복잡계 시스템을 데이터 구조로 압축하는 최고 수준의 아키텍트가 됩니다.

2. Scope & Boundaries

In-Scope

• 그래프 기초 해부학 (Graph Anatomy): 정점(Vertex/Node)과 간선(Edge), 차수(Degree), 경로(Path)와 회로(Cycle), 연결 그래프(Connected Graph).
• 그래프의 메모리 표현 (Physical Representation): 인접 행렬(Adjacency Matrix, $O(V^2)$) vs 인접 리스트(Adjacency List, $O(V+E)$).
• 트리와 특수 그래프 (Trees & Bipartite): 이분 그래프(Bipartite Graph), 사이클이 없는 방향 그래프(DAG: Directed Acyclic Graph), 스패닝 트리(Spanning Tree).
• 네트워크 기하학 (Network Topology): 오일러 경로(Eulerian Path - 붓떼기), 해밀턴 경로(Hamiltonian Path - 외판원 문제), 평면 그래프(Planar Graph).

Out-of-Scope

• 그래프 탐색 및 최단 경로 알고리즘의 최적화 코드 짜기: 다익스트라(Dijkstra)나 A* 알고리즘의 힙(Heap) 튜닝 과정 $\rightarrow$ 04. Data Structures & Algorithms 영역으로 위임.
• RDBMS의 쿼리 최적화 트리: 데이터베이스 엔진 내부에서 B-Tree가 어떻게 쪼개지는가 $\rightarrow$ 06. Data & Information Management 영역.

Boundaries

• GTM vs. Relations (01-01-01): 관계(STR)가 행렬에 0과 1을 찍는 순수한 대수적 논리라면, GTM은 그 관계를 실제 시각적인 점과 선으로 끄집어내어 "서울에서 부산까지 가장 기름을 덜 먹고 가는 선(Path)은 무엇인가?"를 따지는 물리적, 기하학적 적용 단계입니다.

3. Counterexample

• 인접 행렬의 메모리 폭발 (Adjacency Matrix Fallacy): 페이스북 유저 20억 명의 친구 관계망을 구성하겠다면서, 20억 $\times$ 20억 크기의 2차원 배열(인접 행렬)을 메모리에 띄우는 정신 나간 짓. 대부분의 유저는 기껏해야 500명 정도와 연결되어 있으므로 행렬의 99.999%는 텅 빈 '0'이 됩니다(희소 행렬, Sparse Matrix). 이를 인접 리스트(List)로 바꾸지 않으면 지구상의 어떤 슈퍼컴퓨터의 RAM으로도 감당할 수 없이 폭발합니다.
• DAG와 사이클 맹신 (Cyclic Dependency Fallacy): 엑셀에서 A 셀이 B 셀을 참조하고 B 셀이 다시 A 셀을 참조하는 순환(Cycle) 구조를 만들어버리면 에러가 뿜어져 나오듯, 작업 스케줄러(예: Airflow, 빌드 시스템)를 짤 때 방향 그래프가 DAG(사이클이 없는 상태)임을 수학적으로 증명하지 않으면 프로그램이 영원히 멈추는 무한 루프(Deadlock)에 빠져 터져버립니다.

4. Prerequisites

• 집합론과 관계 (Basic): 그래프의 본질이 정점들의 집합($V$)과 그들의 관계($E \subseteq V \times V$)이므로, 이항 관계(Binary Relation)의 행렬 표현을 이해해야 합니다. (01-01-01 STR)

5. Learning Map

6. Learning Topics

Basic

Core Topic 01: 그래프의 해부학과 물리적 메모리 표현 (Graph Anatomy & Representation)

• Why to Learn: 복잡하게 얽힌 고속도로망이나 사람들의 친구 관계를 컴퓨터가 알아들을 수 있는 0과 1의 메모리 덩어리로 압축하기 위해서입니다.
• What to Learn:
  • Concepts: 무방향/방향 그래프(Undirected/Directed Graph), 차수(Degree), 가중치 그래프(Weighted Graph).
  • Skills: 인접 행렬(Adjacency Matrix, $O(V^2)$), 인접 리스트(Adjacency List, $O(V+E)$).
  • Tools: Python list of lists, dict of sets.
  • Trade-offs: "A와 B가 연결되었는가?"를 단 $O(1)$ 만에 찾아내는 빠른 속도지만 빈 공간(0) 때문에 메모리를 미친 듯이 갉아먹는 인접 행렬($V \times V$) vs "A의 모든 친구들"을 메모리 낭비 없이 선형으로 쭉 훑어보는 데 최적화된 인접 리스트의 저렴함.
• How to Learn:
  • 1단계: 정점(Node)이 100만 개인데 간선(Edge)이 200만 개밖에 안 되는 매우 듬성듬성한(Sparse) 그래프를 인접 행렬로 선언했을 때 튀어나오는 OOM(Out of Memory) 에러를 계산합니다.
  • 2단계: 무방향 그래프의 인접 행렬은 언제나 주대각선(Main Diagonal)을 기준으로 대칭(Symmetric)이라는 수리적 거울 역학을 증명합니다.
• Implement: 1,000개의 교차로를 가진 도시의 도로망 데이터를 읽어와서, 특정 조건(Dense/Sparse)에 따라 인접 행렬과 인접 리스트 중 어느 자료구조가 메모리(MB)를 덜 먹는지 물리적으로 측정하는 판별기 작성.

Recommended

Core Topic 02: 경로와 연결성, 그리고 NP-Hard (Paths & Connectivity)

• Why to Learn: 택배 기사가 기름값을 아끼며 모든 동네를 다 도는 방법이나, 모든 다리를 한 번씩 건너는 산책 경로가 수학적으로 존재하는지 계산하기 위함입니다.
• What to Learn:
  • Concepts: 경로(Path), 회로(Cycle), 연결 요소(Connected Components).
  • Skills: 오일러 회로(Eulerian Circuit)의 차수(Degree) 짝수 조건, 해밀턴 회로(Hamiltonian Circuit)와 외판원 문제(TSP).
  • Tools: 한 붓 그리기 기법.
  • Trade-offs: 홀수 차수를 가진 정점이 0개거나 2개면 반드시 오일러 경로(모든 간선을 1번 통과)가 존재함을 $O(E)$에 단박에 알아내는 수리적 명쾌함 vs 모든 정점을 1번씩 방문하는 해밀턴 경로(TSP)는 구하는 공식이 없어 모든 경우를 다 뒤져야 하는 지수 시간($O(N!)$)의 끔찍함.
• How to Learn:
  • 1단계: 쾨니히스베르크의 7개 다리 문제에서, "들어온 다리가 있으면 반드시 나가는 다리가 있어야 한다(모든 정점의 차수가 짝수)"는 위상 기하학적 증명으로 오일러 회로의 불가능성을 해부합니다.
  • 2단계: 연결되지 않고 섬처럼 떨어져 있는 2개의 서브 그래프(Connected Components)를 찾아내기 위해 BFS(너비 우선 탐색)가 물방울처럼 퍼져나가는 물리를 뜯어봅니다.
• Implement: 임의의 무방향 그래프가 주어졌을 때, 각 정점의 차수(Degree) 홀짝 여부를 스캔하여 "이 그래프는 한 붓 그리기가 가능하다/불가능하다"를 0.001초 만에 논리적으로 판별해 내는 검사 모듈 작성.

Practical

Core Topic 03: 트리(Trees)와 방향성 비순환 그래프 (DAGs)

• Why to Learn: 무한 루프(Deadlock)에 빠질 위험이 단 1%도 없는 가장 완벽하고 계층적인 데이터 의존성(Dependency) 파이프라인을 구축하기 위해서입니다.
• What to Learn:
  • Concepts: 트리(Tree: 사이클이 없고 연결된 무방향 그래프, $E = V - 1$), DAG(Directed Acyclic Graph).
  • Skills: 트리의 잎(Leaf) 노드 속성, 위상 정렬(Topological Sorting).
  • Tools: Kahn's Algorithm (위상 정렬 알고리즘).
  • Trade-offs: 부모-자식의 절대적 계층을 유지하여 쿼리 속도($O(\log N)$)를 극한으로 뽑아내는 트리 구조 vs 유연성이 떨어져 노드 간 복잡한 다대다 연결(예: 소셜 네트워크망)을 표현할 수 없는 구조적 한계.
• How to Learn:
  • 1단계: 정점이 $N$개일 때, 그래프가 트리이기 위한 절대 조건은 무조건 간선이 $N-1$개이어야 하며 루프(Cycle)가 없어야 한다는 수학적 불변성(Invariant)을 증명합니다.
  • 2단계: 양말을 신어야 신발을 신을 수 있다는 의존성 화살표가 있는 DAG 모델에서, 진입 차수(In-degree)가 0인 작업(아무런 선수 조건이 없는 일)부터 순서대로 뜯어내며 빌드(Build) 순서를 짜는 위상 정렬 물리를 분석합니다.
• Implement: NPM 패키지 매니저의 package.json 의존성 트리 데이터를 받아, A 패키지가 B를 요구하고 B가 다시 A를 요구하는 미친 순환 참조(Cycle)를 탐지해 에러를 뿜고 차단하는 의존성 파서 구현.

Advanced

Core Topic 04: 그래프 채색과 평면 그래프 (Coloring & Planarity)

• Why to Learn: CPU 레지스터를 변수들에 할당하거나 기지국 주파수를 분배할 때, 서로 부딪히지(충돌) 않게 최소한의 자원(색깔)으로 나누어주는 극강의 자원 할당 능력을 갖추기 위함입니다.
• What to Learn:
  • Concepts: 그래프 채색(Graph Coloring), 채색수(Chromatic Number, $\chi(G)$), 이분 그래프(Bipartite Graph, $\chi(G)=2$).
  • Skills: 평면 그래프(Planar Graph)와 오일러 다면체 정리($V - E + F = 2$), 쿠라토프스키 정리(Kuratowski's Theorem).
  • Tools: Greedy Coloring Algorithm.
  • Trade-offs: 어떤 지도라도 인접한 나라끼리 색이 안 겹치게 칠하는 데 '4가지 색(4-Color Theorem)'이면 충분하다는 수리적 극한 최적화 vs 이 최소 색상을 찾아내는 범용 알고리즘 자체가 NP-Hard라 완벽한 답을 구하려면 영겁의 연산 시간이 걸리는 모순.
• How to Learn:
  • 1단계: 정점들을 두 그룹(예: 학생과 수업)으로 쫙 나누어서, 무조건 A그룹 정점에서 B그룹 정점으로만 화살표가 그어지고 같은 그룹끼리는 연결이 없는 '이분 그래프(Bipartite, 색칠수 2)'의 물리적 매칭 역학을 해부합니다.
  • 2단계: 선(Edge)들이 서로 교차(X자 꼬임)하지 않고 2차원 종이 위에 그릴 수 있는 평면 그래프(Planar Graph)의 조건(오일러 공식 $V - E + 면 = 2$)을 통해 반도체 회로 기판이 합선되지 않게 설계하는 기하학을 뜯어봅니다.
• Implement: 인접한 노드(변수)끼리 같은 CPU 레지스터(색상)를 쓰지 못하도록 하는 '컴파일러 레지스터 할당기'의 코어 로직을 탐욕법(Greedy Coloring)으로 짜서, 필요한 최소 레지스터 개수를 도출하는 수리 시뮬레이터.

7. Terminology

8. References

Primary References

• [P1] CS2023 - DS/Graphs and Trees — The standard for graph modeling.
• [P2] SWEBOK v4.0 - Software Design / Structural Design — Graphs in architecture.

Secondary References

• [Introduction to Graph Theory] Douglas West — Detailed mathematical approach.
• [Graph Theory and Its Applications] Gross & Yellen — Computational perspective.

Industry References

• [Google PageRank Patent] — Graphs for search relevance.
• [GraphQL Specification] — Graph patterns in modern API design.

9. Final Checklist

Primary Checklist

• '핸드셰이킹 보조정리(Handshaking Lemma)'를 이용하여 주어지지 않은 간선의 수를 노드의 차수 정보만으로 산출할 수 있는 가? (P1)
• 정점이 $n$개인 그래프가 트리가 되기 위한 물리적 필요충분조건 3가지를 논리적으로 서술 가능한가? (P1)

Secondary Checklist

• 오일러 경로(Eulerian Path)의 존재 여부를 홀수 차수 정점의 개수만 보고 물리적으로 즉각 판단 가능한가?
• 소셜 네트워크 데이터에서 '클러스터 계수'를 그래프 이론 관점으로 정의하고 네트워크의 밀집도를 분석할 수 있는가?

Industry Checklist

• 마이크로서비스 간의 의존성 구조를 그래프로 모델링하여 순환 참조(Circular Dependency)가 발생하는 지점을 수학적으로 탐지 가능한가? (SFIA)
• 네트워크 전송 지연을 최소화하기 위해 '최단 경로 트리' 아키텍처를 설계하고, 노드 추가 시의 영향도를 그래프 위계 관점에서 평가할 수 있는 가?