Graphentheorie - 20 Städte < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 11:25 Di 24.09.2013 | | Autor: | AntonK |
| Aufgabe | | Zwischen 20 Städten bestehen 172 direkte Flugverbindungen, die jeweils in beide Richtungen benutzbar sind. Keine 2 von ihnen verbinden die selben beiden Städte. Zeigen Sie, dass man von jeder Stadt in jede andere fliegen kann, ohne dabei mehr als einmal umzusteigen. |
Hallo Leute,
habe hierfür folgende Lösung:
http://www.myimg.de/?img=diskrete224a1.jpg
Ich habe ein Problem mit der Summe, warum werden dort die 18 Kanten abgezogen?
Danke schonmal!
|
|
| |
|
> Zwischen 20 Städten bestehen 172 direkte Flugverbindungen,
> die jeweils in beide Richtungen benutzbar sind. Keine 2 von
> ihnen verbinden die selben beiden Städte. Zeigen Sie, dass
> man von jeder Stadt in jede andere fliegen kann, ohne dabei
> mehr als einmal umzusteigen.
> Hallo Leute,
>
> habe hierfür folgende Lösung:
>
> http://www.myimg.de/?img=diskrete224a1.jpg
>
> Ich habe ein Problem mit der Summe, warum werden dort die
> 18 Kanten abgezogen?
>
> Danke schonmal!
Hallo Anton,
die Grundidee des Beweises ist die: wenn man für
die Reise von [mm] v_i [/mm] zu [mm] v_j [/mm] mehr als einmal umsteigen
müsste, muss folgendes erfüllt sein:
1.) zwischen [mm] v_i [/mm] und [mm] v_j [/mm] ist keine Kante (Flugver-
bindung)
2.) die Menge der von [mm] v_i [/mm] aus direkt verbundenen
Städte und die der von [mm] v_i [/mm] aus direkt verbundenen
Städte haben kein gemeinsames Element, also
folgt [mm] deg(v_i)+deg(v_j)\le18 [/mm] (denn es gibt ja außer
[mm] v_i [/mm] und [mm] v_j [/mm] nur 18 andere Städte bzw. Knoten)
In der Summe sollen nun die Grade von allen Knoten
außer jenen mit Nummer i und Nummer j addiert
werden. Diese Summe erhält man, indem man von
344 (=Summe aller 20 Grade=2*Anzahl aller Kanten)
die Anzahl alle von [mm] v_i [/mm] und [mm] v_j [/mm] ausgehenden Kanten
subtrahiert. Weil i und j keine gemeinsamen Nachbarn
haben, ist [mm] deg(v_i)+deg(v_j)\le18 [/mm] .
Daraus folgt nun, dass die Anzahl aller Kanten, welche
weder mit [mm] v_i [/mm] noch mit [mm] v_j [/mm] inzident sind, mindestens
344-18 sein muss.
Mach dir die Idee dazu ev. mal an einem Beispiel-
Graph mit vielleicht nur 8 Städten anschaulich klar.
LG , Al-Chw.
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 09:39 Do 26.09.2013 | | Autor: | AntonK |
Verstehe, danke soweit! Es könnten aber genausogut auch weniger als 18 abgezogen werden, das ist nur der Worstcase oder?
"Also müssen zwischen den verbleibenen 18 Knoten mehr als 163 Kanten sein. K_18 hat aber nur 153 Kanten, was weniger ist als 163. Dies ist ein Widerspruch zur Annahme, dass es ein Graph ist."
Wieso ist das ein Widerspruch? Wenn es mehr sind als bei K_18, dann wären Städte auch doppelt verbunden, verstehe ich das richtig?
|
|
|
| |
|
> Wieso ist das ein Widerspruch?
> Wenn es mehr sind als bei K_18, dann wären Städte
> auch doppelt verbunden, verstehe ich das richtig?
Ja. Und dieser Fall war ja nach Voraussetzung ausge-
schlossen.
LG , Al-Chw.
|
|
|
|
