그래프이론

그래프 이론 혹은 네트워크 이론은 이산수학의 한 분야로써 대단히 중요하게 다뤄졌으며 근래 들어서는 끝도 없는 응용을 보여주며 그 영역을 넓혀나가고 있다. 태생적으로 시각화에 유리하며 알고리즘 친화적이다보니 컴퓨터 공학이나 데이터 과학과도 가까운 분야인데, 아이러니하게도 증명 과정에 수식보다는 말이 많은 경우가 제법 있어 오히려 수학도들이 까다로워하는 과목이기도 하다. 호불호를 떠나 공부해서 시간 낭비할 일은 절대 없고, 선수과목이랄 것도 딱히 없다보니 학부 신입생에게도 부담없이 권할 수 있다.

기초

• 그래프와 네트워크
  • 아이소멀피즘
  • 호메오멀피즘
• 하이퍼그래프의 정의

스펙트럴

• 그래프의 행렬 표현
• 차수 $\deg$
  • 악수 렘마
  • 악수 딜레마
• 그래프와 그래프 사이의 스펙트럴 거리

토폴로지

• 그래프의 집합 표현
  • 서브 그래프
• 거리, 네이버후드, 지름, 둘레 $d$, $N$, $\text{diam}$, $\text{girth}$
• 그래프 컴플리먼트 $\overline{G}$

결정론적 그래프

네임드 그래프

• 널 그래프와 컴플리트 그래프 $K_{n}$
• 레귤러 그래프
• 이분 그래프 $G(A,B)$
• 무한 그래프
  • 쾨닉의 정리
• 에르되시-갈라이 정리
• 하벨-하키미 알고리즘
• 트리 그래프
  • 레이블 트리와 케일리 정리
• 영인자 그래프
  • 앤더슨-리빙스톤 정리
• 완벽 그래프

경로 문제

• 워크, 트레일, 패스, 사이클
  • 그래프의 오리엔테이션
• 오일러 그래프
  • 쾨니히스베르크의 다리 문제와 풀이
  • 플뢰리 알고리즘
• 해밀톤 그래프
  • 디락 정리

4색 문제

• 평면 그래프와 쿠라토프스키 정리
  • 오일러의 다면체 정리
  • 심플 평면 그래프의 성질
• 그래프 컬러링과 브룩스 정리
• 그래프의 k-연결성과 멩거 정리
• 기하적 듀얼 그래프
• 추상적 듀얼 그래프
• 그래프 이론에서 지도의 정의
• 5색 정리
• 4색 지도 문제

비결정론적 네트워크

랜덤 네트워크

• 그래프의 패밀리와 프로퍼티 $2^{\binom{n}{2}}$, $\mathscr{G}_{n,m}$
• 랜덤 네트워크 $\mathbb{G}$
  • 차수의 분포
• 에르되시-레니 모델 $\mathbb{G}_{n,m}$
  • 길버트 모델 $\mathbb{G}_{n,p}$
• 스케일 프리 네트워크
  • 청-루 피트니스 모델
  • 바라바시-알버트 모델
• 유클리드 네트워크

중심성

• 허브 노드
• 차수 중심성
• 매개 중심성
  • 스트레스 중심성
• 근접 중심성
• 고유벡터 중심성

실습

• 그래프의 레이아웃
• Gephi: 그래프 시각화 및 분석 프로그램
• NetworkX: 그래프 분석을 위한 파이썬 패키지
  • GEXF 파일 읽고 쓰기
• Graphs.jl: 그래프 분석을 위한 줄리아 패키지

주요 참고문헌

• Albert, Barabási. (2002). Statistical mechanics of complex networks
• Barabási. (2016). Network Science
• Brouwer. (2011). Spectra of Graphs
• Frieze. (2015). Introduction to Random Graphs
• Newman. (2010). Networks: An Introduction
• Wilson. (1970). Introduction to Graph Theory