Ansatz: Mengen, Relationen, Permutationen (oder sowas ähnliches)

[Don P]

Hallo,

Für 6 Knoten schreibst du:

Momentan habe ich:
A x B = {(1,2),(1,3),(1,4),(2,3),(2,5),(2,6),(3,4),(3,5),(4,2),(4,6),(5,1),(5,4),(5,6),(6,1),(6,3)}

und suchst Lösungen, so dass

jedes Element aus A GENAU EINEM Element aus B zugeordnet ist.
Dafür gibt es bei der gegebenen Menge AxB mehrere Möglichkeiten.

Ja, aber die Ergebnismengen haben dann jeweils nur n Elemente ("jedes Element aus A GENAU EINEM Element aus B zugeordnet").

So langsam dämmert's mir:

Aus der gegebenen Menge AxB mit Mächtigkeit n*(n-1)/2 willst du also alle Teilmengen mit jeweils der Mächtigkeit n erstellen, bei denen "jedes Element aus A GENAU EINEM Element aus B zugeordnet ist". Die restlichen Kanten, die für die Vollständigkeit jeweils noch nötig wären, interessieren dich dann nicht mehr, richtig?

Da würde ich klein anfangen mit nur 3 oder 4 Knoten und einen *allgemeinen* Algorithmus suchen, der damit klar kommt. Sehr wahrscheinlich schafft er die Aufgabe dann auch mit mehr Knoten...

Gruß, Don P