Studium, Ausbildung und Beruf
 StudiumHome   FAQFAQ   RegelnRegeln   SuchenSuchen    RegistrierenRegistrieren   LoginLogin

Graphentheorie?
Neues Thema eröffnen   Neue Antwort erstellen
Foren-Übersicht -> Mathe-Forum -> Graphentheorie?
 
Autor Nachricht
stekoe2000
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 25.10.2005
Beiträge: 4

BeitragVerfasst am: 25 Okt 2005 - 07:55:27    Titel: Graphentheorie?

Hallo!

Ich hänge seit nunmehr 7 Stunden über der Konstellation einer Gruppenarbeit:

Ich habe 6 Gruppen, in denen 2 oder mehr Personen sind. Diese sollen nun in 3 Schichten aufgeteilt werden, und zwar am besten so, dass jede Gruppe mit jedem einmal zusammen arbeiten muss.

1 2 3 // Schichten
=============
1 3 5
2 4 6
====
4 1 2
5 6 3
====
3 2 1
6 5 4
====
2 1 3
4 5 6 // Hier ist 5 schon das 2. mal in der 2. Schicht nacheinander -> soll nicht
====
3 4 1
5 6 2

etc.

Irgendwie kommt das nicht aus, habe hier mehrere Ansätze, die nicht funktionieren. Hat jemand eine Idee?

In einem anderen Forum wurde ich auf die Graphentheorie etc. hingewiesen. Ich habe diese aber noch niemals in der Schule behandelt, und habe keine Ahnung, wie man das anstellen soll ... Daher bitte ich um HIlfe

LG
Stekoe
algebrafreak
Senior Member
Benutzer-Profile anzeigen
Senior Member


Anmeldungsdatum: 28.10.2004
Beiträge: 4143
Wohnort: Passau

BeitragVerfasst am: 25 Okt 2005 - 12:41:17    Titel:

Zitat:
und zwar am besten so, dass jede Gruppe mit jedem einmal zusammen arbeiten muss.


Ich verstehe die Aufgabenstellung nicht. "Am besten" signalisiert doch, dass Du mit einer suboptimalen Lösung auch zufrieden bist, oder? Was heißt "jede Gruppe mit jedem"? Mit jedem "Was"?
stekoe2000
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 25.10.2005
Beiträge: 4

BeitragVerfasst am: 25 Okt 2005 - 14:26:12    Titel:

Es existieren die Gruppen 1, 2, 3, 4, 5, 6 (also Eins bis Sechs!)
Es sind 3 Schichten vorhanden, die belegt werden müssen und zwar so, dass jede Gruppe, mit einer anderen Gruppe zusammen arbeitet:

1 mit 2
3 mit 4
und
5 mit 6

Dies soll nun aber auch so variiert werden, dass jede Gruppe mit jeder anderen Gruppe einmal zusammen arbeitet. Also 1/2, 1/3, 1/4, etc aber auch 2/1 usw.

Dabei ist dann wiederum zu beachten dass die Schichten parallel liegen, also jede der 6 Gruppen nur in einer Sicht sein kann, also nicht:

1 / 2
2 / 5 -> Gruppe 2 müsste sich klonen um hier gleichzeitig mitzuarbeiten
4 / 3

Weiterhin ist es für das Arbeitsklima und die Stimmung der Arbeiter wichtig, dass sie nicht 2 mal nacheinander in der selben Schicht arbeiten:

Tag 1:
1 / 2
3 / 4
5 / 6

Tag 2:
5 / 6
3 / 2 -> Gruppe 3 schon wieder in der 2. Schicht.
1 / 4

Da ich leider absolut keine Ahnung habe, was Graphentheorie ist bitte ich hier um Hile...

LG SteKoe
Samuel Plentz
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 24.10.2005
Beiträge: 6

BeitragVerfasst am: 27 Okt 2005 - 08:14:51    Titel:

Also ich hab mal ein bisschen rumprobiert:

Wie wärs mit:

Variante 1
135 312 153 241 432 (153)
246 564 426 365 516 (264)

Variante 2
135 312 153 214 162 (315)
246 564 426 635 543 (426)

Variante 3
135 312 653 526 315 (153)
246 564 241 134 642 (264)

Variante 4
135 312 653 462 314 (531)
246 564 241 135 256 (642)

Variante 5
135 312 635 346 531 (315)
246 564 421 152 264 (426)

Variante 6
135 312 635 246 125 (531)
246 564 421 513 364 (642)

Alles sind Möglichkeiten ohne Wiederholungen in 5 Schritten alle Kombinationen durchzuspielen.

Um auch noch jeden in jeder Schicht gleich oft arbeiten zu lassen, müsste die Variante 1 und die Variante 2 3x hintereinander ausgeführt werden:

135 ... V1 ... 153 ... V2 ... 513 ... V1 V2 ... 351 ... V1 V2 ... 135
246 ... V1 ... 264 ... V2 ... 624 ... V1 V2 ... 462 ... V1 V2 ... 246

Dadurch ist jeder sowohl in Variante 1 als auch in Variante 2 einmal in jeder Schicht.

PS:
Wozu ist das gut? Und was das mit Grafentheorie zu tun hat weiss ich nicht. Obwohl ich Grafentheorie kenne...
stekoe2000
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 25.10.2005
Beiträge: 4

