1
AD 1852장면 1 / 3같은 연도의 세계에서 이어 보기
4색 추측
거스리가 영국 군 지도에서 4색이면 충분함을 추측.
정확한 장소가 없어 거짓 핀 대신 시간만 이어지는 장면
같은 연도의 세계에서 이어 보기이 개념의 출항 질문
모양 뒤의 세계 읽기12 / 13번째 항구“‘그래프 색칠’에서 묻습니다. 모양을 바꾸어도 남는 것과 세계를 가르는 규칙은 무엇일까?”
길이와 각도에서 출발해 연결, 구멍, 차원처럼 눈에 바로 보이지 않는 공간의 성질로 나아갑니다.
이 항로는 이해를 돕는 편집 경로입니다. 직접적인 역사 영향선이나 한 사람의 단독 발명을 뜻하지 않습니다.
한 호흡으로 이해하기
"인접한 영역이 다른 색을 갖도록 지도를 칠하려면 몇 가지 색이 필요한가?" 1852년 한 학생의 단순한 질문은 124년 후 컴퓨터에 핵심 검증을 맡긴 첫 주요 정리 가운데 하나인 4색 정리로 이어졌다. 학교 시간표·주파수 할당·컴파일러 레지스터 할당도 그래프 색칠로 모델링할 수 있다.
한눈에 보기
그래프 종류 | χ(G) | 실제 응용 |
|---|---|---|
평면 지도 (4색 정리) | ≤ 4 | 국가 지도, GIS |
이분 그래프 (홀수 사이클 없음) | 2 | 학생-과목 매칭 |
n-clique (Kₙ) | n | 완전 그래프 |
홀수 길이 사이클 | 3 | 시간표 충돌 |
Petersen 그래프 | 3 | 교과서 단골 |
트리 | 2 | 계층 구조 |
χ(G) = G의 색칠 수. 인접 정점이 다른 색이어야 하는 최소 색 수. NP-완전 일반 문제.
개념
인접한 노드는 다른 색을 가져야 하는 문제. 지도, 일부 시간표·주파수·레지스터 할당처럼 충돌 관계를 그래프로 모델링할 수 있을 때 유용하다.
핵심 식
χ(G) — 인접 정점이 다른 색을 갖는 데 필요한 최소 색 수
시간의 항구
이 개념은 한 번에 발명되지 않았습니다
장면을 따라가면 문제, 표기, 증명 기준과 쓰임이 서로 다른 장소와 시대에서 어떻게 바뀌었는지 보입니다.
2
AD 1976장면 2 / 3같은 연도의 세계에서 이어 보기
4색 정리 컴퓨터 증명
아펠·하켄이 유한한 경우 환원과 컴퓨터 검증을 결합했다. 컴퓨터 보조로 증명된 첫 주요 정리로 널리 평가된다.
정확한 장소가 없어 거짓 핀 대신 시간만 이어지는 장면
같은 연도의 세계에서 이어 보기3
AD 1979장면 3 / 3같은 연도의 세계에서 이어 보기
카프 — NP-완전 문제
리처드 카프가 3색 결정 문제가 NP-완전임을 증명. 일반 그래프 색칠은 어려움.
정확한 장소가 없어 거짓 핀 대신 시간만 이어지는 장면
같은 연도의 세계에서 이어 보기오늘날의 응용
컴파일러의 레지스터 할당, 시간표 작성, 주파수 할당, GIS 지도, 그래픽 카드의 충돌 회피.
MathVoyage 너머로
큐레이터가 고른 원전과 탐구 과제. OEIS·Project Euler·MathOverflow·arXiv에서는 발견 하나를 수첩으로 가져올 수 있습니다.
- 위키백과
- Wolfram MathWorld
- Numberphile
한 사람이 만든 개념이 아닙니다
역할이 다른 사람들을 따라가기
대표 연결은 발명자 명단이 아닙니다. 문제를 열고, 언어를 다듬고, 다른 세계로 옮긴 서로 다른 항구입니다.
수의 렌즈
같은 개념도 수의 세계가 바뀌면 다르게 보입니다
아래 수는 필수 선수 조건이 아니라 이 항로를 비추는 편집 렌즈입니다.
개념의 계보
무엇을 딛고, 무엇을 열었을까?
직접 연결만 표시하며 완전한 학습 순서나 역사 영향선을 뜻하지 않습니다.