Stellen Sie sich vor, wir haben zwei Gruppen, Frauen und Männer. Jede Frau hat eine Gruppe von Männern, die sie interessiert. Wir vertreten ihr Interesse als Kanten in einem zweiteiligen Graphen.Bipartite Sitzordnung auf runden Tischen
Jetzt versuchen wir, alle in runden Tischen einzurichten, zum Beispiel, wenn Sie um den Tisch herumgehen, wird jeder Platz zwei Sitze von einem Paar mit einer Verbindung besetzt werden. Wenn Sie zum Beispiel im Uhrzeigersinn um den Tisch herumgehen, könnte ein Sitz eine Frau haben, die an einem Mann interessiert ist, der auf dem nächsten Sitzplatz sitzt, und das wird auch das Interesse der Frau sein, die auf dem nächsten Sitz sitzt, und so her. Jeder Tisch muss mindestens eine Anzahl k Gäste haben.
Ich versuche, einen Algorithmus mit max Fluss zu entwerfen, diese Anforderungen zu erfüllen, und ich würde wirklich einige Ideen
Es ist unklar, was die tatsächlichen Einschränkungen hier sind. * Müssen * die beiden Sitze neben einem Frauensitz von Männern besetzt sein, die sie mag? Wenn ja, was passiert, wenn eine Frau nur einen oder keinen Mann mag? Was passiert, wenn 2 Frauen nur die gleichen 2 Männer mögen, aber k> = 5 bedeutet, dass diese 2 Männer nicht neben beiden Frauen sitzen können? –