BeitragVerfasst am: 27 Okt 2005 - 14:37:41    Titel:

Ich wurde in einem anderen Forum auf die Grafentheorie hingewiesen, dass es dadurch zu einer Lösung kommen kann.

Wozu das gut ist. Ich versuche einen Dienstplan zu erstellen, in dem sich 6 Gruppen befinden. Ich habe 3 Schichten, die besetzt werden MÜSSEN und zwar immer so, dass 2 der 6 Gruppen bei jeweils einer Schicht eingesetzt werden.

Nun sollte es der fairnesshalber so sein, dass die Gruppen so gemischt werden, dass jede Gruppe einemal mit einer anderen zusammen eine SChicht übernehmen muss. Ausserdem soll es so sein, dass die selbe Gruppe nicht zwei mal nacheinander die selbe Schicht arbeiten muss, da diese beispielsweise morgens um 8.30 Uhr beginnt. (Neben 18.30 und 10.45)
Samuel Plentz
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 24.10.2005
Beiträge: 6

BeitragVerfasst am: 28 Okt 2005 - 07:15:04    Titel:

Reicht dir das als Lösung Question
starzfighter
Junior Member
Benutzer-Profile anzeigen
Junior Member


Anmeldungsdatum: 29.07.2005
Beiträge: 78

BeitragVerfasst am: 28 Okt 2005 - 10:26:36    Titel:

Jop es wäre gut etwas genauer zu erfahren was du genau willst.Alle Lösungen? Eine Lösung?
Ein möglicher Lösungsansatz wäre besipielsweise sich das ganze als 3 eck vorzustellen mit den einzelnen möglichen Komponenten

1 1 1 1 1
2 3 4 5 6

2 2 2 2
3 4 5 6

3 3 3
4 5 6

4 4
5 6

5
6

Nun entscheide ich mich dafür mit wenn es für 5 Arbeitstage gedacht ist mit den 1 in der ersten Zeile zu beginnen

1yx x1x xx1 x1x 1xx
2yx x3x xx4 x5x 6xx

So kann ich sicher sein das sich nicht die 1 Gruppe 2 mal hintereinander in der gleichen Schicht befindet.
Nun sehe ich das ich bei der Positon yy keine der 2er-Tupel aus der ersten zweiten oder 3ten Zeile nehmen kann da sonst sich die 1 oder 3 in der gleichen Schicht die 3 befände oder aber die 1 nochmal vorkäme.
Die erste Zeile ist jetzt eh uninteressant. Also wähle ich die 56 wodurch automatisch das letzte Tupel als 34 mitbestimmt wird.
zur verfügung stehende tupel:
4 4 5
5 6 6
=>
153 412 321 213 124
264 635 564 456 635

Das kann man wunderschön machen wenn man sich das Dreieck auf nen Zettel schreibt und immer Vorgänger und Nachfolger betrachten. Man kann dann wegstreichen was man schon hat.

@Samuel die Zahlen in den Klammern sind mir nicht klar wofür die da sind. Spätstens nach 5 Tagen müsste man eigentlich zu einer wiederholung eines Tupels kommen was an der Anzahl der Tupel liegt.
Samuel Plentz
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 24.10.2005
Beiträge: 6

BeitragVerfasst am: 28 Okt 2005 - 10:42:17    Titel:

Die Zahlen in den Klammern sind für mehrere Zyklen. Wenn man mit eine Kombination durchlaufen hat kann man nicht wieder mit

135
246

weitermachen, da ansonsten wieder Leute die gleiche Schicht hintereinander machen. Es ist sinnvoll nur Spalten auszutauschen. Werden dann zum Beispiel Variante 1 und 2 ausgeführt hat man die Spalten um eine Spalte nach rechts verschoben. -> Wenn man das dreimal macht ist man wieder am Anfang.
Da dann jeder einmal in jeder Spalte war, als Variante 1 und 2 ausgeführt wurde, hat jeder alle Schichten gleich oft hinter sich.
(Jede Kombination stellt schon sicher, dass jeder mit jedem mal dran war...)
stekoe2000
Newbie
Benutzer-Profile anzeigen
Newbie


Anmeldungsdatum: 25.10.2005
Beiträge: 4

BeitragVerfasst am: 28 Okt 2005 - 13:10:09    Titel:

Ja, dankeschön, hab das fast vergessen zu sagen!
Die Lösung ist gut, reicht mir aus, aber ich bin noch im Verstehensprozess, brauche noch ein wenig. Zudem bin ich krank und das Denken geht nicht so schnell *g
Beiträge der letzten Zeit anzeigen:   
Foren-Übersicht -> Mathe-Forum -> Graphentheorie?
Neues Thema eröffnen   Neue Antwort erstellen Alle Zeiten sind GMT + 1 Stunde
Seite 1 von 1

 
Gehe zu:  
Du kannst keine Beiträge in dieses Forum schreiben.
Du kannst auf Beiträge in diesem Forum nicht antworten.
Du kannst deine Beiträge in diesem Forum nicht bearbeiten.
Du kannst deine Beiträge in diesem Forum nicht löschen.
Du kannst an Umfragen in diesem Forum nicht mitmachen.

Chat :: Nachrichten:: Lexikon :: Bücher :: Impressum