Graph Theory & Modeling

1. Overview

그래프 이론 및 모델링(Graph Theory & Modeling, GTM)은 현실 세계의 복잡한 연결 관계를 노드(Vertex)와 간선(Edge)이라는 수학적 객체로 추상화하여 분석하는 원리를 다룹니다.

그래프는 인터넷의 링크 구조, 소셜 네트워크, 물류 경로, 지식 맵 등 현대 컴퓨팅의 거의 모든 데이터를 표현하는 언어입니다. 학습자는 방향성 유무에 따른 유향/무향 그래프의 물리적 성질, 계층 구조의 근간인 트리(Tree), 그리고 효율적 탐색의 핵심인 **연결성(Connectivity)**과 최단 경로 논리를 배웁니다. 이를 통해 복잡하게 얽힌 정보 뭉치에서 의미 있는 패턴을 추출하고, 최적의 데이터 이동 경로를 물리적으로 설계하는 능력을 갖춥니다.

2. Scope & Boundaries

In-Scope

Graph Fundamentals: 정점(Vertex), 간선(Edge), 차수(Degree) 및 인접성(Adjacency)의 정의
Paths & Circuits: 오일러 경로, 해밀턴 경로 및 사이클(Cycle) 탐지 물리
Tree Dynamics: 뿌리 깊은 트리(Rooted Trees), 스패닝 트리 및 계층적 통신 구조
Special Graphs: 이분 그래프(Bipartite Graph), 완전 그래프 및 평면 그래프의 성질

Out-of-Scope

그래프 알고리즘의 구체적인 코드 구현 (04-02 AL 영역으로 위임)
그래프 데이터베이스(Neo4j 등)의 쿼리 튜닝 (06-02 NPL 영역으로 위임)

Boundaries

GTM vs. Network Engineering: 네트워크 공학이 '물리적 케이블과 전송 규격'을 다룬다면, GTM은 그 연결들이 형성하는 '논리적이고 추상적인 구조적 한계와 흐름 가능성'에 집중합니다.

3. Counterexample

단순히 "트리 자료구조를 코딩하는 것"은 GTM 학습이 아닙니다. 왜 특정 네트워크 토폴로지에서 브리지(Bridge) 간선을 제거하면 시스템이 물리적으로 두 개의 독립된 컴포넌트로 분리되는지 가용성을 수학적으로 설명할 수 있어야 하고, 특정 그래프가 평면 그래프가 아닐 때 왜 회로 기판 설계에서 선의 교차 없이 배치가 불가능한지 입증할 수 있어야 합니다.

4. Prerequisites

집합론 및 관계 (Basic): 두 객체 간의 짝(Pair)을 통한 관계 정의가 필수입니다. (01-01 STR)
이산 구조 및 수학적 논리 (Recommended): 증명 기법과 논리적 추론력이 권장됩니다. (01. CS&E Root)

5. Learning Map

Atomic Connections: 점과 선의 결합으로 관계를 모델링하는 법을 익힙니다.
Structural Fingerprints: 인접 행렬 및 인접 리스트를 통해 그래프의 성질을 수치화합니다.
Traversal Physics: 그래프 내부를 유영하며 도달 가능성(Reachability)을 판단하는 시퀀스를 배웁니다.
Optimal Substructures: 트리와 사이클을 구분하여 자원 낭비 없는 최소 연결망을 구상합니다.

6. Learning Topics

Basic

Core: 그래프의 구성과 표현 물리 (Graph Basics)

Why to Learn: 복잡한 네트워크를 컴퓨터가 이해할 수 있는 정형 데이터로 변환하기 위함입니다.
What to Learn:
- 그래프 정의: $G = (V, E)$ 의 성분과 물리적 의미
- 유향 그래프(Directed) vs 무향 그래프(Undirected)의 흐름 역학
- 차수(Degree) 규칙: 정점에 연결된 간선의 수( $\sum deg(v) = 2|E|$ )
How to Learn:
- 교차로를 정점으로, 도로를 간선으로 하는 지도 모델링 실습
- 인접 행렬(Matrix)과 인접 리스트(List)의 메모리 점유 및 접근 속도 물리 비교
Implement: 실시간으로 정점과 간선을 추가/삭제하며 변화를 추적하는 그래프 데이터 관리기

