Graphen < Lineare Algebra < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 12:58 Mi 02.05.2007 | | Autor: | Freak84 |
| Aufgabe | | Zwischen 20 Städten bestehen 172 direkte Flugverbindungen. Die in beiden richtungen benutzbar sind. Keine Zwei verbinden die gleichen Städte. Zeigen sie, dass man von jeder Stadt in jede andere kommen kann ohne mehr als einmal umzusteigen. |
Hi
Also ich habe es ja hier mit einem Graphen zu tun, der aus 20 Knoten und 172 Katen besteht.
Und zeigen muss ich, dass jeweis zwei punkte Maximal durch einen Punkt dazwischen liegt beim kürzesten weg. Nur ich habe keine Ahnung wie ich dieses zeigen soll.
Ich weiß, wenn des Graph vollständig wäre hätte er 189 Kanten.
Also hat dieser 17 Kanten weniger. Also wie könnte ich dieses machen ??
Gruß
Freak
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:44 Mi 02.05.2007 | | Autor: | piet.t |
Hallo,
> Hi
> Also ich habe es ja hier mit einem Graphen zu tun, der aus
> 20 Knoten und 172 Katen besteht.
> Und zeigen muss ich, dass jeweis zwei punkte Maximal durch
> einen Punkt dazwischen liegt beim kürzesten weg. Nur ich
> habe keine Ahnung wie ich dieses zeigen soll.
>
> Ich weiß, wenn des Graph vollständig wäre hätte er 189
> Kanten.
Also ich komme für den vollständigen Graphen auf (20*19)/2 = 190 Kanten???
> Also hat dieser 17 Kanten weniger. Also wie könnte ich
> dieses machen ??
...damit hätte ich dann 18 Kanten weniger als beim vollständigen Graphen.
>
> Gruß
> Freak
>
Die Aufgabe kenne ich noch aus dem Bundeswettbewerb Mathematik als ich in der 10. war - übrigens die einzige, die ich damals rausbekommen habe.
Man kann das eigentlich ganz anschaulich begründen. Beginne mit dem vollständigen Graphen und wähle eine beliebige Ausgangsstadt A und eine davon verschiedene Zielstadt B.
Dann versuche durch entfernen möglichst weniger Kanten eine Konstellation zu erzeugen, so dass man von A nach B mindestens zweimal umsteigen muss. Wie viele Kanten musst Du dann entfernen und warum?
Gruß
piet
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 21:30 Mi 02.05.2007 | | Autor: | Freak84 |
Vielen Dank
Habe sie jetzt fertig habe einfach einen Denkfehler gehabt beim Kantenrechnen ?
So habe ich ja den K19 Vollständig und kann die eine Kante zum K20 führen
Vielen Dank
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 21:46 Mi 02.05.2007 | | Autor: | piet.t |
Hmm, rein von den Zahlen kommt das schon hin - allerdings kann es ja durchaus auch Kostellationen geben, die keinen vollständigen Teilgraphen mit 19 Knoten enthalten. Und was dann??
|
|
|
|
