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 Studienfächer findest Du auf www.vorhilfe.de z.B. Astronomie • Medizin • Elektrotechnik • Maschinenbau • Bauingenieurwesen • Jura • Psychologie • Geowissenschaften
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 59m 10. HJKweseleit
GraphTheo/Hyperwürfel teilen
Status vor 5h 21m 3. matux MR Agent
UAlgGRK/Ringerweiterung
Status vor 5h 21m 2. Gonozal_IX
MaßTheo/Fast überall
Status vor 6h 40m 3. Schreim
USons/Quasireguläre Hexagone
Status vor 7h 30m 2. Diophant
DiffGlGew/Differentialgleichung lösen
^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]