Mathematik online lernen im Mathe-Forum. Nachhilfe online

Startseite » Forum » Anzahl Graphen

Anzahl Graphen

Universität / Fachhochschule

Graphentheorie

Tags: Graphentheorie

student11 aktiv_icon

19:27 Uhr, 04.08.2012

Hallo zusammen

Könnt ihr mir vielleicht sagen, ob es eine einfache Formel gibt, die Anzahl Graphen zu einer gegebenen Knotenzahl zu berechnen (ungerichtet, nicht zwingend zusammenhängend).

Also wenn die Knoten ja nummeriert wären, habe ich mir überlegt, dass es

\sum_{i = 1}^{n} (\begin{matrix} n \\ i \end{matrix}) = 2^{n}

Graphen wären, aber das stimmt irgendwie nicht, denn dann habe ich Loops dabei, ich möchte aber einfache Graphen.. Oder was geht hier falsch?

Aber eigentlich gehts mir eher um nicht nummerierte Graphen, also die Anzahl nicht isomorpher Graphen mit einer gegebenen Anzahl Knoten.. Brauche da noch nicht mal dringend eine Formel, die ersten paar Zahlen genügen..

Wie

z . B

. mit Bäumen gibt es ja

1,1,2,3,6

mit

n = 1,2, . .

. Knoten..

Gibt es eine Liste mit Zahlen der planaren Graphen?

Bin auch schon auf Listen mit allen Hamiltongraphen,.. etc gestossen, fand die ziemlich hilfreich, nur konnte ich für dieses Problem leider keien finden..

Vielen Dank

Für alle, die mir helfen möchten (automatisch von OnlineMathe generiert):
"Ich möchte die Lösung in Zusammenarbeit mit anderen erstellen."

student11 aktiv_icon

19:45 Uhr, 04.08.2012

garsia.math.yorku.ca~zabrocki/math3260w03/nall.html

ach hier hab ichs gefunden..

Könnte trotzdem noch jemand was zu der obigen Formel mit Summe schreiben, was da schief geht?

hagman aktiv_icon

21:07 Uhr, 04.08.2012

Wie sollen wir dir sagen was an der Formel falsch ist? Du hast ja keinen wirklichen Grund angegeben, weshalb sie Formel so richtig sein sollte. :-)

Für

n

nummerierte Knoten gibt es genau

(\begin{matrix} n \\ 2 \end{matrix})

Kandidaten für Kanten. Da jede unabhängig von den anderen entweder zum Graphen gehören kann oder nicht, erhält man

2^{\frac{n \cdot (n + 1)}{2}}

Sehr hilfreich ist für deine art der Fragenstellung www.oeis.org: Wenn du die ersten paar Zahlen zu Fuß ausrechnest und die Werte eingibst, wird dir aller Wahrscheinlichkeit nach die gesuchte Folge mit mehr Gliedern und weiteren Informationen ausgespuckt.
Beispielsweise ergeben sich bei Suchbegriff "1,1,2,3,6"

368

Ergebnisse. Bereits das zweite Resultat

(A 00055)

hat in seiner Beschreibung "Number of trees with

n

unlabeled nodes", ist also das, was du suchtest, so dass du jetzt weißt, dass die Folge mit

11, 23, 47, 106, 235, 551, 1301, 3159

weitergeht (und für

n = 0

und

n = 1

ebenfalls sinnvoll mit dem Wert 1 belegt werden kann).

student11 aktiv_icon

21:14 Uhr, 04.08.2012

Diese Argumentation ergibt Sinn..

Weiss nicht, was ich vorher überlegt habe. Dachte, es gäbe maximal

n

Kanten und ich kann dann für jede Kante die entsprechenden Knoten, die involviert sind, auswaählen..

Wenn ich das jetzt korrigiere auf

(\begin{matrix} n \\ 2 \end{matrix})

Kanten, dann erhalte ich

\sum_{i = 0}^{(\begin{matrix} n \\ 2 \end{matrix})} (\begin{matrix} n \\ i \end{matrix}),

denn ich kann ja für jedes Mal, wenn ich mich entscheide,

i

Kanten zu nehmen, aussuchen, welche Knoten ich dazu aussuche.

Das gäbe ja dann

2^{(\begin{matrix} n \\ 2 \end{matrix})}

und würde übereinstimmen...?? Bin mir aber etwas unsicher..

Vielen DAnk für den Tipp mit den Folgen, kann ich super brauchen.. :-)

hagman aktiv_icon

21:17 Uhr, 04.08.2012

Wenn es unbedingt als Summe gehen soll, eher

\sum_{i = 0}^{(\begin{matrix} n \\ 2 \end{matrix})} (\begin{matrix} (\begin{matrix} n \\ 2 \end{matrix}) \\ i \end{matrix}) = 2^{(\begin{matrix} n \\ 2 \end{matrix})}

aber die direkte Argumentation (oder auch: Anzahl der Teilmengen einer

(\begin{matrix} n \\ 2 \end{matrix}) -

elementigen Menge) ist

m . E

. weniger verwirrend

student11 aktiv_icon

21:20 Uhr, 04.08.2012

Stimmt, deine Variante ist um einiges einfacher.. Werde auf diese zurückgreifen..

Könntest du mir trotzdem (nun ist meine Neugierde geweckt.. :-)

),

weshalb denn obige Gleichung mit Summe dasselbe ergibt..

Also man summiert über alle

i

von 0 bis

(\begin{matrix} n \\ 2 \end{matrix}),

also über alle möglichen Anzahlen von Kanten. DAzu wähle ich aus allen

(\begin{matrix} n \\ 2 \end{matrix})

möglichen Kanten diejenigen

i

aus, die ich gerne wählen möchte?

klingt kompliziert..

hagman aktiv_icon

22:52 Uhr, 04.08.2012

Bekanntlich ist

{(a + b)}^{m} = \sum_{i = k}^{m} (\begin{matrix} m \\ k \end{matrix}) a^{k} b^{m - k}

(das ist letztlich die ihrem Namen entsprechende Definition der Binomialkoeffizienten).
Mit

a = b = 1

folgt also

2^{m} = \sum_{i = k}^{m} (\begin{matrix} m \\ k \end{matrix})

.
Und mit

m = (\begin{matrix} n \\ 2 \end{matrix})

der obige Spezialfall.

student11 aktiv_icon

23:17 Uhr, 04.08.2012

Alles klar, vielen DAnk für die Hilfe.

1019891

1019876

	Status: nicht eingeloggt	Noch nicht registriert?