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
StartseiteMatheForenGraphentheorieGraphen
Foren für weitere Schulfächer findest Du auf www.vorhilfe.de z.B. Philosophie • Religion • Kunst • Musik • Sport • Pädagogik
Forum "Graphentheorie" - Graphen
Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
Ansicht: [ geschachtelt ] | ^ Forum "Graphentheorie"  | ^^ Alle Foren  | ^ Forenbaum  | Materialien

Graphen: Aufgabe
Status: (Frage) beantwortet Status 
Datum: 02:17 Di 01.08.2006
Autor: mond

Aufgabe
Aufgabe:
(a) Sei G=(V,E) ein zusammenhängender Graph und e von E eine Kante. Zeige: Der Teilgraph G1( V, E\ {e}) ist genau dann zusammenhängend, wenn es einen Kreis in G gibt, der die Kante e enthält.
(b) Zeige, dass es in einen zusammenhängenden Planaren Graphen mit 20 Knoten und 40 Kanten mindestens 8 Dreiecke gibt.

Bitte kann Jemand mir hilfen.
wie kann ich a und b beantworten
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt


        
Bezug
Graphen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 07:14 Di 01.08.2006
Autor: kretschmer

Hallo,

also es wäre schön, wenn Du nicht einfach nur nach einer Lösung fragst, sondern auch sagst, was Du bereits geschafft hast. Dann kann man Dir auch helfen!


Zum Teil a): Also ich würde das vielleicht per Widerspruch versuchen. Angenommen e gehört nicht zu einem Kreis ...

Zum Teil b): Da würde ich mir die Eigenschaften zu Hilfe nehmen, die planare Graphen ausmachen. D.h. man hat keine 5-Klicken, zum Beispiel. Gab noch andere Objekte, die es nicht geben kann. Dann das gepaart mit der Anzahl der Knoten zu der Anzahl der Kanten sollte Dich zu einer Lösung bringen.

--
Gruß
Matthias

Bezug
                
Bezug
Graphen: ruekfrage
Status: (Frage) beantwortet Status 
Datum: 10:45 Di 01.08.2006
Autor: mond

danke fuer die Hilfe
Ich moechte wissen ist Teil a so richtig

wenn G keinen Kreis enthaelt, so ist G bereit ein Baum ( kreisfrei und zusammenhaenged)
wenn G ist ein Baum, dann e ist ein Blatter
dann [mm] G1=G\e [/mm] ist nicht yusammenhaengd weil wenn wir e loeschen dann gibt es kein Kantenzug zwischen ( ve-1,ve)
dann G1 nicht zusammenhaenged ist.
Nun enthaelt G einen Kreis k, e ist die Kante die von G1 geloescht hat.
Da k ein Kreis ist, werden die Enfknoten von e durch G1 verbunden. Daher ist G1 immer noch yusammenhaenged.


Bezug
                        
Bezug
Graphen: Antwort
Status: (Antwort) fertig Status 
Datum: 13:55 Mi 02.08.2006
Autor: kretschmer

Hallo,

also es ist sehr schwer Dir zu folgen. Ja wenn ein Graph kreisfrei und zusammenhängend ist, dann ist es ein Baum modulo Richtung der Kanten. Eine Kante entfernen führt dazu, dass es dann kein zusammenhängender Graph. Formal müsstest Du jetzt noch beweisen, dass jeder kreisfreie zusammenhängende Graph einem Baum (module Richtung der Kanten) entspricht.

--
Gruß
Matthias

Bezug
                                
Bezug
Graphen: danke und b schritt
Status: (Frage) beantwortet Status 
Datum: 14:06 Mi 02.08.2006
Autor: mond

für b habe ich nue knoten una kanten Anzahl.
und 8 Dreieckig
und als Satz habe ich
n-m+f=2 in Planar Graphen
20-40+f=2
dann f die Anzahl von Faces ist 22 .f=22
wie kann ich weiter gehen?


Bezug
                                        
Bezug
Graphen: Antwort
Status: (Antwort) fertig Status 
Datum: 22:46 Mi 02.08.2006
Autor: felixf

Hallo mond!

> für b habe ich nue knoten una kanten Anzahl.
>  und 8 Dreieckig
>  und als Satz habe ich
>  n-m+f=2 in Planar Graphen
>  20-40+f=2
>  dann f die Anzahl von Faces ist 22 .f=22
>  wie kann ich weiter gehen?

Das ist schonmal ein guter Anfang. Sei $F$ die Menge aller Faces, und zu jedem $f [mm] \in [/mm] F$ sei [mm] $\deg [/mm] f$ die Anzahl der Ecken (was gleich der Anzahl von Kanten ist, die zum Face gehoeren). Dann ist naemlich [mm] $\sum_{f \in F} \deg [/mm] f = 2 m$ (da jede Ecke zu genau zwei Faces gehoert). Nun ist $2 m = 2 [mm] \cdot [/mm] 40 = 80$.

Beachte, dass ein Face $f [mm] \in [/mm] F$ genau dann ein Dreieck ist, wenn [mm] $\deg [/mm] f = 3$ ist.

Sei $d$ nun die Anzahl der Dreiecke. Dann ist [mm] $\sum_{f \in F} \deg [/mm] f = [mm] \sum_{f \in F \atop \deg f > 3} \deg [/mm] f + d [mm] \cdot [/mm] 3 [mm] \ge \sum_{f \in F \atop \deg f > 3} [/mm] 4 + d [mm] \cdot [/mm] 3 = (22 - d) [mm] \cdot [/mm] 4 + d [mm] \cdot [/mm] 3 = 22 [mm] \cdot [/mm] 4 - d$.

Wenn also $d < 8$ ist, dann ist [mm] $\sum_{f \in F} \deg [/mm] f [mm] \ge [/mm] 88 - d > 80$, ein Widerspruch. Also muss $d [mm] \ge [/mm] 8$ sein, es muss also mindestens acht Dreiecke geben!

LG Felix



Bezug
                                
Bezug
Graphen: Mitteilung
Status: (Mitteilung) Reaktion unnötig Status 
Datum: 07:16 Mi 09.08.2006
Autor: mathiash

Moin zusammen,

da nichts anderes erwähnt ist, sollte man davon ausgehen, dass es sich um einen ungerichtetetn Graphen handelt.

Jedenfalls ist die Sprechweise ''modulo Richtung der Kanten'' unüblich.

Ansonsten frohes Schaffen wünscht

Mathias

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


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