문서의 임의 삭제는 제재 대상으로, 문서를 삭제하려면 삭제 토론을 진행해야 합니다. 문서 보기문서 삭제토론 그래프(이산수학) (문단 편집) ==== 연결의 정도 ==== 그렇다면 연결된 그래프의 연결이 어느정도로 강한지를 정의할 수 있는 방법은 무엇일까. 이는 얼마나 많은 점 또는 모서리를 제거해야 연결이 사라지는지로 나타낼 수 있다. 이러한 점들의 집합을 separating set이라고 부르며, cut vertex는 오로지 하나의 vertex만을 지니는 separating set을 뜻한다. 이때 연결그래프 G의 연결성을 k(G) 카파 G라고 하는데 이는 separating set의 cardinality의 최솟값을 의미한다. 만약 k(G) >= k면 G을 k-connected하다고 부른다. 즉 점을 하나만 제거해도 연결성이 제거된다면 1-connected, 2개를 제거해야 한다면 2-connected라고 하는 것. 이는 당연히 모서리를 통해서도 정의가 가능한데, 모서리의 경우에는 disconnecting set이라 하며, cutset은 disconnecting set의 극소이며, bridge는 하나의 모서리를 가진 cutset을 뜻한다. 여기서 극소라 하면, 어떤 그래프에서 몇몇 모서리만을 지정하고, 이 모서리중에서 그래프를 분리시킬 수 있는 최소의 모서리들을 뜻하기 때문에, 전체 그래프에 해당되는 개념이 아니다. 여기서는 연결성을 Λ(G) 람다 G라고 하며, Λ(G) >= k면 G를 k-edge-connected이라고 정의한다.저장 버튼을 클릭하면 당신이 기여한 내용을 CC-BY-NC-SA 2.0 KR으로 배포하고,기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다.이 동의는 철회할 수 없습니다.캡챠저장미리보기