gerichtete Graphen |
| 13.05.2010, 00:11 | mlk | Auf diesen Beitrag antworten » | ||||
| gerichtete Graphen hallo, ich habe eine Frage, die ich leider ohne weitere Hilfe nicht lösen kann 
Wie viele ungerichtete Graphen G = (V;E) mit |V| = n gibt es? (V ist die Knotenmenge, E die Kantenmenge, n?IN.) Meine Ideen: Es gilt V >= E, also müsste ja |E| <= n sein... jetzt komme ich irgendwie nicht weiter... |
||||||
| 13.05.2010, 00:16 | Abakus | Auf diesen Beitrag antworten » | ||||
| RE: gerichtete Graphen Hallo! Du kannst ja überlegen, wieviele Graphen es dann mit 0, 1, 2, ... vielen Kanten gibt? Hilft das? Grüße Abakus 
|
||||||
| 13.05.2010, 00:20 | mlk | Auf diesen Beitrag antworten » | ||||
ja, danke
gibt es eigentlich eine Formel dazu?? Ich finde leider keins... |
||||||
| 13.05.2010, 00:34 | Abakus | Auf diesen Beitrag antworten » | ||||
RE: gerichtete Graphen
Schau dir mal ein Beispiel an, dann siehst du schon, dass das nicht hinkommt. Ja, für sowas gibt es Formeln. Du willst alle Graphen zählen und isomorphe Graphen nicht identifizieren: also zB sind alle Graphen mit einer Kante ja isomorph ? Grüße Abakus
|
||||||
| 13.05.2010, 08:26 | Mystic | Auf diesen Beitrag antworten » | ||||
RE: gerichtete Graphen
Oder man kann - von der anderen Seite kommend - den vollständigen Graphen betrachten, der alle möglichen Kanten enthält, und dann eventuell welche wieder weglassen, was hier vielleicht sogar einfacher ist... P.S. Ist ja lustig, das der Threadersteller in der Überschrift von gerichteten Graphen spricht, es aber dann tatsächlich um ungerichtete Graphen geht... Na wat denn nun? 
Angesichts solcher Probleme würde ich die Abzählung von "nichtisomorphen" Graphen mit gegebener Knotenanzahl nicht einmal "andenken"... |
||||||
| 13.05.2010, 16:23 | mlk | Auf diesen Beitrag antworten » | ||||
Also es sollte auf jeden Fall ein ungerichteter Graph sein
Ich habe es mal mit ein paar Zahlen ausprobiert: Für n = 2 sind die Knoten größer als die Kanten (-anzahl). Für n = 3 ist Knoten = Kante. Ab n >=4 steigt die Anzahl der Kanten schneller als die Anzahl der Knoten... Nun, die Formel habe ich gesucht nur leider nicht gefunden... Wenn zBsp: |V| = 4 ist, sind es dann 6 ungerichtete Graphen?? ( G = (4,6) ) 
|
||||||
| Anzeige | ||||||
|
|
||||||
| 13.05.2010, 18:36 | Abakus | Auf diesen Beitrag antworten » | ||||
Also 2 Fragen für dich: Wenn du n Knoten hast, wieviele Kanten kann dann dein Graph maximal haben? (Mehrfachkanten und Schlingen nicht zulässig) ? Wenn du n Knoten und k Kanten hast, wieviele Graphen kannst du damit bilden? (Isomorphie hier nicht berücksichtigt) Grüße Abakus
|
||||||
| 13.05.2010, 19:25 | mlk | Auf diesen Beitrag antworten » | ||||
Also deine erste Frage: Anzahl Knoten - Anzahl Kanten, oder wenn wir n Knoten haben gibt es max. n+1 Kanten.... deine zweite Frage: G=(n,k) hmm ja gute Frage, bei uns im Skript steht davon auch leider nix
|
||||||
| 13.05.2010, 21:21 | Abakus | Auf diesen Beitrag antworten » | ||||
Bei 4 Knoten kann ich bereits 6 Kanten unterbringen (du auch?): das spricht nicht für (n+1) - viele.
Analog wäre etwa: du hast 49 Kugeln und wählst davon nun 6 aus, wieviele Möglichkeiten gibt es (Lotto) ? Grüße Abakus
|
||||||
| 13.05.2010, 22:16 | mlk | Auf diesen Beitrag antworten » | ||||
Hallo Abakus
also die Frage mit dem Lotto die Lösung wäre (49 6) (untereinander geschrieben) ja da hast du recht bei 4 Knoten habe auch ich 6 Kanten, und mit steigender Anzahl der Knoten steigt die Anzahl der Kanten noch schneller... Wo kann ich denn die formel dazu finden?? |
||||||
| 13.05.2010, 22:19 | Abakus | Auf diesen Beitrag antworten » | ||||
Wähle einen Knoten und verbinde den mit den anderen, macht (n-1) Kanten. Dann den nächsten Knoten und verbinde diesen, macht nur noch (n-2) Kanten (denn mit dem von oben hast du ja schon eine Verbindung). Siehst du wie es weitergeht und was demzufolge aufzusummieren ist? Grüße Abakus
|
||||||
| 13.05.2010, 22:22 | mlk | Auf diesen Beitrag antworten » | ||||
Ja aber wie bekomme ich denn die ANZAHL der ungerichteten Graphen?? Kannst du nicht ein Beispiel machen, wäre echt nett 
|
||||||
| 13.05.2010, 23:09 | Abakus | Auf diesen Beitrag antworten » | ||||
Indem du erstmal obiges Frage mit den Kanten löst. Denn aus der Gesamtzahl der möglichen Kanten wählst du schließlich was aus und bildest Kombinationen: auch hier musst du wieder aufsummieren. Aber ein Beispiel: 4 Knoten: dann gibt es maximal 6 Kanten. Wenn du die Gesamtzahl der Graphen haben willst: betrachte die Anzahlen 0, 1, 2, ..., 6 Kanten aus diesen 6 Kanten auszuwählen und addiere dann. Das wäre die gesuchte Gesamtanzahl. Grüße Abakus
|
||||||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
