Graphen < Sonstiges < Hochschule < Mathe < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 02:35 So 27.02.2005 | | Autor: | newbie |
Nicht erschrecken bei womöglich langen Text, bei den meisten Aufgaben geht es mir vorallem um ein richtig oder falsch (oder Verbesserungsvorschlag, dass es auch formhalber richtig ist). Die meisten Aufgaben gehen also relativ schnell...
Also Graph soll jetzt endlich, ungerichtet, schlingenfrei und ohne Mehrfachkanten sein.
1.
Ist [mm] K_{4} [/mm] ein Teilgraph des [mm] K_{4,4}? [/mm] Mit Begründung.
Meine Antwort wäre nein, da ich bei einem [mm] K_{4,4} [/mm] keine 4 Ecken habe, die alle untereinander verbunden sind... würde das schon ausreichen oder einfach schnell aufzeichnen und es damit begründen?
2.
Wieviele nicht isomorphe Graphen, nichtisomorphen bipartiten Graphen und vollständig bipartite Graphen mit 8 Ecken gibt es?
Also die Frage könnte ich nur durch aufzeichnen und rumprobieren beantworten oder gibt es einen anderen Weg?
3.
Für welche m und n ist [mm] K_{m,n} [/mm] regulär?
Regulär heißt ja, dass alle Ecken den gleichen Grad haben, also muss m=n sein (wobei ich doch bei [mm] K_{m,n} [/mm] von einem vollständig bipartiten graphen ausgehen kann, oder?).
Für welche m und n enthält der [mm] K_{m,n} [/mm] keine Kreise?
Meiner Meinung nach nur für alle m=1 und n beliebige oder eben umgedreht, oder gibt es noch mehr?
4
Zeigen sie, dass für unendliche Graphen nicht gilt, dass die Anzahl der Ecken von ungeradem Grad gerade sein muss...
Naja, da es sich um unendliche Graphen handelt, kann ich ja beliebig Kanten anfügen. Auf jeder Kante von einem Knoten folgt zwar ein weitere Knoten, da der Graph in dem Sinne aber kein Ende hat, kann ich dies immer so fortsetzen... Also anders wüsste ich es nicht zu erklären...
5.
Bestimmen sie alle zusammenhängende Teilgraphen des [mm] K_{5}, K_{2,5},P_{15} [/mm] und [mm] C_{20} [/mm] Hier geht es mir nur darum, ob ich es verstanden habe, es also alles richtig ist:
Bei [mm] K_{5} [/mm] sind alle [mm] K_{5} [/mm] zwischen 10Kanten und 4 Kanten, wobei der Graph natürlich zusammenhängend bleiben muss, dann alle [mm] K_{4} [/mm] mit 6-3 Kanten, alle [mm] K_{3} [/mm] mit 3-2 Kanten, alle [mm] K_{2} [/mm] mit einer Kante und schließlich [mm] K_{1}.
[/mm]
Bei [mm] K_{2,5} [/mm] alle [mm] K_{n,m} [/mm] wobei [mm] 0\le m\le [/mm] 5 und [mm] 1\le n\le [/mm] 2 und dann noch [mm] 1\le m\le [/mm] 5 mit [mm] 0\le n\le2.
[/mm]
Bei [mm] P_{15} [/mm] alle Wege mit weniger als 15 aber mit mindestens einer Ecke. Und bei [mm] C_{20} [/mm] alle Wege mit maximal 20 aber mindestens 1 Ecke.
6.
Bestimmen Sie alle Graphen mit n>2 Knoten, in denen zwischen jedem Paar von Knoten genau zwei Wege existieren.
Können doch nur Kreise sein, ODER?
7.
Wieviele Kanten besitzt ein kreisfreier Graph mit n Knoten und c Komponenten?
m=n-c Richtig?
8.
Zeigen Sie, dass in jedem Graph mindestens zwei Ecken vom gleichen Grad existieren.
Hm, ich kann es mir vorstellen und könnte es auch irgendwie umständlich erklären, aber formal korrekt würde ich es vermutlich nicht so hinbekommen... Womöglich werde ich hier später noch einen eigene Ansatz reinschreiben, werde mich aber ersteinmal hinlegen...
9.
Zeigen Sie, das für die Kantenzahl des n-dimensionalen Hyperwürfels gilt:
[mm] |K(Q_{n})|=n*2^{n-1}
[/mm]
Ähm, Verständnisproblem. Ist n jetzt die Anzahl der Ecken und K die Anzahl der Kanten oder wie habe ich die Formel zu verstehen?
10.
Für welche m und n enthält [mm] K_{m,n} [/mm] einen Eulerkreis?
Müssten alle gerade m und n sein.
Für welche m und n ist der [mm] K_{m,n} [/mm] ein Baum?
Naja, wenn m oder n eins ist, dann ist [mm] K_{m,n} [/mm] ein Baum, richtig?
11.
Zeigen Sie, dass in jedem zusammenhängenden bipartiten Graphen G=(E,K) gilt |E| [mm] \le [/mm] 2|V|-4 Wobei ich denke, dass mit V die Kanten und E die Ecken gemeint sind... Hier wäre ich ersteinmal über einen Ansatz dankbar...
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 17:28 So 27.02.2005 | | Autor: | Sigrid |
Hallo newbie
Ich habe nicht sehr viel Ahnung von Graphentheorie, ich fange erst an, mich ein wenig damit zu beschäftigen. Deshalb versuche ich erstmal nur bei wenigen Aufgaben eine Antwort.
> Nicht erschrecken bei womöglich langen Text, bei den
> meisten Aufgaben geht es mir vorallem um ein richtig oder
> falsch (oder Verbesserungsvorschlag, dass es auch
> formhalber richtig ist). Die meisten Aufgaben gehen also
> relativ schnell...
>
> Also Graph soll jetzt endlich, ungerichtet, schlingenfrei
> und ohne Mehrfachkanten sein.
>
> 1.
> Ist [mm]K_{4}[/mm] ein Teilgraph des [mm]K_{4,4}?[/mm] Mit Begründung.
> Meine Antwort wäre nein, da ich bei einem [mm]K_{4,4}[/mm] keine 4
> Ecken habe, die alle untereinander verbunden sind... würde
> das schon ausreichen oder einfach schnell aufzeichnen und
> es damit begründen?
Ich würde schon etwas genauer begründen. Wenn du irgendeinen bipartiten Graphen [mm]K_{4,4}[/mm] hast, und du wählst 4 Punkte beliebig aus, dann liegen wenigstes 2 Knoten in einer Klasse und sind damit nicht durch eine Kante verbunden, d.h. die 4 Knoten sind nicht Knoten eines vollständigen Graphen.
> 2.
> Wieviele nicht isomorphe Graphen, nichtisomorphen
> bipartiten Graphen und vollständig bipartite Graphen mit 8
> Ecken gibt es?
> Also die Frage könnte ich nur durch aufzeichnen und
> rumprobieren beantworten oder gibt es einen anderen Weg?
Ich denke, zeichnen ist zumindest bei beliebigen Graphen sehr aufwendig. Ich würde mir überlegen, wie viele Kanten es jeweils geben kann. Wenn du beliebige Graphen untersuchst, kann es z.B. 8 Ecken und 0 Kanten geben. Diese Graphen sind alle isomorph. Das gleich gilt auch bei 8 Knoten und einer Kante. Bei 2 Kanten hast du 2 nicht isomorphe Graphen. Einmal gehen die beiden Kanten vom selben Ecke aus, im zweiten Fall nicht.
Usw.
Alle Fälle habe ich mir noch nicht überlegt. Vielleicht kann auch jemand mal erst prüfen, ob ich nicht nur Mist schreibe.
Beim vollständigen bipartiten Graphen vermute ich, dass es die nichtisomorphen Graphen [mm]K_{1,7}[/mm], [mm]K_{2,6}[/mm], [mm]K_{3,5}[/mm] und [mm]K_{4,4}[/mm] gibt.
> 3.
> Für welche m und n ist [mm]K_{m,n}[/mm] regulär?
> Regulär heißt ja, dass alle Ecken den gleichen Grad haben,
> also muss m=n sein (wobei ich doch bei [mm]K_{m,n}[/mm] von einem
> vollständig bipartiten graphen ausgehen kann, oder?).
Ich denke auch, sonst macht die Frage eigentlich keinen Sinn.
> Für welche m und n enthält der [mm]K_{m,n}[/mm] keine Kreise?
> Meiner Meinung nach nur für alle m=1 und n beliebige oder
> eben umgedreht, oder gibt es noch mehr?
Wenn du wieder von vollständigen bipartiten Graphen ausgehst, wohl nicht.
> 4
> Zeigen sie, dass für unendliche Graphen nicht gilt, dass
> die Anzahl der Ecken von ungeradem Grad gerade sein
> muss...
> Naja, da es sich um unendliche Graphen handelt, kann ich
> ja beliebig Kanten anfügen. Auf jeder Kante von einem
> Knoten folgt zwar ein weitere Knoten, da der Graph in dem
> Sinne aber kein Ende hat, kann ich dies immer so
> fortsetzen... Also anders wüsste ich es nicht zu
> erklären...
Da verstehe ich die Aufgabenstellung nicht. Welche Eigenschaft soll dieser Graph denn haben?
> 5.
> Bestimmen sie alle zusammenhängende Teilgraphen des [mm]K_{5}, K_{2,5},P_{15}[/mm]
> und [mm]C_{20}[/mm] Hier geht es mir nur darum, ob ich es verstanden
> habe, es also alles richtig ist:
> Bei [mm]K_{5}[/mm] sind alle [mm]K_{5}[/mm] zwischen 10Kanten und 4 Kanten,
> wobei der Graph natürlich zusammenhängend bleiben muss,
> dann alle [mm]K_{4}[/mm] mit 6-3 Kanten, alle [mm]K_{3}[/mm] mit 3-2 Kanten,
> alle [mm]K_{2}[/mm] mit einer Kante und schließlich [mm]K_{1}.
[/mm]
> Bei [mm]K_{2,5}[/mm] alle [mm]K_{n,m}[/mm] wobei [mm]0\le m\le[/mm] 5 und [mm]1\le n\le[/mm]
> 2 und dann noch [mm]1\le m\le[/mm] 5 mit [mm]0\le n\le2.
Das habe ich auch
[/mm]
> Bei [mm]P_{15}[/mm]
> alle Wege mit weniger als 15 aber mit mindestens einer
> Ecke. Und bei [mm]C_{20}[/mm] alle Wege mit maximal 20 aber
> mindestens 1 Ecke.
Hier muss ich passen.
> 6.
> Bestimmen Sie alle Graphen mit n>2 Knoten, in denen
> zwischen jedem Paar von Knoten genau zwei Wege
> existieren.
> Können doch nur Kreise sein, ODER?
Ein Weg darf ja Knoten durchaus mehrfach durchlaufen, nur Kanten nicht. Wenn das auch für den für den Endknoten gilt, genügt es, dass der Graph genau einen Kreis enthält, oder?
> 7.
> Wieviele Kanten besitzt ein kreisfreier Graph mit n Knoten
> und c Komponenten?
> m=n-c Richtig?
> 8.
> Zeigen Sie, dass in jedem Graph mindestens zwei Ecken vom
> gleichen Grad existieren.
> Hm, ich kann es mir vorstellen und könnte es auch
> irgendwie umständlich erklären, aber formal korrekt würde
> ich es vermutlich nicht so hinbekommen... Womöglich werde
> ich hier später noch einen eigene Ansatz reinschreiben,
> werde mich aber ersteinmal hinlegen...
> 9.
> Zeigen Sie, das für die Kantenzahl des n-dimensionalen
> Hyperwürfels gilt:
> [mm]|K(Q_{n})|=n*2^{n-1}
[/mm]
> Ähm, Verständnisproblem. Ist n jetzt die Anzahl der Ecken
> und K die Anzahl der Kanten oder wie habe ich die Formel zu
> verstehen?
> 10.
> Für welche m und n enthält [mm]K_{m,n}[/mm] einen Eulerkreis?
> Müssten alle gerade m und n sein.
> Für welche m und n ist der [mm]K_{m,n}[/mm] ein Baum?
> Naja, wenn m oder n eins ist, dann ist [mm]K_{m,n}[/mm] ein Baum,
> richtig?
> 11.
> Zeigen Sie, dass in jedem zusammenhängenden bipartiten
> Graphen G=(E,K) gilt |E| [mm]\le[/mm] 2|V|-4 Wobei ich denke, dass
> mit V die Kanten und E die Ecken gemeint sind... Hier wäre
> ich ersteinmal über einen Ansatz dankbar...
Mit den übrigen Aufgaben muss ich mich erst noch länger beschäftigen. Aber bis dahin kennst du wahrscheinlich auch schon die Lösungen. Wäre schön, wenn du sie hier angeben könntest.
Gruß Sigrid
|
|
|
|
