Максималды жалпы жиек субографиясы - Maximum common edge subgraph

Екі графиктер ${ displaystyle G}$ және ${ displaystyle G '}$ , максималды кеңейтілген шеттік ақаулық графикті табу проблемасы болып табылады ${ displaystyle H}$ мүмкіндігінше көп шеттермен изоморфты екеуіне де подограф туралы ${ displaystyle G}$ және ${ displaystyle G '}$ .

Жалпы графиктердегі максималды кеңейтілген субографиялық проблема болып табылады NP аяқталды өйткені бұл жалпылау субографиялық изоморфизм: график ${ displaystyle H}$ басқа графиктің субграфына изоморфты болып табылады ${ displaystyle G}$ егер және егер максималды ортақ жиек субографиясы болса ғана ${ displaystyle G}$ және ${ displaystyle H}$ сияқты жиектер саны бар ${ displaystyle H}$ . Екі кіріс болмаса ${ displaystyle G}$ және ${ displaystyle G '}$ максимумға дейінгі жалпы шеттік проблемаға дейін бірдей шыңдардың болуы талап етіледі, мәселе мынада APX-қиын.^[1]

Сондай-ақ қараңыз

Пайдаланылған әдебиеттер

^ Бахьенсе, Л .; Маник, Г .; Пива, Б .; de Souza, C. C. (2012), «Максималды кең таралған субографиялық проблема: көпсалалы тергеу», Дискретті қолданбалы математика, 160 (18): 2523–2541, дои:10.1016 / j.dam.2012.01.026.

Бұл алгоритмдер немесе мәліметтер құрылымы - қатысты мақала а бұта. Сіз Уикипедияға көмектесе аласыз оны кеңейту.

[1] Бахьенсе, Л .; Маник, Г .; Пива, Б .; de Souza, C. C. (2012), «Максималды кең таралған субографиялық проблема: көпсалалы тергеу», Дискретті қолданбалы математика, 160 (18): 2523–2541, дои:10.1016 / j.dam.2012.01.026.

[1]