Why to Learn: 데이터가 한 지점에서 다른 지점으로 전달될 수 있는 통로가 존재하는지 확인하기 위해서입니다.
What to Learn:
- 보행(Walk), 경로(Path), 회로(Circuit)의 엄밀한 수학적 구분
- 연결 성분(Connected Components): 정점 간의 고립 여부 판단 논리
- 강한 연결성(Strongly Connected): 유향 그래프에서의 순환 도달 물리
How to Learn:
- 한붓그리기(Eulerian) 가능성을 차수가 짝수인지 여부로 즉각 판별하는 연습
- 인터넷 라우팅에서 특정 노드가 죽었을 때 우회 경로가 수학적으로 보장되는지 분석
Implement: 그래프에서 사이클 존재 여부를 감지하여 데드락(Deadlock) 가능성을 경고하는 엔진

Practical

Core: 트리의 물리적 구조와 활용 (Tree Mechanics)

Why to Learn: 중복된 경로 없이 모든 데이터를 최단 거리로 연결하는 효율적인 위계를 구성하기 위함입니다.
What to Learn:
- 트리의 정의: 사이클이 없는 연결 그래프( $|V| - 1 = |E|$ )
- 루트(Root), 리프(Leaf), 부모-자식의 물리적 위계 구조
- 최소 신장 트리(MST) 개념: 전체 노드를 잇는 가장 적은 비용의 간선 집합
How to Learn:
- 파일 시스템의 디렉토리 구조를 트리 모델로 추상화하고 탐색 비용 측정
- 스패닝 트리 알고리즘이 네트워크 브로드캐스트 스톰(Storm)을 어떻게 물리적으로 막는지 원리 분석
Implement: 불필요한 루트를 제거하고 효율성을 높인 최소 신장 트리 시뮬레이터

Advanced

Core: 특수 그래프와 매칭 이론 (Advanced Topologies)

Why to Learn: 칩 설계, 스케줄링 등 특수 목적의 물리적 배치 문제를 해결하기 위해서입니다.
What to Learn:
- 이분 그래프(Bipartite Graph): 두 그룹 사이의 연결로만 구성된 매칭 구조
- 평면 그래프(Planar Graph): 2D 평면에서 간선 교차 없이 그릴 수 있는 물리성
- 그래프 채색(Coloring): 인접한 노드와 다른 색을 입히는 자원 할당 논리
How to Learn:
- '작업자'와 '일거리'를 이분 그래프로 모델링하고 최대 매칭(Maximum Matching) 가능성 연구
- 오일러의 다면체 정리( $V - E + F = 2$ )를 통해 평면 그래프의 한계를 수리적으로 도출
Implement: 서버 클러스터 가용 영역(AZ) 할당 시 충돌을 방지하는 그래프 채색 솔루션

7. Terminology

Term (EN / ko, abbr)	1문장 정의	단계(기본/권장/실무/심화)	역할/맥락	관련 개념	유사/대비/함께 사용	오해 포인트	Evidence(Primary/Secondary/Industry)	Flags(core)
Adjacency (인접)	두 정점이 하나의 간선으로 직접 연결되어 있는 물리적 상태입니다.	기본	연결 정의	Matrix	Incident	'가까움'의 감성적 의미와 혼동	P1:CS2023/Graphs	core
Connectivity (연결성)	그래프 내 임의의 두 노드 사이에 경로가 존재하여 통신이 가능한 정도를 나타내는 수치입니다.	추천	신뢰성 분석	Components	Reachability	단순히 '선이 많음'으로 오해	P1:CS2023/Graphs	core
Tree (트리)	순환(Cycle)이 전혀 없으면서 모든 노드가 연결된 특수한 형태의 그래프 물리입니다.	실무	계층 형성	Root / Leaf	Graph	'데이터 구조'로만 한정 오해	P1:CS2023/Graphs	core
Bipartite (이분)	모든 간선이 서로 다른 두 집합의 원소 사이에서만 발생하는 분리된 그래프 구조입니다.	심화	매칭/할당	Matching	Flow	'두 개로 쪼개짐'과 혼동	P1:CS2023/Graphs	core

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)
네트워크 전송 지연을 최소화하기 위해 '최단 경로 트리' 아키텍처를 설계하고, 노드 추가 시의 영향도를 그래프 위계 관점에서 평가할 수 있는 가?