요약
수학자 미하일 라브로프가 퍼즐에서 출발해 증명까지 이끄는 그래프 이론 입문서를 무료로 공개했습니다.
그래프 이론은 대상들 사이의 관계를 다루는 수학 분야입니다. 조합론 연구자인 라브로프는 케네소주립대학교에서 그래프 이론을 가르치며 쓴 강의 노트를 보강해 이 책으로 엮었습니다.
왜 중요한가
- 증명을 처음 써 보는 독자를 위해 각 단계를 왜 밟는지까지 풀어 쓴 입문서입니다.
- 학부 수업 교재로도, 혼자 공부하는 독자의 독학서로도 쓰도록 만들었습니다.
- CC BY-SA 4.0(출처를 밝히고 같은 조건으로 나누면 자유롭게 쓸 수 있는 라이선스)으로 공개해 누구나 내려받아 읽을 수 있습니다.
핵심 내용
- 제목에는 수학은 직접 해 보지 않고는 배울 수 없다는 저자의 믿음이 담겼습니다.
- 본문에 수업에서 던질 질문을 넣고, 답을 보기 전에 멈춰서 생각해 보라고 권합니다.
- 스위스 지도 색칠, 하노이의 탑, 스도쿠, 체스 나이트의 순회 같은 퍼즐로 개념을 끌어냅니다.
- 차수, 트리, 매칭, 그래프 색칠, 평면 그래프, 연결도와 최대 흐름까지 7부로 다룹니다.
- 부록에는 증명 작성법과 귀납법을 따로 실었고, 고친 오류는 버전 기록으로 공개합니다.
HN 반응
- 경로 탐색 소프트웨어, 부품 구성 관리, PageRank 같은 실무 활용 사례가 이어졌고, 실제로는 학부 수준의 단순한 알고리즘이 가장 쓸모 있다는 경험담도 나왔습니다.
- AI가 쓴 책일까 봐 경계된다는 댓글에 저자를 10년 넘게 안다는 이용자가 직접 쓴 책이라고 보증했고, AI 저작을 어떻게 볼지를 두고 긴 논쟁이 붙었습니다.
저는 몇 년째 업무에서 그래프 이론을 쓰고 있습니다. 그래프 이론이 실제로 쓰이는 좋은 예가 경로 탐색 소프트웨어입니다. 말 그대로 처음부터 끝까지 그래프로 이루어져 있습니다.
우선 도로망 전체가 방향 그래프로 표현됩니다. 그래프의 정점을 따라 경로를 찾는 데 가장 널리 쓰이는 알고리즘은 유서 깊은 A입니다. 꼭 최단 거리를 찾는 것은 아니고, 직접 정의한 휴리스틱에 따라 온갖 상충 요소를 고려했을 때 가장 최적인 경로를 찾습니다. A에는 변형이 많은데, 요즘 구현체는 대부분 더 빠른 사촌격인 양방향 A*를 씁니다. 출발점과 도착점 양쪽에서 동시에 지점 간 계산을 밀고 들어오는 방식입니다.
그다음이 다익스트라인데, 홍수 탐색(flood search)에 씁니다. 예컨대 모든 정점에서 집으로 돌아오는 최소 비용을 구해 두면, 탐색 예산이 정해져 있을 때 언제 탐색을 되돌려야 하는지 알 수 있습니다.
되돌아오는 루프를 만들 수 있는지 판단할 때는 멩거의 정리를 썼습니다. 기본적으로 바깥쪽으로 탐색한 뒤, 같은 간선을 지나지 않고 돌아오는 경로를 탐색하는 겁니다.
타잔(Tarjan) 알고리즘은 모든 하위 네트워크를 식별하는 데 씁니다. 그래야 더 넓은 네트워크로 빠져나갈 길이 없는, 끊어진 정점들의 섬에 갇히는 일이 없으니까요.
이런 알고리즘 상당수가 수십 년 전에 고안됐는데도 여전히 현대 경로 탐색 소프트웨어의 근간입니다.
계속 머릿속을 떠나지 않는 생각이 있는데, 경로 탐색은 결정론적 성격이 매우 강한 문제 영역이라 LLM이 이를 대체할 수 있을 것 같지 않다는 겁니다. LLM이 직접 구현하기보다는 호출해서 쓰는 도구의 좋은 예로 보입니다.
실제로 제가 @simonw와 나눈 대화를 보시면, 그가 Astra에게 조깅 경로를 생성하게 했는데 GIS 스택 전체를 구축하느라 30분쯤 걸렸습니다. 바다를 끓이겠다는 식의 무모한 접근처럼 보이고, 그게 과연 최적일지 확신이 서지 않습니다. https://x.com/baz_shkara/status/2099118620647305630
도시 20곳에 대한 최적 외판원 문제를 무차별 대입으로 풀려면 우주가 몇 번은 생겼다 사라질 시간이 걸리는데, 그래도 절반에도 못 미칠 거예요. 휴리스틱으로 타협해야 하고, 보통은 그러면 최적에 가까운 해가 나옵니다.
외판원 문제를 푸는 가장 단순한 정확해 알고리즘은 O(n!)이지만, 동적 계획법을 쓰면 O(n^2 * 2^n)까지 낮출 수 있어서 n=20이면 충분히 다룰 만합니다.
그리고 그래프의 구조를 활용하면, 수만 개 지점에 이르는 훨씬 큰 실제 데이터 집합에서도 정확해를 구할 수 있을 때가 있습니다.
제 다른 댓글을 보세요. 이제 바보가 된 기분이네요.
무차별 대입을 어떻게 정의하느냐에 따라 달라요. 20개 도시는 동적 계획법으로 쉽게 풀 수 있는데, 동적 계획법은 본질적으로 가지치기를 곁들인 무차별 대입이거든요.
:faceslap:
저는 가지치기로는 가지의 하한만 구할 수 있을 뿐 최적 경로로 이어지지는 않는다고 계속 생각하고 있었어요. 오늘 또 하나 배웠네요!
지난 몇 년간 그래프를 많이 다뤄 왔습니다. 대체로 neo4j를 쓰기 시작한 뒤부터인데, 모든 작업이 neo4j와 직접 관련된 것은 아닙니다. 아주 흥미로운 그래프 알고리즘도 여럿 만들었지만, 제 그래프 이론 지식이 활약할 일이 별로 없다는 점은 늘 조금 아쉽습니다. 해밀턴 경로가 필요했던 적도, 정점의 차수로 뭔가를 해야 했던 적도 없습니다. 전부 논리와 직관으로 해결됩니다.
그래도 지금 하는 일에 적용할 만한 게 있는지 이 글을 읽어 봐야겠습니다.
제 경험상 가장 쓸모 있는 건 비교적 단순한 학부 수준 알고리즘이었습니다. 그래서 가장 먼저 배우는 것이기도 할 겁니다.
제 생각에는 단순한 기법을 철저히 배우고 이해하는 쪽이 훨씬 실용적입니다. 생각보다 깊이가 있는 경우가 많습니다.
비유하자면, 종합격투기 경기 중 상당수(대부분?)는 첫해에 배우는 기술로 승부가 갈립니다.
여담이지만, 졸업하고 16년 동안 고급 알고리즘보다 간단한 통계에서 훨씬 많은 덕을 봤습니다.
EDIT:
제 생각에 이론과 기법은 배우기가 그리 어렵지 않습니다. 정작 어려운 건 응용처를 찾는 일이고, 여기에는 어느 정도 창의력이 필요합니다.
그래프 이론(과 그 응용인 네트워크 이론)의 활용처 중 아주 유용한데도 잘 쓰이지 않는[1] 사례가 부품 데이터 시스템의 형상 관리입니다.
하드웨어 제조 현장, 특히 새로 시작했거나 "차고 공장" 같은 곳에서 신규 사업을 많이 따내다 보면, "형상이 너무 많다"는 문제가 "우리 제품이 너무 많이 팔린다"는 문제와 정면충돌하는 악몽 같은 상황에 금세 빠집니다. 차고 공장 규모라면 온갖 종류를 대여섯 대씩 만드는 건 그럭저럭 해낼 수 있지만, 1,000대, 10,000대 주문이 들어오기 시작하면 그 많은 라인을 계속 돌리는 복잡도에 어뢰를 맞게 됩니다. 결국 뭔가 하나는 망치게 되고, 징계를 받거나 심지어 블랙리스트에 오릅니다(방위 산업에서는 큰일입니다).
하지만 부품 데이터 시스템에 그래프 이론을 적용하면 이 문제를 피해 갈 수 있습니다. 일부 PDM은 실제로 이를 기본 기능으로 갖추고 있고(Oleg Shilovitsky의 OpenBOM, Yoann Maingon의 Ganister가 그렇습니다. 둘 다 똑똑한 사람들이니 이들의 제품을 써 보세요!), 덩치만 크고 둔한 어떤 PDM 위에서든 이런 네트워크 이론을 보고서 계층으로 얹어 쓸 수 있습니다.
예를 들면 다음과 같습니다.
(예전에 쓴 슬라이드의 Asciidoc 표입니다. 죄송합니다)
[1] 이런 접근법과 사촌지간인 설계 구조 행렬(Design Structure Matrix, DSM)과 다중 영역 행렬(Multiple-Domain Matrix, MDM)은 제외하고 하는 말입니다. MIT의 Steven Eppinger와 Tyson Browning이 쓴 Design Structure Matrix Methods and Applications도 참고하세요.
그래프는 정말 대단합니다. 구글 검색을 움직였던(지금도 어느 정도는 그렇고요) PageRank [1], 추출식 텍스트 요약용 TextRank [2], 이웃 탐지용 Louvain [3] 모두 그래프를 씁니다. 신뢰 전파(belief propagation), 마르코프 군집화, A* 같은 다른 알고리즘도 수없이 많고요. 그러니 네, 배우세요.
[1] https://en.wikipedia.org/wiki/PageRank
[2] https://aclanthology.org/W04-3252.pdf
[3] https://en.wikipedia.org/wiki/Louvain_method
1년 전만 해도 생각조차 못 했던 문제가 있습니다. 이 책을 사람이 썼는지 아닌지 따져야 한다는 점입니다.
이 저자는 그런 의심을 받을 만한 일을 전혀 하지 않았습니다. 그래도 공개된 지 얼마 안 된 새 책(이 글의 가장 이른 버전이 2026년 봄입니다)을 온라인에서 보면, 이게 "AI로 보강"됐거나 AI가 쓴 글일 수 있다는 생각에 경계부터 하게 되는 감정을 떨칠 수 없습니다.
이런 기분이 싫고, 예전에 이런 글을 보면 느꼈던 설렘이 사그라듭니다.
그건 그렇고, 저자가 AI 없이 직접 썼다면 박수를 보내고, 그 성취를 축하합니다!
기분이 좀 나아지실지 모르겠지만, 저는 이 저자를 10년 넘게 개인적으로 알고 있고, 그는 사람이고 뛰어난 선생이기도 합니다. 이 책을 본인이 직접 썼다고 거의 확신합니다. (이 말로 완전히 안심하시려면 물론 저를 믿으셔야 하지만, 조금이라도 도움이 될까 싶어 신뢰 한 표를 보탭니다.)
이 책은 그렇다 치고, 글이 더 이상 사람의 사고를 보여 주는 확실한 증거가 아니라는 점은 LLM 시대에서 제가 가장 싫어하는 부분 중 하나입니다. 그 서글픔에 정말 공감합니다.
분명히 해 두고 싶은데, 저는 저자가 AI를 썼다고 의심할 이유가 전혀 없습니다. 이제 이런 의심을 전반적으로 품어야 한다는 사실이 저자에게 오히려 좀 속상할 정도입니다. 그런 의심을 살 만한 일을 하지 않은 저자에게는 불공평하지만, 지금 우리가 사는 세상이 그렇습니다.
제가 이런 감정을 말하는 건 저자가 의심받을 만한 일을 해서가 아닙니다. 이 포럼에서는 "AI면 뭐 어때서?"라는 말을 흔히 하는 분들이 있는데, 업계를 둘러싼 이런 감정을 꺼내 놓아야 대화가 되고, (바라건대) 다른 분들도 책을 쓰면서 AI를 쓸지 한 번 더 생각해 볼 수 있기 때문입니다.
저는 이 책을 읽고 싶고 읽을 목록에도 넣었습니다. 저자를 보증해 주신 덕분에 확실히 도움이 됩니다. 제 안에 있는 근본적인 문제(순전히 제 문제이긴 합니다)는, 이 분야를 전혀 모르다 보니 이 분야의 전문가도 알지 못해서 사람의 보증에 의존하게 된다는 점입니다.
글을 사람이 썼든 기계가 썼든 상관없지만, AI는 읽는 사람을 지치게 하는 글쓰기 방식이 있어요. 요점 주위를 쓸데없이 빙빙 도는데, 요즘 들어 예전에는 더 참아 주던 글에도 몹시 참을성이 없어졌어요. AI 슬롭 같은 글이 보이는 순간 페인트 마르는 걸 구경하며 시간을 낭비하는 기분이 들어서 그냥 버려요.
틀린 경우도 많고요.
그리고 제가 쓰는 돈은 토큰이 아니라 사람에게 갔으면 해요.
그럼 이야기를 해 보죠. AI면 뭐 어때서요? 따져야 할 건 정확성과 좋은 교육 방식이어야 하지 않나요? 보증해야 할 것도 늘 그런 것들이어야 하지 않나요? 정말 잘 만들었다면(예를 들어 혼자서는 못 그렸을 더 나은 삽화를 생성할 수 있었다면), 왜 굳이 한 번 더 생각해야 하죠?
저자는 자기 이름과 평판을 걸었어요. 훌륭한 작업물이면 훌륭한 작업물이고, 슬롭이면 슬롭이죠.
적어도 지난 5년 동안 Amazon.com은 임의의 문자열로 찍어낸 일회용 브랜드명으로 완전히 뒤덮였어요. 화이트라벨 상품을 파는 브랜드들인데, 실적이 나쁘면 버려지고 교체되고, 반응이 오는 것만 순위를 올라가요.
2026년에는 책, SNS 글, 심지어 학술 논문의 "저자"에게도 똑같은 일이 벌어지지 않을 거라고 보세요? 이미 널리 알려지고 신뢰받는 평판이 있는 게 아니라면, 누가 평판을 걸었는지는 중요하지 않아요.
글쎄요, 이 사람은 자기 웹사이트에서 CMU 수학 박사 학위가 있고 여러 주립대학에서 이 주제를 가르쳤다고 밝히고 있어요. 그게 사실인지 어느 정도 파 볼 수 있고, 그 기관들을 잘 모른다면 거기 이름이 오른 기관들의 평판에 기댈 수 있죠.
예전부터 평판이 작동하던 방식 그대로예요. 사람들은 서로 연결되어 있고, 서로를 보증해 주고, 보증에는 어느 정도 전이되는 무게가 실려요(그래프 이론으로 모델링할 수 있겠네요). 이건 AI와 아무 상관이 없어요. 맞아요, Amazon은 평판이 전혀 없고 끊임없이 바뀌는 "브랜드"로 가득해요. 하지만 그건 오늘 처음 알게 됐더라도 찾아볼 수 있는 일관된 평판이 있는 사람이나 회사와는 다른 얘기예요. Amazon에도 AHIKJASFDIUHER 같은 걸 사기 싫으면 삼성이나 에이수스 같은 브랜드가 있고요.
LLM 이후 시대의 차이는 가짜 신원이 일관된 배경과 온라인 존재감을 극히 적은 노력과 사람의 개입만으로, 원하는 만큼 몇 번이고 만들어 낼 수 있다는 거예요.
웹사이트에 있는 이력서를 슬쩍 훑어보고는 그 정도면 이번에는 의심을 거둬도 되겠다고 판단하신 거잖아요. 하지만 신뢰를 쌓겠다고 점점 더 깊이 파고드는 데는, 어떤 의도를 관철하려는 악의적인 쪽이 들여야 하는 시간과 노력보다 더 많은 시간과 노력이 들어요. 비대칭이죠.
신원을 지어내서 유명 대학 박사라고 주장하고, 그걸 남의 웹사이트(예컨대 그 대학 사이트)에 올릴 수는 없어요. ChatGPT에게 물어봤어요.
그랬더니 그 주장을 뒷받침하는 .edu 사이트 링크를 줬어요(예를 들어 박사 학위자 명단에 올라 있더군요[0]). 해당 기관이 이 사이트를 링크하느냐고 물었더니, 본인 개인 사이트가 이 사이트를 링크하고[1], CMU가 그의 개인 사이트를 링크한다고[2] 하더라고요. 오히려 요즘은 이런 걸 확인하기가 훨씬 쉬워요. 30초 걸렸어요.
[0] https://www.cmu.edu/math/grad/phd/past-recipients.html
[1] https://misha.fish/
[2] https://www.math.cmu.edu/users/math/mlavrov/
노먼 쿡은 시대를 수십 년 앞서 갔어요. (팻보이 슬림은 그저 변곡점 복권에 우연히 당첨된 예명이었을 뿐이고요.)
얼마 전에 HN에서 중국 기업들이 엉터리 정보로 Amazon에 입점해서 연락할 방법도 없고 잘못을 해도 책임을 물을 이론적 수단조차 없다는 불만을 확인해 본 적이 있어요. 그 댓글이 걸어 둔 상품 링크로 가 봤더니, 그 상품을 파는 회사의 등록 사업장 주소(Amazon에 나와 있었어요)가 누가 봐도 가엾은 주인의 자택 주소였어요.
이 질문은 이 글타래 다른 곳에서 답했습니다. 링크는 여기 있습니다. https://news.ycombinator.com/item?id=50273553
그건 사실 아무 답도 안 되잖아요. 자기 "이론"에 엄청난 시간을 기꺼이 쏟는 사람 괴짜도 세상에 수두룩해요. 사람도 실수하고요. 원본 자료를 평가할 방법이나 신뢰할 만한 누군가의 보증이 없다면, AI가 있다고 달라지는 건 없어요. 보증이 있다면(예를 들어 테런스 타오가 어떤 AI 책이 아주 잘 만들어졌다고 하거나, 집필에 AI를 썼다고 공개한 자기 책을 내놓는다면) 왜 AI라는 이유로 버리겠어요?
저는 원 댓글 작성자는 아니지만, 이 질문에 대한 제 답, 적어도 답 중 하나를 말씀드릴게요.
이 책은 사람이 쓴 것으로 소개되어 있어요. (이 경우에는 제가 마침 아는 사람이라 불만에 또 다른 차원이 더해지는데, 그건 아니라고 치고 상상해 보죠.) 언젠가는 책 맨 위에 사람 이름을 붙여도 그 사람이 책 속 글을 썼다는 암시를 주지 않는 세상에 살게 될지도 모르겠어요. 그것도 다른 이유로 슬플 테지만, 어쨌든 지금은 그런 세상이 아니에요. 그러니 지금은 책에 사람 이름을 넣으면 그 사람이 그 책을 썼다고 주장하는 거예요. 사실이 아니라면 거짓말을 하는 거고, 저도 대부분의 사람처럼 거짓말당하는 게 싫어요.
이름을 올린다는 게 왜 모든 글자를 직접 썼다는 뜻이어야 하죠? 그냥 자기 평판을 걸고, 누가/무엇이 글을 썼든 이 안의 내용을 보증한다고 말하는 것일 수도 있잖아요. 그렇게 보면 우리는 지금까지처럼 내용과 교육 방식 등을 평가하면서 좋고 나쁜 내용과 교육 방식을 저자와 연결해 둘 수 있고, 그 저자의 이름을 보면 무엇을 기대해야 할지 (개별 문장을 누가 썼든) 알 수 있어요.
저는 영화감독을 대하는 방식에 더 가까운 걸 상상해요. 마이클 베이와 쿠엔틴 타란티노를 보면, 이 사람들이 각본을 쓰고 촬영 구도를 하나하나 짜고 의상을 디자인했다고는 생각하지 않아요. 하지만 그 모든 것을 갖추는 데 손을 댔고, 결국 모든 게 그들 특유의 도장이 찍혀 나온다는 건 알죠.
지금의 저자 개념과 다른 새로운 방식의 저자 개념을 제안하시는 거네요. 그게 지금 체제보다 나은지는 논쟁할 만한 주제입니다. 저는 아니라는 쪽이지만, 어느 쪽이 분명히 맞다고 주장하지는 않습니다.
하지만 새 체제가 더 낫다고 보시든 아니든, 그건 현재의 체제가 아닙니다. 쓰지 않은 책에 이름을 올려 거짓말을 하는 것인지는, 아직 일어나지도 않은 저자 개념의 가상의 미래 변화에 달려 있을 수 없습니다.
"현재의" 혹은 "우리의" 체제가 무슨 뜻이에요? 그건 전적으로 당신의 해석이잖아요. 우리는 편집자부터 대필 작가까지 "저자가 아닌 정도"의 스펙트럼을 늘 갖고 있었어요. AI 모델도 마찬가지예요. 아주 구체적으로 지시하며 쓸 수도 있고(기본적으로 편집자처럼, 혹은 삽화 같은 걸 외주 맡기는 식으로), 손은 놓고 승인만 할 수도 있죠.
편집자는 자기가 저자라고 말할 수 없어요.
그건 AI 때문에 생긴 일도 아니고, 우린 이미 그런 세상이 아니에요. 대필은 수백 년 전부터 있었어요.
저도 그게 싫어요! 부정직한 일이라고 생각하고, 대필 작가를 쓴 사실이 드러나면 어떤 공인도 재기할 수 없을 만큼 망신당하는 세상이면 좋겠어요. AI 때문에 사정이 더 나빠진 것도 싫고요. 그래도 대필이라면 의심해 볼 만한 분야(정치인, 유명인 전기)가 있기는 한데, 대부분의 분야에서는 의심조차 하지 않게 되잖아요.
하지만 우리는 지금 바로 그런 세상에 살고 있어요.