Multigraph < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:01 Di 01.09.2009 | | Autor: | Pacapear |
Hallo zusammen!
Ich habe eine Frage zur Definition eines Multigraphen.
Also in meinem einen Buch steht, dass das Graphen sind, in denen parallele Kanten zugelassen sind.
Und in meinem anderen Buch steht folgendes:
Ein Multigraph ist ein Paar $(V,E)$ disjunkter Mengen (von Ecken und Kanten) zusammen mit einer Funktion $E [mm] \to [/mm] V [mm] \cup [V]^2$, [/mm] die jeder Kante ihre - ein oder zwei - Endecken zuordnet. Auch ein Multigraph kann also Kanten und Schlingen haben.
Also zum einen versteh ich die zweite Definition an sich nicht, was will sie mir sagen?
Und die zweite Definition scheint doch was anderes zu sein als die erste, oder?
Weil die erste sagt ja, das ein Multigraph ein Graph ist, der Mehrfachkanten hat.
Und die zweite sagt, dass auch ein Multigraph Mehrfachkanten haben kann, was ja besagt, dass es auch andere Graphen außer Multigraphen zu geben scheint, die Mehrfachkanten enthalten können.
Das wiederrum schließt ja die erste Definition doch aus, weil sie sagt, das solche Graphen dann eben Multigraphen sind...
Äh, ja, irgendwie bin ich grad verwirrt...
Kann mir jemand weiterhelfen?
Danke, LG, Nadine
P.S.: Parallele Kanten sind doch Mehrfachkanten, oder?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 21:43 Do 03.09.2009 | | Autor: | koepper |
Hallo Nadine,
> Also in meinem einen Buch steht, dass das Graphen sind, in
> denen parallele Kanten zugelassen sind.
genau, und auch Schlingen.
>
> Und in meinem anderen Buch steht folgendes:
>
> Ein Multigraph ist ein Paar [mm](V,E)[/mm] disjunkter Mengen (von
> Ecken und Kanten) zusammen mit einer Funktion [mm]E \to V \cup [V]^2[/mm],
> die jeder Kante ihre - ein oder zwei - Endecken zuordnet.
> Auch ein Multigraph kann also Kanten und Schlingen haben.
>
> Also zum einen versteh ich die zweite Definition an sich
> nicht, was will sie mir sagen?
Bitte präzisiere deine Frage etwas. Als Mathe-Student muss man solche Definitionen lesen können. Was genau verstehst du nicht?
> Und die zweite Definition scheint doch was anderes zu sein
> als die erste, oder?
die 2. Def. ist formaler, das ist alles.
> Weil die erste sagt ja, das ein Multigraph ein Graph ist,
> der Mehrfachkanten hat.
nicht "hat" sondern "haben darf". Das Wort Multigraph will nur betonen, daß Schlingen und parallele Kanten zugelassen sind. Oft möchte man die nämlich ausschließen, weil man dann wesentlich weitergehende theoretische Aussagen treffen kann. Jeder Graph ist ein Multigraph in diesem Sinne. Schließt man Schlingen und parallele Kanten aus, nennt man solche Graphen auch "schlicht".
> P.S.: Parallele Kanten sind doch Mehrfachkanten, oder?
ja
LG
Will
|
|
|
| |
|
| Status: |
(Frage) beantwortet | | Datum: | 11:50 Sa 12.09.2009 | | Autor: | Pacapear |
Hallo Will!
> > Und in meinem anderen Buch steht folgendes:
> >
> > Ein Multigraph ist ein Paar [mm](V,E)[/mm] disjunkter Mengen (von
> > Ecken und Kanten) zusammen mit einer Funktion [mm]E \to V \cup [V]^2[/mm],
>
> > die jeder Kante ihre - ein oder zwei - Endecken zuordnet.
> > Auch ein Multigraph kann also Kanten und Schlingen
> haben.
> >
> > Also zum einen versteh ich die zweite Definition an sich
> > nicht, was will sie mir sagen?
>
> Bitte präzisiere deine Frage etwas. Als Mathe-Student muss
> man solche Definitionen lesen können. Was genau verstehst
> du nicht?
Ich verstehe folgendes nicht:
1) Die Abbildung [mm]E \to V \cup [V]^2[/mm], irgendwie kann ich den Wertebereich [mm]V \cup [V]^2[/mm] nicht fassen. Welche Menge ist das genau? Ich kann daraus irgendwie nicht ablesen, dass einer Kante ihre ein oder zwei Endknoten zugewiesen werden.
2) Die Aussage "Auch ein Multigraph kann also Kanten und Schlingen haben.". Was bedeutet denn hier das Wörtchen auch? Welche Graphen können das denn noch (also Kanten und Schlingen haben)? Ich dachte, dass gerade nur Multigraphen eben Kanten und Schlingen haben können... ![[nixweiss]](/images/smileys/nixweiss.gif "[nixweiss]")
LG, Nadine
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 12:47 Mo 14.09.2009 | | Autor: | koepper |
Hallo Nadine,
> > > Und in meinem anderen Buch steht folgendes:
> > >
> > > Ein Multigraph ist ein Paar [mm](V,E)[/mm] disjunkter Mengen (von
> > > Ecken und Kanten) zusammen mit einer Funktion [mm]E \to V \cup [V]^2[/mm],
>
> >
> > > die jeder Kante ihre - ein oder zwei - Endecken zuordnet.
> > > Auch ein Multigraph kann also Kanten und Schlingen
> > haben.
> > >
> > > Also zum einen versteh ich die zweite Definition an sich
> > > nicht, was will sie mir sagen?
> >
> > Bitte präzisiere deine Frage etwas. Als Mathe-Student muss
> > man solche Definitionen lesen können. Was genau verstehst
> > du nicht?
>
>
>
> Ich verstehe folgendes nicht:
>
> 1) Die Abbildung [mm]E \to V \cup [V]^2[/mm], irgendwie kann ich den
> Wertebereich [mm]V \cup [V]^2[/mm] nicht fassen. Welche Menge ist
> das genau? Ich kann daraus irgendwie nicht ablesen, dass
> einer Kante ihre ein oder zwei Endknoten zugewiesen
> werden.
[mm]E \to V \cup [V]^2[/mm]
Die eckigen Klammern sind mir auch schleierhaft. Ansonsten ist das eine Abbildung, die jeder Kante entweder einen Knoten (für den Fall der Schlinge) oder ein geordnetes Paar aus zwei Knoten (das sind dann die beiden Endknoten) zuordnet.
Anzumerken wäre, dass das geordnete Paar eigentlich auf eine gerichtete Kante (manchmal auch Pfeil genannt) hindeutet.
Graphen mit gerichteten Kanten nennt man auch Digraphen (für "directed").
> 2) Die Aussage "Auch ein Multigraph kann also Kanten und
> Schlingen haben.". Was bedeutet denn hier das Wörtchen
> auch? Welche Graphen können das denn noch (also Kanten und
> Schlingen haben)? Ich dachte, dass gerade nur Multigraphen
> eben Kanten und Schlingen haben können...
"auch" scheint mir hier nichts wesentliches zu bedeuten.
Parallele Kanten und Schlingen sind nur bei Multigraphen erlaubt.
LG
Will
|
|
|
|
