Kantenanzahl in einem Graphen |
| 22.02.2013, 10:45 | Nspace | Auf diesen Beitrag antworten » | ||
| Kantenanzahl in einem Graphen Ich habe die folgende ältere Klausurfrage gefunden und ich habe nicht mal einen Ansatz, wie ich hier rangehen würde. Es sei A = {a, b, c, d, e} und n Element N mit n >= 2. Der Graph G sei wie folgt definiert: Die Knotenmenge V(G) sei die Menge A^n, d.h. die Menge der n-Tupel (x1, x2, .... xn) mit xi Element A für i = 1 .. n. Zwei Elemente aus V(G) seien genau dann durch eine Kante verbunden, wenn sie in n - 2 Stellen übereinstimmen und sich an genau zwei Stellen unterscheiden. i) Wie viele Knoten hat G? Kann mir irgendjemand kurz auf die Sprünge helfen, dass ich einen Ansatz zum anfangen habe? Das ist ein wenig zu theoretisch für mich, obwohl ich meine, dass es da bestimmt einen ganz leichten Trick gibt, um sich das besser vorzustellen. Meine Ideen: Leider keine. Die Menge der n-Tupel meint wohl das kartesische Produkt der Elemente, also für n = 2 wohl die geordneten Paare: {(a, a), (a, b), (a, c), (a, d), (a, e), (b, c), (b, d), (b, e), (c, d), (c, e), (d, e)} Ist das schon einmal richtig? |
||||
| 22.02.2013, 18:29 | Nspace | Auf diesen Beitrag antworten » | ||
Habe ich die Frage zu ungenau gestellt? :/ Ich würde mich wirklich über einen Ansatz freuen, weil unter der Aufgabe kann ich mir nicht viel vorstellen. |
||||
| 22.02.2013, 18:55 | weisbrot | Auf diesen Beitrag antworten » | ||
wenn aber doch nach der kantenzahl gefragt ist: da muss man ein bisschen möglichkeiten zählen - ich würds so machen: erstmal einen beliebigen knoten vorstellen und zählen wieviele kanten der zu anderen hat (die kantenzahl zu anderen knoten sollte auch für jeden knoten gleich sein, kannst du dir bst. überlegen). das dann mit der anzahl der knoten multiplizieren und, weil man damit ja jede kante doppelt gezählt hätte, durch 2 teilen. die hauptaufgabe ist also sich zu überlegen, mit wievielen kanten ein beliebiger knoten verbunden ist. lg |
||||
| 22.02.2013, 19:01 | Nspace | Auf diesen Beitrag antworten » | ||
In Teilaufgabe i ist tatsächlich nach der Knotenzahl gefragt. Wieso 5^n? , das ist klar, aber nicht genau wie du mit Sicherheit 5^n sagen kannst. Erklärst du es mir? In Teilaufgabe ii heißt es, dass wir beweisen sollen, dass der Graph dann exakt Kanten hat. Mein Problem ist die Vorstellung hierbei. Wenn die Gradzahl jedes Knotens gleich sein soll, wie du sagst, dann wird es sich hierbei wohl um einen vollständigen Graphen handeln. Ist die Beschreibung aus der Aufgabe also eine Beschreibung für einen vollständigen Graphen, sprich ist das kartesische Produkt einer Menge immer ein vollständiger Graph? |
||||
| 22.02.2013, 19:12 | weisbrot | Auf diesen Beitrag antworten » | ||
naja, die knotenmenge ist doch einfach das n-fache kartesische produkt - davon weiß man einfach, dass das ding |A|^n elemente hat; oder man argumentiert kombinatorisch: für den ersten eintrag eines solchen elements gibt es n möglichkeiten, für den 2. auch, usw. - das multipliziert ergibt die gesamtanzahl solcher möglichen elemente.
du solltest dir nicht versuchen vorzustellen wie der graph wohl für irgendein n aussieht, sondern am besten dem folgen was ich im 1. post schon geschrieben hab und ein bisschen mit deinen kombinatorischen fähigkeiten glänzen
lg |
||||
| 22.02.2013, 19:22 | Nspace | Auf diesen Beitrag antworten » | ||
Uh klar... Es steht ja sogar implizit in der Aufgabe... peinlich. Gut kombinatorisch sagst du, ist nicht gerade meine Stärke. Aber versuchen wir's: Wir haben ein n-Tupel als Knoten der geht zu den Knoten die sich in 2 Stellen unterscheiden. Dafür gibt es doch dann (n über 2) = n * (n - 1) / 2 Möglichkeiten. Ist mein Gedankengang soweit richtig? Ab jetzt wird's nämlich etwas komplizierter für mich. |
||||
| Anzeige | ||||
|
|
||||
| 22.02.2013, 19:32 | weisbrot | Auf diesen Beitrag antworten » | ||
ja, das hört sich schon 'fast' gut an. n über (n-2) bzw. n über 2 ist erstmal die anzahl der möglichkeiten (n-2) einträge (in denen der knoten anderen gleichen soll) auszuwählen. das multipliziert man dann weiter mit der anzahl der anderen knoten, die diesem eben in den gewählten n-2 stellen gleich, aber in den anderen beiden verschieden sind pass dabei auf, dass sie sich in GENAU 2 stellen unterscheiden sollen, nicht etwa mind. oder max. 2. lg |
||||
| 22.02.2013, 19:37 | Nspace | Auf diesen Beitrag antworten » | ||
Hm, wieso n über (n - 2) wenn die Anzahl der unterschiedlichen Komponente doch stets 2 ist?
Den Satz kann ich nicht ganz nachvollziehen, vllt. deswegen das Verständnis Problem. |
||||
| 22.02.2013, 19:42 | weisbrot | Auf diesen Beitrag antworten » | ||
du weißt aber, dass n über k = n über (n-k) !? es ist eben dasselbe ob du nach der anzahl der möglichkeiten fragst, die es gibt, dass solche n-tupel an genau k stellen gleich sind, oder dass sie an genau k stellen verschieden sind. ist das ein deutscher satz 
lg |
||||
| 22.02.2013, 19:51 | Nspace | Auf diesen Beitrag antworten » | ||
Ich war kurz verwirrt, ob du Fakultät meinst oder ob es wirklich ein Satzzeichen ist.^^ Aber stimmt, da war was. Kombinatorik sollte ich mir nochmal ansehen. Damit haben wir 5^n * (n über (n - 2)) bzw 5^n * (n * (n - 1) / (n - 2) * 2) wenn ich das richtig sehe. Eine Heidenarbeit sowas herbei zu zaubern. Ich denke ich lass das erstmal aus. Aber danke für die Ansätze. 
|
||||
| 22.02.2013, 20:23 | weisbrot | Auf diesen Beitrag antworten » | ||
ok, deine entscheidung, ich könnts dir auch richtig erklären; aber stimmt, ist auch langsam zeit fürs wochenende. aber eine sache kann so nicht gelassen werden:
und damit wär man auch noch nicht fertig, weil man für eine feste solche wahl von stellen, an denen knoten übereinstimmen sollen, noch nicht die möglichen solchen knten gezählt hat. lg |
||||
| 22.02.2013, 20:25 | Nspace | Auf diesen Beitrag antworten » | ||
Wenn du vor Montag nochmal Zeit und Lust hast, würde ich mich über eine Erklärung dazu natürlich sehr freuen. |
||||
| 22.02.2013, 20:27 | weisbrot | Auf diesen Beitrag antworten » | ||
ok, bestimmt. du musst dann nur selbst nochmal überlegen und posten - wenn ichs dann sehe antworte ich auch. jetzt aber erstmal schönes we.! lg |
||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
