Graphentheorie: Anwendungs-Aufgabe

07/04/2012 - 21:24 von Thomas Plehn | Report spam
Die aufgebe ist es eine Band mit möglichst vielen Musikern
zusammenzustellen, die alle unterschiedliche Instrumente spielen.

Jetzt gibt es bestimmte Einschrànkungen:
Z.b. A spielt nicht, wenn B Gitarre spielt, usw.
C spielt nur, wenn D Schlagzeug spielt

wie kann man Graphentheoretische Algorithmen verwenden, um das Problem
zu lösen?
 

Lesen sie die antworten

#1 Detlef Müller
08/04/2012 - 11:05 | Warnen spam
On 07.04.2012 21:24, Thomas Plehn wrote:
Die aufgebe ist es eine Band mit möglichst vielen Musikern
zusammenzustellen, die alle unterschiedliche Instrumente spielen.

Jetzt gibt es bestimmte Einschrànkungen:
Z.b. A spielt nicht, wenn B Gitarre spielt, usw.
C spielt nur, wenn D Schlagzeug spielt

wie kann man Graphentheoretische Algorithmen verwenden, um das Problem
zu lösen?



Dazu braucht man erst einmal einen Graphen - es würde sich eine
Art "Zustandsraum" anbieten, wobei die Knoten zulàssige
Band-Konstellationen sind und die Kanten mögliche Änderungen der
Konstellation durch Hinzunahme/Abgang eines/mehrerer Musiker(s)
darstellen.

Der Beschreibung nach ist eine Menge Musiker (M) gegeben,
vermutlich ist jedem davon wiederum eine eine Menge von Instrumenten
zugeordnet (i(m)), die gespielt werden können und es gibt einen Satz
einschrànkender Bedingungen an die Teilmengen (Bands) von M,
etwa m,n aus B => i(m) disjunkt zu i(n), da ja alle Instrumente
unterschiedlich sein sollen.

Sollte es gelingen den resultierenden Graphen hinreichend gut
zu beschreiben, könnte man die Kanten gewichten (Änderung der
Mitgliederzahl) und z.B. nach einem làngsten Weg im Graphen
suchen.

Gruß,
Detlef

Dr. Detlef Müller,
http://www.mathe-doktor.de oder http://mathe-doktor.de

Ähnliche fragen