--Network flow
----예시)무한히 공급되는 수도에서 싱크대까지 물을 대는데 캐파가 정해진 파이프에서 최대한으로 흐를수 있는 양은 얼마일까?
----예시)소셜 네트워크에서 개인이 메시지를 보낼수있는 양이 제한될 때 얼마나 많은 용량을 준비해야 어떤상황에도 대비할수 있을까?
----특징
-----방향성이 있는 가중치 그래프
-----전송 가능양은 엣지에 정해진 용량만큼만 보낼수 있다
-----손실이 없다는 가정하에 인입과 도착한양의 flow는 보존된다
--ford-fulkerson algorithm
----모든 엣지에서 사용하지 않은 용량이 있는 엣지를 탐색하는 알고리즘
--residual network
----네트워크상에서 얼마나 많은 용량이 네트워크에 남았는지 확인한다
--intution
----원본 네트워크에 flow가 없을 때 용량 잔존량
----방향성 그래프에서 흐르는양을 제어하기 위해 흐르는 방향의 반대방향으로 flow를 조절해서 용량을 조정
--augmentation / augmenting path
----잔종량을 가지고 원본그래프보다 많은양을(잔존량을 다른곳으로 이동시키며) 전송하게 해준다
Maximum pipatite matching
--definition 정의
----2분법 그래프로서 인접 노드는 다른색을 칠하며 그룹을 나누는 것.각노드는 1번씩만 선택이 가능하다
Bridge/weak ties,bridge detection
--bridge / localbridge
----브릿지:엣지중 제거하면 연결된 컴포넌트의 수가 증가하는 엣지, 해당 엣지를 제거하면 노드가 섬이 되어버린다
----로컬 브릿지: 제거하면 최소 경로가 2이상으로 증가하는 엣지
--strength of ties
----연결성의 강/약
-----소셜 네트워크상에서 강한 연결=친구관계 약한 연결=지인 관계 등으로 표현가능
--bridge and tie strength
----노드가 삼각형의 형상을 가질 때 모서리의 연결은 약한 연결을 의미한다
그림에서 A B C연결에서 푸른색의 연결라인이 약한 연결성을 의미한다
댓글 없음:
댓글 쓰기