Nichtisomorphe Graphen < Graphentheorie < Diskrete Mathematik < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:54 Mo 06.07.2009 | | Autor: | wurmi86 |
| Aufgabe | | alle einfache Graphen(nichtisomorph) mit 6 knoten und 5 kanten |
Also ich komm auf 7. gibt es mehr? gibt es auch einen idiotensicheren weg, immer alle zu finden, bzw die anzahl zu bestimmen?
....
und ja, es ist wieder eine Vogelsche Aufgabe =)
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
|
|
| |
|
> alle einfache Graphen(nichtisomorph) mit 6 knoten und 5
> kanten
> Also ich komm auf 7. gibt es mehr? gibt es auch einen
> idiotensicheren weg, immer alle zu finden, bzw die anzahl
> zu bestimmen?
Sollen die Graphen auch zusammenhängend
sein ? Wenn nicht, gibt es wohl deutlich mehr !
LG
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 23:38 Mo 06.07.2009 | | Autor: | wurmi86 |
von zusammenhängend steht nix in der aufgabenstellung. daher vermute ich alles ist möglich..
und wenn das so ist . wie viel wird denn "deutlich mehr" sein?
|
|
|
| |
|
> von zusammenhängend steht nix in der aufgabenstellung.
> daher vermute ich alles ist möglich..
> und wenn das so ist . wie viel wird denn "deutlich mehr"
> sein?
Das hab ich mir nicht im Detail überlegt,
aber man könnte so vorgehen:
Kombinatorische Überlegung, wie man
den Graph in zusammenhängende
Subgraphen (inkl. isolierte Punkte
ohne Kanten) aufteilen kann:
1+1+1+3 (geht nicht, weil man
mit nur 3 Punkten keinen einfachen
Graph mit 5 Kanten machen kann,
und Schleifen sind ja verboten)
1+1+1+1+1+1
1+1+1+1+2
1+1+2+2
1+1+1+3
(geht alles nicht)
1+1+4 (das sollte auf verschiedene Arten gehen)
1+2+3 (geht nicht, weil max. 4 Kanten möglich)
2+4
1+5
3+3
6
Dann innerhalb der verschiedenen
möglichen Gruppen die nicht-isomorphen
Fälle skizzieren und zählen. Das ist noch
nicht idiotensicher, aber für normal Begabte
machbar ...
LG Al-Chw.
|
|
|
|
