 |
 |
 |
 |
 |
 |
Startseite » Forum » Extremalprinzip
Extremalprinzip
Universität / Fachhochschule
Sonstiges
Tags: Sonstig
 
|
  |
|---|
|
Betrachte eine Gruppe . . . von Personen eine natuerliche Zahl). Jede dieser Personen kenne maximal drei andere Personen. Dabei soll das Verhaeltnis ” kennen“ symmetrisch sein, das heißt kennt eine andere Person so kennt auch die Person . Zeige, dass sich die Gruppe in zwei kleinere Teilgruppen und aufteilen laesst, sodass jede Person maximal eine weitere in der eigenen Teilgruppe kennt. Hinweis: Betrachte dazu beispielsweise fuer jede Aufteilung in zwei Teilgruppen und die folgende Groeße: Summe der Anzahl der Bekanntschaften innerhalb und der Anzahl der Bekanntschaften innerhalb . Ich komme trotz des Hinweises nicht wirklich auf einen Lösungsansatz. Hat da jemand ne kleine Idee für mich? Danke Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert): "Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen." |
|
 |
|
Grundsätzlich ist es hier bewiesen: mathoverflow.net/questions/247734/partition-of-a-graph-into-subgraphs-with-small-maximum-degree |
 |
|
Das hilft mir leider nicht weiter, daraus werde ich nicht wirklich schlauer. |
|
|
|
Ja, es ist nicht ganz einfach zu verstehen. Gut, ich erkläre es konkret für deine Aufgabe. Sei die Anzahl der Bekanntschaften, die Personen innerhalb haben, und entsprechend die Anzahl der Bekanntschaften, die Personen innerhalb haben, wobei jede Bekanntschaft nur einmal gezählt wird. (Also Bekanntschaft zwischen und ist die Kante im entsprechenden Graph). Beispiel: wenn , die einzigen Bekanntschaften sind und , , dann ist () und (). Sei jetzt solche Aufteilung, die minimiert. Da es nur endlich viele Aufteilungen gibt, existiert solche. Angenommen, bei dieser Aufteilung gibt's in einer Gruppe jemanden mit mindestens Bekanntschaften. Also, z.B. in gibt's und sind Bekanntschaften. Da nur Bekanntschaften insgesamt haben kann, ist seine dritte Bekanntschaft (wenn er sie hat) in . Jetzt ändern wir die Aufteilung, und zwar verlegen aus nach . Damit verschwinden zwei Bekanntschaften aus und es kommt höchstens eine neue in (eine, wenn existiert und keine, wenn nicht). Also, ist kleiner geworden, was ein Widerspruch zu der Annahme der Minimalität ist. Damit alles bewiesen. |
 |
|
Vielen Dank, das war verständlich! |
1550562
1550538