Aufteilungsproblem < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 19:14 Di 12.06.2007 | | Autor: | schlomo |
| Aufgabe | | Es sollen eine Anzahl von Menschen in zwei Räume aufgeteilt werden. Dabei sollen Freunde nicht im selben Raum sein. Die Freundesbeziehungen sind als Paare gegeben. Entwickle eine Algorithmus der festellt, ob dies möglich ist, wenn ja, ausgiebt wie. |
Hat jemand einen Ansatz, wie man vorgehen könnte?
Ich habe überlegt alle Freundschaftspaar nacheinader durchzugehen und die Leute nach einer Überprüfung in den jeweils passenden Raum zu legen. Allerdings können hierbei am Anfang entscheidungen getroffen werden, die am Ende zu einem Problem werden.
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:41 Di 12.06.2007 | | Autor: | dormant |
Hi!
Dieses Problem ist in der Graphentheorie als das Perfect Matching Problem bekannt. Das ist ein Standard-problem und in der Literatur gibt es einge Algorithmen dazu. Ach ja - das Problem ist NP-schwer.
Gruß,
dormant
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 22:01 Di 12.06.2007 | | Autor: | schlomo |
Also ich habe mir gerade die Beschreibung vom Perfect Matching durchgelesen und finde nicht das es auf meine Aufgabe zutrifft.
Also bei folgenden Freunschaften:
a,b;c,b;d,b;c,e;d,f;
könnte man folgende Aufteilung bilden die die Voraussetzung erfüllt, aber nicht perfekt paart.
Raum1(a,c,d);Raum2(b,e,f)
Sehe ich das falsch?
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 02:57 Mi 13.06.2007 | | Autor: | dormant |
Hi!
> Also bei folgenden Freunschaften:
>
> a,b;c,b;d,b;c,e;d,f;
>
> könnte man folgende Aufteilung bilden die die Voraussetzung
> erfüllt, aber nicht perfekt paart.
>
> Raum1(a,c,d);Raum2(b,e,f)
>
> Sehe ich das falsch?
Ja. Es gibt 5 Kanten (die hast du ja oben angegeben mit Anfangs- und Endknoten). Das Matching a, c, d (bzw. b, e, f) überdeckt alle 5 Kanten, d.h. alle Kanten in dem Graphen enthalten einen der Knoten a, c oder d und zwischen a, c und d sind paarweise mit keiner Knate verbunden => perfect matching.
Ein perfect matching hat immer eine gerade Anzahl an Knoten und die kann man in zwei Reihen aufstellen, s.d. zwei Knoten, die in einer Reihe sind, durch keine Kante verbunden sind (wie eben in deinem Beispiel - in der einen Reihe hast du a, c, d in der anderen b, e, f). Dabei ist aber jede Kante in dem Graphen von einem perfect matching überdeckt - sie fängt an, oder hört auf in einem Knotnen der einen Reihe (oder Raum, wie auch immer).
Gruß,
dormant
|
|
|
|
