Graphentheorie |
| 25.12.2013, 18:23 | MeineKekse | Auf diesen Beitrag antworten » |
| Graphentheorie Zeige, dass ein schlichter bipartiter Graph mit n Knoten höchsten n^2/4 Kanten haben kann. Also auf eine allgemeine Lösung komme ich leider nicht. Bis jetzt habe ich mir überlegt, dass wenn man eine gerade Anzahl an Knoten hat und diese in zwei disjunkte gleich große Mengen aufteilt. Kann jeder Knoten aus einer dieser Mengen maximal den Grad n/2 haben. da ich n Knoten habe ist die Summer der Grade n*n^2/2. Ebenfalss weiß ich dass die Summe der Grade = 2E ist. Also gilt n*(n^2/2) >= 2E => n^2/4 >= E. In allen anderen Fällen komme ich leider nicht auf die Lösung. Vielen Dank schon einmal für eure Hilfe |
||
| 26.12.2013, 16:07 | MI | Auf diesen Beitrag antworten » |
| RE: Graphentheorie Wenn ich das richtig sehe, geht das einfacher: - du hast zwei Mengen: eine mit k und eine mit l Elementen mit k+l=n (n Knoten). - die Kanten können nur zwischen den Mengen liegen, nicht ganz innerhalb (bipartit) - damit kann jeder Knoten der Menge mit k Elementen nur maximal l Kanten haben, die an ihm enden (eine zu jedem Knoten der anderen Menge). - also gibt's insgesamt höchstes k*l Kanten. Siehst du, dass du damit auf ein einfaches Optimierungsproblem stößt? Gruß MI |
||
| 26.12.2013, 19:50 | MeineKekse | Auf diesen Beitrag antworten » |
| RE: Graphentheorie Hi, vielen Dank für deine Antwort, leider weiß ich nicht genau worauf du hinaus willst, ich soll doch zeigen, dass es nicht mehr als n^2/ 4 Kanten geben kann.. 
|
||
| 28.12.2013, 13:08 | MeineKekse | Auf diesen Beitrag antworten » |
| RE: Graphentheorie hat keiner eine Idee? Ich bin leider auch nicht weiter gekommen 
|
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
