schlichte Graphen mit n Ecken < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 22:56 Do 26.06.2008 | | Autor: | schennie |
Guten Abend :)
Ich sitze mal seit längerem an unserem Matheübungsblatt und versuche eine Lösung für die folgende Aufgabenstellung zu finden:
"Wie viele schlichte Graphen mit n Ecken gibt es?"
Dazu ist zu sagen, dass es sich bei uns immer um ungerichtete Graphen handelt.
Ich habe mir jetzt überlegt, dass die Formel dazu lauten könnte: [mm] 2^{n\choose 2}
[/mm]
Im Aufgabenteil b) ist mir dann aber aufgefallen, dass dies nicht stimmen kann. Da da die Aufgabenstellung lautet alle schlichten Graphen mit 4 Ecken zu finden. Laut meiner Formel kommt da 64 raus. Ich vermute also, dass das die Formel ist für alle Graphen mit n Ecken und nicht nur für die schlichten. Wie kann ich denn jetzt auf die Anzahl der schlichten Graphen mit n Ecken kommen?
Vielen Dank für eure Hilfe!
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 00:06 Fr 27.06.2008 | | Autor: | koepper |
Guten Abend,
> "Wie viele schlichte Graphen mit n Ecken gibt es?"
>
> Dazu ist zu sagen, dass es sich bei uns immer um
> ungerichtete Graphen handelt.
>
> Ich habe mir jetzt überlegt, dass die Formel dazu lauten
> könnte: [mm]2^{n\choose 2}[/mm]
so ist es.
> Im Aufgabenteil b) ist mir dann aber aufgefallen, dass dies
> nicht stimmen kann. Da da die Aufgabenstellung lautet alle
> schlichten Graphen mit 4 Ecken zu finden. Laut meiner
> Formel kommt da 64 raus.
stimmt auch.
> Ich vermute also, dass das die
> Formel ist für alle Graphen mit n Ecken und nicht nur für
> die schlichten.
Wenn du noch Schlingen und Mehrfachkanten zuläßt, gibt es natürlich unendlich viele Graphen.
Du kannst ja unendlich viele Kanten hinzufügen, wo du willst.
> Wie kann ich denn jetzt auf die Anzahl der
> schlichten Graphen mit n Ecken kommen?
Die Lösung hast du schon. Wo ist dein Zweifel?
LG
Will
|
|
|
|
