Maximale Anzahl an Freunden bestimmen |
| 29.12.2010, 18:02 | mathe760 | Auf diesen Beitrag antworten » | ||
| Maximale Anzahl an Freunden bestimmen ich habe hier mal wieder eine Aufgabe, bei der ich einen Ansatz benötige: Gegeben seien n Personen. Es werden nun m>3 Personen ausgewählt, wobei gilt: Immer wenn m Personen ausgewählt werden haben sie genau einen gemeinsamen Freund. Hierbei gilt: Wenn B Freund von A ist, so ist auch A Freund von B und man kann nicht Freund von sich selbst sein. Bestimmen Sie die Anzahl Freunde, die eine Person maximal hat. Ich denke man kann hier Graphentheorie anwenden, jedoch habe ich bisher keinen entsprechenden Satz gefunden. Alternativ könnte man bestimmt das Prinzip vom kleinsten/größten Element anwenden. Meine Vermutung ist, dass der maximale "Freundschaftsgrad" unabhängig von m gleich n-1 ist. Ich benötige jetzt einfach nur einen Ansatz oder einen Satz, der nützlich sein könnte. Schonmal vielen Dank für eure Antworten 
Bis denn mathe760 
|
||||
| 31.12.2010, 18:41 | mathe760 | Auf diesen Beitrag antworten » | ||
Hat keiner eine Idee für mich? Bis denn mathe760
|
||||
| 31.12.2010, 20:31 | pseudo-nym | Auf diesen Beitrag antworten » | ||
RE: Maximale Anzahl an Freunden bestimmen
Das scheint mir falsch zu sein, betrachte |
||||
| 31.12.2010, 23:30 | mathe760 | Auf diesen Beitrag antworten » | ||
Ja aber dieser Fall existiert garnicht, weil die ausgewählten m Personen genau einen Freund gemeinsam haben sollen, dieser aber nat. nicht unter den m Personen sein kann. Folglich muss gelten n>m. Bis denn mathe760
|
||||
| 01.01.2011, 00:23 | pseudo-nym | Auf diesen Beitrag antworten » | ||
Oh da hab ich hab ich die Aufgabenstellung falsch interpretiert. |
||||
| 02.01.2011, 16:14 | mathe760 | Auf diesen Beitrag antworten » | ||
Kein Problem
.Kann mir denn einer bei meinem Problem helfen? Bis denn mathe760
|
||||
| Anzeige | ||||
|
|
||||
| 08.01.2011, 20:12 | mathe760 | Auf diesen Beitrag antworten » | ||
Hmm ich komme immer noch nicht so richtig weiter. Immerhin habe ich jetzt das Problem in die Algebra übertragen, nur ob das hilft?: Seien n,m gegeben, wobei 3<m<n. Betrachte alle möglichen m- elementigen Teilmengen von der Menge M={1,2,....,n}, eine solche Teilmenge heißt M_j. Die Zahlen von 1 bis n stehen hierbei für die n Knoten. Betrachte nun die Abbildung , wobei ist. Zu zeigen ist jetzt, dass für jede beliebige Abbildung von obiger Art (mindestens) ein Bildelement n-1 verschiedene Urbilder hat. Kann man damit etwas anfangen oder habt ihr vielleicht doch noch einen Tipp, der in eine ganz andere Richtung geht? Das Problem für mich ist, dass es sehr viele Kantenkonfigurationen gibt, wenn man einen graphentheoretischen Ansatz bemüht- daher mein Versuch das Problem algebraisch anzugehen. Ich bin dennoch auch sehr stark an einem graphentheoretischen Ansatz interessiert.
Bis denn mathe760
|
||||
| 08.01.2011, 20:33 | chili12 | Auf diesen Beitrag antworten » | ||
Also evtl habe ich irgendwo einen Denkfehler. Aber mMn geht das ganze garnicht. wir haben n Freunde F1...FN Bsp N=5 Sagen wir mal F1 ist mit F2 und F3 befreundet dann finde ich eine Menge M mit F1 F2 und F3 in der alle Freunde von F1 sind somit muss F1 auch mit F4 oder F5 befreundet sein. Wenn man das Gedankenexperiment weiterführt sieht man ein, dass eigentlich jeder mit jedem fefreundet sein müsste. Aber Moment das geht ja auch nicht, denn wenn ich nur F1,F2 und F3 auswähle wären ja genau zwei gemeinsame Freunde in der übrigen Menge. |
||||
| 08.01.2011, 23:08 | mathe760 | Auf diesen Beitrag antworten » | ||
Ich verstehe nicht was du meinst... 1. F1 kann in deinem Bespiel ja nicht Freund von sich selber sein ( siehe 1. Beitrag). 2. Die anzahl m der ausgewählten Personen ist eine FEST gewählte Zahl, was wäre sie denn in deinem Beispiel? 3. Die von mir angegebene Menge M_j enthält eben nicht den Knoten, der mit den Knoten aus M_j inzidiert, aber du hast doch M_j={F1,F2,F3} (={1,2,3}) gewählt und vorausgesetzt, dass F1 mit F2 und F3 befreundet ist, das ist aber ein widerspruch?! Bis denn mathe760
|
||||
| 09.01.2011, 00:09 | chili12 | Auf diesen Beitrag antworten » | ||
1 ist klar ich meine natürlich mit allen ausser sich selbst. 2. Also das lese ich in der Aufgabenstellung nicht so. Es scheint mir eher so zu sein, dass für jede beliebig ausgewählte Gruppe aus m > 3 Personen eine übrige Person existieren muss, die mit allen ausgewählten Personen befreundet ist. 3. Genau dieser Widerspruch ist es ja der mMn diese Aufgabe unlösbar macht. Man kann eben immer eine Gruppe von m Personen finden die keine mit allen befreundete Person übrig lässt. Ausser jeder ist mit jedem befreundet. |
||||
| 09.01.2011, 12:54 | mathe760 | Auf diesen Beitrag antworten » | ||
| RE: Maximale Anzahl an Freunden bestimmen Entschuldigung, da war ich wohl etwas schlampig und habe ein kleines Wort vergessen:
Ich hoffe jetzt ist es klar.... Bis denn mathe760
|
||||
| 09.01.2011, 13:18 | chili12 | Auf diesen Beitrag antworten » | ||
Ok das heisst ja schonmal, dass jeder mindestens m Freunde haben muss, da sich sonst eine Menge von m Personen (Ihn und m-1 seiner Freunde) finden liesse, die alle seine Freunde beinhaltet. Dh für m=n-1 ist es einfach in diesem Fall ist nämlich jeder mit jedem Befreundet. (Anzahl freunde = m=n-1) für m = n-2 wird es komplizierter. Dh die Anzahl der Freunde liegt zwischen m und m+1=n-1 Nehmen wir mal an jmd (P1) hätte n-1 Freunde, wäre also mit allen Befreundet. Dann heisst das, dass jede Gruppe von m Personen, die P1 nicht beinhaltet. Nur ihn als gemeinsamen Freund haben darf. Dh alle anderen dürfen nur m Freunde besitzen. Was aber wenn ich nun m Personen auswähle incl P1 die zwei befreundete Personen übriglässt. D.h. beide sind nur mit m-1 Personen aus der Gruppe befreundet also keinesfalls mit allen -> Wiederspruch. Also muss jeder mit genau m=n-2 Personen befreundet sein. Nunja kA ob man das so weiterführen kann aber es ist immerhin schonmal ein Anfang. mfg |
||||
| 09.01.2011, 18:31 | mathe760 | Auf diesen Beitrag antworten » | ||
Ja das ist logisch, dass jeder Knoten mind. Grad m hat, aber das hat mir eben nicht weiter geholfen... Was ist denn mit meinem algebraischen Ansatz, kann jemand etwas dazu sagen? \Edit: Ich glaube ich kann doch was mit dem Ansatz anfangen, ich prüfe eben meine Vermutung. Bis denn mathe760
|
||||
| 09.01.2011, 20:47 | chili12 | Auf diesen Beitrag antworten » | ||
Hmm mir ist eben aufgefallen. Wenn mand as ganze andersrum anpackt geht es auch nicht gut. Sei m=n-2. Ich hatte ja gezeit, dass dann jeder m Freunde haben muss. Wenn man nun aber zwei befreundete Personen im Kompliment von M hat kann es wieder nicht gehen, da beide nur m-1 Freunde in M haben und somit nicht mit allen befreundet sein können. Ich hab den starken verdacht, dass die Aufgabe nicht lösbar ist. |
||||
| 09.01.2011, 21:13 | mathe760 | Auf diesen Beitrag antworten » | ||
Naja das es eine Person mit Grad n-1 gibt, war ja nur meine Vermutung, keinesfalls aber die Aussage des Aufgabentextes. Offensichtlich war diese Vermutung aber falsch, und es gilt nun den richtigen Zusammenhang zu finden! Erstmal vielen Dank für deine Hilfe chili12, ich melde mich wieder, falls ich etwas neues herausgefunden habe. Bis denn mathe760
|
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
