Kruskal und Graph < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:05 So 16.02.2014 | | Autor: | Klass |
| Aufgabe | | Bestimmen Sie den minimalen Baum für einen ungerichteten Graphen mit dem Kruskal Algorithmus. Geben Sie jeweils die Kanten in der Reihenfolge an, in der Sie hinzugefügt bzw. weggelassen worden sind. |
Hallo,
ich habe eine allgemeine Frage:
Wenn man die besuchten Kanten angibt, macht man das ja in der Form:
{a,b} oder (a,b), wenn ich aber einen ungerichteten Graphen habe, in welcher Reihenfolge gebe ich dann die Elemente in der Menge an?
(a,b) oder (b,a)? Eigentlich handelt es sich doch um eine Menge, daher ist doch die Reihenfolge der Elemente egal.
Oder?
Danke im Voraus.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 06:26 Mo 17.02.2014 | | Autor: | tobit09 |
Hallo Klass!
> Wenn man die besuchten Kanten angibt, macht man das ja in
> der Form:
>
> {a,b} oder (a,b), wenn ich aber einen ungerichteten Graphen
> habe, in welcher Reihenfolge gebe ich dann die Elemente in
> der Menge an?
>
> (a,b) oder (b,a)? Eigentlich handelt es sich doch um eine
> Menge, daher ist doch die Reihenfolge der Elemente egal.
>
> Oder?
Die genauen Definitionen von (gerichteten bzw. ungerichteten) Graphen und somit von Kanten sind leider nicht einheitlich. Wie habt ihr einen ungerichteten Graphen formal definiert?
Wenn die Kanten in ungerichteten Graphen bei euch Mengen sind, solltest du Mengenklammern [mm] ($\{$ und $\}$) [/mm] und keine runden Klammern verwenden. [mm] $\{a,b\}$ [/mm] und [mm] $\{b,a\}$ [/mm] bezeichnen die gleiche Menge. Die Reihenfolge ist also in der Tat egal.
Wenn ungerichtete Graphen bei euch spezielle gerichtete Graphen sind, solltest du runde Klammern verwenden. Es gilt zwar [mm] $(a,b)\not=(b,a)$ [/mm] für [mm] $a\not=b$, [/mm] aber für die Notation der Durchführung des Algorithmus' sollte es aus meiner Sicht genügen, eine beliebige der beiden Kanten $(a,b)$ und $(b,a)$ anzugeben.
Viele Grüße
Tobias
|
|
|
|
