이언배 연구노트

그래프가 "잘 연결되어있다", "더 연결되어있다" 란 무슨 의미일까. 5.1 Connectivity Definition.Seperating set, vertex cut: a set $S \subseteq V(G)$ that $G-S$가 하나 이상의 component를 갖게 하는. 빼면 component가 늘어나게 되는 애들.k-connected: $k$개보다 vertex가 많고, 모든 seperating set 이 사이즈가 최소 $k$다. 뭘 떼내려면 최소 $k$개 이상의 vertex는 뽑아야 한다.Connectivity of $G$ : G가 k-connected가 되게 하는 최대의 $k$.  Fact.$K_n$의 경우, separating set 이 없다. 뭘 뽑아도 다 연결되어있음. 하지만 maxim..