Nicht-Isomorphie < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:12 Mo 23.01.2006 | | Autor: | dump_0 |
Hallo.
Ich soll zeigen das es mind. [tex]2^{ \vektor{n \\ 2}}/{(n!)}[/tex] viele nicht-isomorphe Grahen mit n Knoten gibt.
Bekannt ist das es zwischen 2 Mengen mit je n elementen n! bijektive Abb. gibt.
Was muss ich aber tun um obige Sache zu beweisen ?
Ich weiß wie man den Binomialkoeffizient berechnet, aber das hilft mir irgendwie auch nich weiter :(
Mfg
[mm] dump_0
[/mm]
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 18:44 Mo 23.01.2006 | | Autor: | Hanno |
Hallo.
Es sei $G$ ein Graph mit $n$ Knoten. Eine Kante verbindet je zwei verschiedene Knoten; da es [mm] $\vektor{n\\ 2}$ [/mm] Knoten-Paare gibt, können maximal [mm] $\vektor{n\\2}$ [/mm] Kanten existieren; zur eindeutigen Bestimmung des Graphen ist für jede dieser Kanten ist zu entscheiden, ob sie im Graph enthalten ist oder nicht. Zur Konstruktion des Graphen auf diese Weise gibt es also [mm] $2^{\vektor{n\\ 2}}$ [/mm] Möglichkeiten.
Um isomorphe Graphen nicht mehrfach zu zählen, teilen wir zudem noch durch die Anzahl der Möglichkeiten, einen Graphen durch Umbenennung der Knoten in einen isomorphen Graphen überzuführen; diese Anzahl ist maximal $n!$.
Daraus ergibt sich das gewünschte Resultat.
Liebe Grüße,
Hanno
|
|
|
|
