Maksymalny podgraf wspólnej krawędzi

pod uwagę dwa wykresy $i$ , maksymalnym $problemem$ podgrafu wspólnej krawędzi jest problem ze znalezieniem wykresu z największą liczbą krawędzi, który $izomorficzny$ a podwykres sol ${\ displaystyle G}$ i podwykres $G'}$ .

Maksymalny problem podgrafu wspólnej krawędzi na grafach ogólnych jest NP-zupełny $,$ ponieważ jest uogólnieniem izomorfizmu podgrafu : wykres jest izomorficzny z podwykresem innego wykresu $,$ gdy maksimum podwykres wspólnej krawędzi $taką$ ma samą liczbę krawędzi jak $\ displaystyle H$ $}$ . $G$ dwa wejścia i ${\ displaystyle G'}$ do maksymalnego problemu podgrafów ze wspólną krawędzią musi mieć taką samą liczbę wierzchołków, problem jest APX-trudny .

Zobacz też