최대 공통 에지 하위 그래프

두 개의 $그래프{\displaystyle }$ G ${\displaystyle$ G$}$ 및 $G$ ${\displaystyle {\prime }^{}}$ ${\$을$($를) 고려할 때 최대 공통 에지 하위 그래프 $문제$는 G ${\displaystyle$ G$}$의 하위 그래프와 $G{\displaystyle {}^{}}$ ${\displaystyle {\prime }^{}}$ ${\$의 하위 그래프 모두에 대해 이형인 가장자리가 가능한$$ 한 많은 그래프 $H{\displaystyle }$ ${\\\displaystystystytype H}$을 찾는 문제다$.$

일반 그래프의 최대 공통 에지 서브그래프 문제는 서브그래프 $이형화$의 일반화인 만큼 NP-완전하다: $G{\displaystyle }$ ${\displaystyle G$$}$의 최대 공통 에지 서브그래프에서$$ G {\displaystyle $G$$}$이(가) $다른{\displaystyle }$그래프$$G {\$displaystyty$ G}의 하위 그래프에 이형성이 있는 경우에만$$ 해당된다$$.$H{\displaystyle }$ {\$displaystyle H}$과(와$)$ 동일한 수의 가장자리. 최대 공통 가장자리 하위그래프 문제에 $대한{\displaystyle }$$$ 두$$입력 G {\$displaystyle G}$과(와$)$ ^[1]$display$ {\displaystyle $G'}$이(가) 동일한 수의 꼭지점을 가져야 하는 경우가 아니라면 문제는 APX-hard이다$.$

참고 항목

• 최대 공통 서브그래프 이형성 문제
• 서브그래프 이형성 문제
• 유도 서브그래프 이형성 문제

참조

이 알고리즘이나 데이터 구조와 관련된 기사는 단조롭다.위키피디아를 확장하여 도울 수 있다.

• v
• t