Alle möglichen Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:48 Mi 25.06.2008 | | Autor: | picke |
| Aufgabe | | Ermitteln Sie die Anzahl der möglichen schlichten Graphen mit 4 Knoten |
hallo, bin zwar student der informationstechnik, und hoffe daher, das die frage hier richtig ist.
also das wär meine meinung:
es gibt 6 mögliche wege, AB, AC, AD, BC, BD, CD
die anzahl der möglichkeiten ist meiner meinung nach also eine permutation dieser 6 wege,
also 6! --> 720 möglichkeiten
aber irgendwie kommt mir das doch ein wenig viel vor...
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 22:25 Mi 25.06.2008 | | Autor: | Bastiane |
Hallo picke!
> Ermitteln Sie die Anzahl der möglichen schlichten Graphen
> mit 4 Knoten
Was ist mit einem schlichten Graphen gemeint? Ein einfacher Graph (also ohne Schleifen)? Oder soll er auch noch planar sein? Und bestimmt auch noch zusammenhängend?
> hallo, bin zwar student der informationstechnik, und hoffe
> daher, das die frage hier richtig ist.
![[daumenhoch]](/images/smileys/daumenhoch.gif "[daumenhoch]")
> also das wär meine meinung:
>
> es gibt 6 mögliche wege, AB, AC, AD, BC, BD, CD
Was genau meinst du mit Wegen? Also wenn du vier Knoten hast, dann gibt es obige vier Möglichkeiten für eine Kante. Nun muss ein Graph mit vier Knoten aber nicht genau alle diese Kanten besitzen. Kann es sein, dass du das so gedacht hattest in deiner Berechnung?
Ich würde alle Graphen mit einer Kante zählen, dann alle mit zwei usw. bzw., falls der Graph zusammenhängend sein soll, alle Graphen mit 3 Kanten, alle mit 4 usw.
Viele Grüße
Bastiane
![[cap]](/images/smileys/cap.gif "[cap]")
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:36 Mi 25.06.2008 | | Autor: | picke |
Ich hoff das hilft weiter:
Eing graph g heißt schlicht, wenn er weder schlingen noch mehrfachkannten hat.
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:41 Mi 25.06.2008 | | Autor: | Bastiane |
Hallo picke!
> Ich hoff das hilft weiter:
>
> Eing graph g heißt schlicht, wenn er weder schlingen noch
> mehrfachkannten hat.
Aha, also muss er weder planar noch zusammenhängend sein. Dann würde ich alle Graphen mit einer Kante, alle mit zwei Kanten und so weiter versuchen zu finden. Ach ja, und isomorphe Graphen zählen wohl nur als eins, oder?
Viele Grüße
Bastiane
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig | | Datum: | 22:49 Mi 25.06.2008 | | Autor: | koepper |
Hallo Bastiane,
alle schlichten Graphen mit 4 Knoten sind planar. Probier's mal aus 
LG
Will
|
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:46 Mi 25.06.2008 | | Autor: | koepper |
Hallo Andreas,
> Ermitteln Sie die Anzahl der möglichen schlichten Graphen
> mit 4 Knoten
> es gibt 6 mögliche wege, AB, AC, AD, BC, BD, CD
du meinst Kanten nicht Wege.
> die anzahl der möglichkeiten ist meiner meinung nach also
> eine permutation dieser 6 wege,
> also 6! --> 720 möglichkeiten
>
> aber irgendwie kommt mir das doch ein wenig viel vor...
viel zu viel...
Ein Graph ist ein Paar G=(V, E).
V ist festgelegt, E ist eine beliebige Teilmenge der oben genannten Menge von 6 möglichen Kanten
Es gibt [mm] $2^6 [/mm] = 64$ solcher Teilmengen. Das ist die Mächtigkeit der Potenzmenge.
LG
Will
|
|
|
|
