해밀턴 회로 만들기

두 집합 $A , B$ 를 $A = \left\{ v _{1} , v _{2} , v _{3} , v _{4} , v _{5} \right\} , B = \left\{ v _{6} , v _{7} , v _{8} \right\}$ 이라 하면, 그래프의 접들은다른 집합의 점들끼리만 연결되어 있는 상태이다. $A _{1} - B _{1} - A _{2} - B _{2} - A _{3} - B _{3} - A _{4}$로 연결할 수 있으므로 $A _{1} - B _{1} - A _{2} - B _{2} - A _{3} - B _{3} - A _{4} - A _{5} - A _{1}$ 의 해밀턴 회로가 되려면 최소 $2$개의 변을 추가해야 한다. $i )$ $A$의 하나의 점에서 $A$의 다른 두 개의 점을 연결하는 경우 $5 \times _{4} C _{2}$$= 30$ (가지) 예) $v _{1} - v _{2}$연결, $v _{1} - v _{3}$ 연결 $ii )$ $A$ 의 점들끼리 연결하는 선분을 두 개 추가하는 경우 $\displaystyle \frac{{} _{5} C _{2} \times _{3} C _{2}}{2 !} = 15$(가지) 예) $v _{1} - v _{2}$연결, $v _{3} - v _{4}$ 연결 $i ) , ii )$ 에서 , 그래프 $H$의 개수는 $45$개다.