Schlagwort: edgecoloring

Hallo zusammen,

hier eine verspätete Einladung für unser Mann-o-Meter-Treffen heute Abend.
Zum Ausgleich ein paar poetische Worte: Amor erwacht und richtet seinen Pfeil auf zwei Personen, die sich sofort unsterblich ineinander verlieben [1]. Wer hier die Ankündigung für einen Werwolf-Spieleabend wittert, muss enttäuscht werden. In gewisser Weise machen wir allerdings schon einen Spieleabend (zumindest sehen es manche Leute so): Ein Speed-„Dating“-Abend.
Zumindest nenne ich das mal so, weil mir kein besserer Name einfällt. Das Ganze läuft ab wie man es aus Filmen kennt: Wir werden in Zweier-Paare eingeordnet [2], haben ein paar Minuten, um miteinander zu reden, dann klingelt der Timer und es gibt neue Zweier-Paare. Dadurch lernen wir uns alle mal auf eine andere Art kennen (als dauernd diese Gruppengespräche). Wer jetzt denkt: „Uh, aber ich habe doch schon einen Partner!“ oder „Uh, ich suche gerade gar nicht nach einem!“, dem sei gesagt: Du darfst trotzdem teilnehmen, denn wir wollen uns in erster Linie besser kennenlernen und das kann man auch freundschaftlich.

Ihr seid also alle herzlich willkommen, ich freue mich auf euch heute Abend ab 20 Uhr im MoM. Kommt bitte einigermaßen pünktlich, weil Zuspätkommer den Ablauf durcheinanderbringen [3].

Bis heute Abend
Euer Mark

P.S.: Übrigens, wer keinen Kalender hat (oder nicht reinschaut oder selektive Wahrnehmung das weggefiltert hat): Am 14. Februar ist Valentinstag. Ein Schelm, wer die Vorstellungsrundenfrage erahnt ;).

[1] Der Realismus dieser Aussage ist noch zu klären, allerdings ist es ein eher schlechtes Zeichen, dass der Satz aus einem Spiel kommt, in dem sich auch Werwölfe, Hexen und Seher fröhlich und unfriedlich tummeln.

[2] Im Gegensatz zu den Heten ist es bei uns deutlich schwieriger, alle „sinnvollen“ Kombinationen in der minimalen Anzahl an Runden stattfinden zu lassen. (Bei Heten gibt es Männer und Frauen, da kann man z.B. die Männer einfach auf einen Platz setzen und die Frauen für das nächste Gespräch zum nächsten Mann wandern lassen. Bei uns geht das nicht, weil die „Sitzenden“ ja auch miteinander sprechen wollen.) So, wer Bock hat auf Nerdigkeit, darf weiterlesen, für alle anderen das Wichtigste: Mathe ist doch praxisrelevant und eine tolle Studienwahl!

Nerd-Teil (ihr wurdet gewarnt!): Hier ist etwas Graphentheorie notwendig. Wir können das Problem als minimales Kantenfärbungsproblem modellieren, allerdings nicht auf einem bipartiten (à das wären die Heteros, wo alles leicht und in Polynomialzeit geht), sondern auf einem vollständigen Graphen, was dieses Problem NP-vollständig macht. Glücklicherweise sagt Vizing’s Theorem, dass die minimale Kantenfärbung entweder den Grad D des Graphen oder aber D+1 Farben hat. Und für letzteres existieren schnelle Algorithmen (vrgl. Misra & Gries https://www.cs.utexas.edu/users/misra/psp.dir/vizing.pdf). D.h. wir haben vielleicht eine Runde mehr als die optimale Rundenanzahl wäre, aber dafür können wir eine Lösung ausrechnen, die gut skaliert). Ich nenne unseren Anwendungsfall mal das „Gay speeddating problem“
Addendum: Für den Spezialfall eines vollständigen Graphen existieren einfache und stärkere Algorithmen (vrgl. Baranyai’s theorem), allerdings macht uns das den Übergang zum „online gay speeddating problem“, bei dem Leute (und damit auch Kanten) hinzu und wegkommen können, schwieriger.

[3] Nerd-Kommentar 2: Dies wäre das online gay speeddating problem. Und mit online ist nicht Internet gemeint 😊.