그래프이론
그래프 이론 혹은 네트워크 이론은 이산수학의 한 분야로써 대단히 중요하게 다뤄졌으며 근래 들어서는 끝도 없는 응용을 보여주며 그 영역을 넓혀나가고 있다. 태생적으로 시각화에 유리하며 알고리즘 친화적이다보니 컴퓨터 공학이나 데이터 과학과도 가까운 분야인데, 아이러니하게도 증명 과정에 수식보다는 말이 많은 경우가 제법 있어 오히려 수학도들이 까다로워하는 과목이기도 하다. 호불호를 떠나 공부해서 시간 낭비할 일은 절대 없고, 선수과목이랄 것도 딱히 없다보니 학부 신입생에게도 부담없이 권할 수 있다.
기초
스펙트럴
토폴로지
결정론적 그래프
네임드 그래프
경로 문제
4색 문제
비결정론적 네트워크
랜덤 네트워크
- 그래프의 패밀리와 프로퍼티 $2^{\binom{n}{2}}$, $\mathscr{G}_{n,m}$
- 랜덤 네트워크 $\mathbb{G}$
- 에르되시-레니 모델 $\mathbb{G}_{n,m}$
- 스케일 프리 네트워크
- 유클리드 네트워크
중심성
실습
- 🔒(24/10/07) 그래프의 레이아웃
- Gephi: 그래프 시각화 및 분석 프로그램
- NetworkX: 그래프 분석을 위한 파이썬 패키지
- 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
전체 포스트
- 수학에서의 그래프와 네트워크
- 그래프의 아이소멀피즘
- 그래프 이론에서의 차수
- 악수 렘마 증명
- 악수 딜레마 증명
- 그래프의 행렬 표현
- 그래프의 집합 표현
- 서브 그래프
- 그래프 컴플리먼트
- 널 그래프와 컴플리트 그래프
- 레귤러 그래프
- 이분 그래프
- 무한 그래프
- 그래프 이론에서의 워크, 트레일, 패스, 사이클
- 그래프에서의 거리, 네이버후드, 지름, 둘레
- 그래프의 오리엔테이션
- 쾨닉의 정리 증명
- 오일러 그래프
- 쾨니히스베르크의 다리 문제와 풀이
- 플뢰리 알고리즘 증명
- 해밀톤 그래프
- 그래프 이론에서의 디락 정리 증명
- 트리 그래프
- 레이블 트리와 케일리 정리
- 에르되시-갈라이 정리
- 하벨-하키미 알고리즘 증명
- 그래프 컬러링과 브룩스 정리
- 그래프의 호메오멀피즘
- 평면 그래프와 쿠라토프스키 정리
- 오일러의 다면체 정리 증명
- 그래프의 k-연결성과 멩거 정리
- 기하적 듀얼 그래프
- 추상적 듀얼 그래프
- 심플 평면 그래프의 성질
- 그래프 이론에서 지도의 정의
- 5색 정리 증명
- 4색 지도 문제
- 영인자 그래프
- 앤더슨-리빙스톤 정리 증명
- 완벽 그래프
- 그래프의 패밀리와 프로퍼티
- 랜덤 그래프
- 에르되시-레니 모델
- 길버트 모델
- 네트워크에서 차수의 분포
- 스케일 프리 네트워크
- 청-루 피트니스 모델
- 바라바시-알버트 모델
- 네트워크 이론에서의 허브 노드
- 그래프(네트워크) 시각화 및 분석 프로그램 Gephi
- 파이썬의 그래프(네트워크) 분석 패키지 NetworkX
- 줄리아의 그래프(네트워크) 분석 패키지 Graphs.jl
- NetworkX에서 GEXF 파일 읽고 쓰기
- 유클리드 그래프
- 네트워크 이론에서의 차수 중심성
- 네트워크 이론에서의 스트레스 중심성
- 네트워크 이론에서의 매개 중심성
- 네트워크 이론에서의 근접 중심성
- 네트워크 이론에서의 고유벡터 중심성
- 하이퍼그래프의 정의
- 수학에서 그래프의 레이아웃
- 그래프와 그래프 사이의 스펙트럴 거리
- 그래프와 그래프 사이의 편집 거리