matheraum.de
Raum für Mathematik
Offene Informations- und Nachhilfegemeinschaft

Für Schüler, Studenten, Lehrer, Mathematik-Interessierte.
Hallo Gast!einloggen | registrieren ]
Startseite · Forum · Wissen · Kurse · Mitglieder · Team · Impressum
Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
Forenbaum
^ Forenbaum
Status Mathe
  Status Schulmathe
    Status Primarstufe
    Status Mathe Klassen 5-7
    Status Mathe Klassen 8-10
    Status Oberstufenmathe
    Status Mathe-Wettbewerbe
    Status Sonstiges
  Status Hochschulmathe
    Status Uni-Analysis
    Status Uni-Lin. Algebra
    Status Algebra+Zahlentheo.
    Status Diskrete Mathematik
    Status Fachdidaktik
    Status Finanz+Versicherung
    Status Logik+Mengenlehre
    Status Numerik
    Status Uni-Stochastik
    Status Topologie+Geometrie
    Status Uni-Sonstiges
  Status Mathe-Vorkurse
    Status Organisatorisches
    Status Schule
    Status Universität
  Status Mathe-Software
    Status Derive
    Status DynaGeo
    Status FunkyPlot
    Status GeoGebra
    Status LaTeX
    Status Maple
    Status MathCad
    Status Mathematica
    Status Matlab
    Status Maxima
    Status MuPad
    Status Taschenrechner

Gezeigt werden alle Foren bis zur Tiefe 2

Das Projekt
Server und Internetanbindung werden durch Spenden finanziert.
Organisiert wird das Projekt von unserem Koordinatorenteam.
Hunderte Mitglieder helfen ehrenamtlich in unseren moderierten Foren.
Anbieter der Seite ist der gemeinnützige Verein "Vorhilfe.de e.V.".
Partnerseiten
Dt. Schulen im Ausland: Mathe-Seiten:Weitere Fächer:

Open Source FunktionenplotterFunkyPlot: Kostenloser und quelloffener Funktionenplotter für Linux und andere Betriebssysteme
StartseiteMatheForenGraphentheorieGraphentheorie - 20 Städte
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Deutsch • Englisch • Französisch • Latein • Spanisch • Russisch • Griechisch
Forum "Graphentheorie" - Graphentheorie - 20 Städte
Graphentheorie - 20 Städte < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Graphentheorie - 20 Städte: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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!

        
Bezug
Graphentheorie - 20 Städte: Antwort
Status: (Antwort) fertig Status 
Datum: 11:59 Di 24.09.2013
Autor: Al-Chwarizmi


> 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.





Bezug
                
Bezug
Graphentheorie - 20 Städte: Frage (beantwortet)
Status: (Frage) beantwortet Status 
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?

Bezug
                        
Bezug
Graphentheorie - 20 Städte: Antwort
Status: (Antwort) fertig Status 
Datum: 13:35 Do 26.09.2013
Autor: Al-Chwarizmi


>  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.

Bezug
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien


Alle Foren
Status vor 9h 57m 2. fred97
UAnaR1FunkDiff/Polynomfunktion differenzierba
Status vor 10h 10m 1. Stephan30
Maxima/Indizes zählen mit Funktion
Status vor 11h 46m 1. mathenoob3000
UStoc/Markov Kette: Definitionen
Status vor 14h 48m 1. tc_engineer
Algebra/Hash für Bloom-Filter
Status vor 16h 29m 4. Diophant
ULinASon/Lineare Optimierung
^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]