Hallo,
was für Operationen habe ich eigentlich auf Graphen, damit ich eine Reduktion von einem Problem auf das andere Problem durchführen kann(Clique auf Independent). Was für Möglichkeiten gibt es noch ausser „alle Kanten wegnehmen“, „Knoten hinzufügen und mit allen anderen Knoten verbinden“,„Komplemenärgraphen bilden“ und deren Kombination. Gibt es noch mehr Operationen? Nein, oder?
Wenn ich z.B. von Clique auf Independent reduziere, dann muss ich ja nur den Komplemtärgraphen bilden, damit ich von dem Graphen, der eine Clique, der Grösse k bildet, einen Graphen bekomme, der eine unabhängige Menge von k Knoten hat.
Felix