Maximální společný hranový podgraf - Maximum common edge subgraph

Vzhledem k tomu dva grafy ${ displaystyle G}$ a ${ displaystyle G '}$, maximální společný problém hranového podgrafu je problém najít graf ${ displaystyle H}$ s co největším počtem hran, což je izomorfní oběma a podgraf z ${ displaystyle G}$ a podgraf ${ displaystyle G '}$.

Maximální obecný problém s hranovým podgrafem na obecných grafech je NP-kompletní protože se jedná o zobecnění podgraf izomorfismus: graf ${ displaystyle H}$ je izomorfní s podgrafem jiného grafu ${ displaystyle G}$ právě tehdy, pokud maximální společný hranový podgraf z ${ displaystyle G}$ a ${ displaystyle H}$ má stejný počet hran jako ${ displaystyle H}$. Pokud však nejsou dva vstupy ${ displaystyle G}$ a ${ displaystyle G '}$ k maximálnímu společnému problému hranového podgrafu se vyžaduje, aby měl stejný počet vrcholů, problém je APX-tvrdé.^[1]

Viz také

• Maximální běžný problém izomorfismu podgrafu
• Problém izomorfismu podgrafu
• Problém isomorfismu vyvolaného podgrafu

Reference

Tento algoritmy nebo datové struktury související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.