Rigidity

다음과 같은 철골구조에서 RIGID(튼튼)한 것과 그렇지 않은 것 1)구별하는 방법과 제시된 cross bar의 갯수가 2)최소로 필요한 갯수인지 알 수 있는 방법은?

1) RIGID 구별 방법

 1. 철골구조의 row와 column을 bipartite graph로 나타낸다.

 2. bipartite graph의 component들이 연결이 된다면 RIGID 하고 그렇지 않다면 NOT RIGID하다.

 

2) RIGID를 위해 필요한 cross bar의 최소 갯수

 1. bipartite graph에서 edge 수가 가장 적은 경우를 찾는 문제로 치환할 수 있다.

 2. 결국, bipartite graph에서 spanning tree 찾기 문제다.