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

Navigation
 Startseite...
 Neuerdings beta neu
 Forum...
 vorwissen...
 vorkurse...
 Werkzeuge...
 Nachhilfevermittlung beta...
 Online-Spiele beta
 Suchen
 Verein...
 Impressum
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
StartseiteMatheForenGraphentheorieIst Graph verbunden?
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Informatik • Physik • Technik • Biologie • Chemie
Forum "Graphentheorie" - Ist Graph verbunden?
Ist Graph verbunden? < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Ist Graph verbunden?: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 22:25 Do 11.02.2010
Autor: Wimme

Aufgabe
Nimm einen Graph mit 8 Knoten, 4 von diesen Knoten haben Rang 2 (soll heißen hat 2 Nachbarn) die anderen 4 haben Rang 1. Ist dieser Graph verbunden?


Hallo!

Meiner Meinung nach ist es unter den gegebenen Voraussetzungen unmöglich den Graph zu verbinden.
Ich versuche mal zu erklären wieso:

Die 4 Knoten mit Rang 1 können nur mit jeweils einem verschiedenen Knoten von Rang 2 verbunden werden, so dass man 4 Komponenten erhält. (verbindet man 2 Knoten mit Rang 1 hat man auf jeden Fall eine seperate Komponente. Verbindet man 2 Knoten von Rang 1 mit einem von Rang 2 gilt dasselbe).

Verbindet man nun jeweils 2 dieser 4 Komponenten erhält man 2 Komponenten, bei denen alle Knoten bereits ihren vollen Rang erfüllt haben.
Eine zusätzliche Kante würde einen weiteren Rang 2 Knoten bedeuten oder aber einen Knoten von Rang 3.


Ist das so nachvollziehbar? Wie schreibe ich sowas schön auf? ;)

Dankesehr,
Wimme

        
Bezug
Ist Graph verbunden?: Antwort
Status: (Antwort) fertig Status 
Datum: 23:36 Do 11.02.2010
Autor: kalkulator


> Nimm einen Graph mit 8 Knoten, 4 von diesen Knoten haben
> Rang 2 (soll heißen hat 2 Nachbarn) die anderen 4 haben
> Rang 1. Ist dieser Graph verbunden?
>  
>
> Hallo!
>  
> Meiner Meinung nach ist es unter den gegebenen
> Voraussetzungen unmöglich den Graph zu verbinden.
> Ich versuche mal zu erklären wieso:
>  
> Die 4 Knoten mit Rang 1 können nur mit jeweils einem
> verschiedenen Knoten von Rang 2 verbunden werden, so dass
> man 4 Komponenten erhält. (verbindet man 2 Knoten mit Rang
> 1 hat man auf jeden Fall eine seperate Komponente.
> Verbindet man 2 Knoten von Rang 1 mit einem von Rang 2 gilt
> dasselbe).
>  
> Verbindet man nun jeweils 2 dieser 4 Komponenten erhält
> man 2 Komponenten, bei denen alle Knoten bereits ihren
> vollen Rang erfüllt haben.
>  Eine zusätzliche Kante würde einen weiteren Rang 2
> Knoten bedeuten oder aber einen Knoten von Rang 3.
>  
>
> Ist das so nachvollziehbar? Wie schreibe ich sowas schön
> auf? ;)
>  
> Dankesehr,
>  Wimme


Hallo Wimme,

Dein Lösungsweg ist nachvollziehbar und meiner Meinung nach richtig. Wie Du diese Lösung in eine besonders gute Form bringst, das weiß ich auch nicht so genau. Ich würde vermutlich die Knoten durchnummerieren und sagen, dass die ersten vier nur Rang eins haben...(?)

Ich kann Dir aber eine Alternative anbieten: Man kann relativ leicht zeigen, dass ein zusammenhängender Graph mit acht Knoten mindestens eine bestimmte Kantenzahl hat. Füge einfach nacheinander Knoten in den Graphen ein und sorge dann immer dafür, dass der Graph mit jedem weiteren Knoten immer noch zusammenhängend ist.
Die so ermittelte Kantenzahl passt nicht zu dem Graphen in Deiner Aufgabe.
Ich lenke Deine Aufmerksamkeit auf diesen anderen Lösungsweg, weil ich glaube, dass man ihn viel leichter aufschreiben kann.

viele Grüße vom Kalkulator

Bezug
                
Bezug
Ist Graph verbunden?: Frage (beantwortet)
Status: (Frage) beantwortet Status 
Datum: 16:02 So 14.02.2010
Autor: Wimme

Hallo kalkulator!

Also ich würde behaupten ein Graph mit 8 Knoten braucht mindestens 7 Kanten um verbunden zu sein.

Ein Graph der 4 Knoten mit Rang 2  und 4 Knoten mit Rang 1 hat, hat aber nur 6 Kanten, weil jede Kante im Rang ja doppelt gezählt wird.

Daraus folgt, dass der Graph nicht verbunden sein kann.

So meinst du das etwa?

Bezug
                        
Bezug
Ist Graph verbunden?: Antwort
Status: (Antwort) fertig Status 
Datum: 18:08 So 14.02.2010
Autor: Al-Chwarizmi


> Hallo kalkulator!
>  
> Also ich würde behaupten ein Graph mit 8 Knoten braucht
> mindestens 7 Kanten um verbunden zu sein.
>  
> Ein Graph der 4 Knoten mit Rang 2  und 4 Knoten mit Rang 1
> hat, hat aber nur 6 Kanten, weil jede Kante im Rang ja
> doppelt gezählt wird.
>  
> Daraus folgt, dass der Graph nicht verbunden sein kann.
>  
> So meinst du das etwa?

Hallo Wimme,

wie kalkulator das ganz genau gemeint hat, weiß ich nicht,
aber dein Lösungsweg ist so richtig.

Übrigens denke ich, dass man die Struktur des vorliegenden
Graphen vollständig (bis auf Isomorphie) beschreiben kann.
Er muss wohl aus einem "Vierer-Ring" und zwei "Hanteln"
bestehen und ist also offensichtlich nicht verbunden.

LG   Al-Chw.


Bezug
                        
Bezug
Ist Graph verbunden?: Antwort
Status: (Antwort) fertig Status 
Datum: 22:45 So 14.02.2010
Autor: kalkulator

Jo, genauso hab' ich mir das auch gedacht.

viele Grüße von  Andreas .
(Tarnname is doch vielleicht n' bischen reingesteigert)

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


^ Seitenanfang ^
www.matheraum.de
[ Startseite | Forum | Wissen | Kurse | Mitglieder | Team | Impressum ]