Graphentheorie |
| 25.12.2004, 15:37 | knoten | Auf diesen Beitrag antworten » |
| Graphentheorie Für jeden knotenregulären Graphen vom Grad 3 ist die Knotenzusammenhangszahl gleich der Kantenzusammenhangszahl. Wie gehe ich das an? |
||
| 29.12.2004, 13:34 | quarague | Auf diesen Beitrag antworten » |
Für das nächste mal: es würde ziemlich helfen, wenn du die wesentlichen Definitionen noch mal dazu schreibst. Also wann ist ein Graph knotenregulär, was ist der Grad, und wie sind deine beiden Zusammenhangszahlen definiert ? ansonsten, wenn der Graph nur 3 Knoten hat, gibt es doch gar nicht so viele Möglichkeiten, wie der Graph aussehen kann, die kann man bestimmt alle aufzeichen und dann sehen, das die Zusammenhangszahlen mehr oder weniger trivialerweise gleich sind. |
||
| 29.12.2004, 16:38 | knoten | Auf diesen Beitrag antworten » |
Knotenregulär vom Grad 3 heißt, dass alle Knoten den Knotengrad 3 haben, jeder Knoten hat also Verbindung zu 3 anderen Knoten, der Graph kann aber natürlich mehr als 3 Knoten haben. Knotenzusammenhangszahl bzw. Kantenzusammenhangszahl bedeutet die minimale Anzahl der Knoten bzw. Kanten, die man weglassen muss, um den Graphen unzusammenhängend zu machen. |
||
| 02.01.2005, 16:39 | quarague | Auf diesen Beitrag antworten » |
Sei N die Knotenzushszahl, und A die Kantenzshzahl für einen Graphen. Dann zeige N<=A und A<= N für die erste kann man den Graph als zwei 'Wolken' darstellen, die durch A Brücken miteinander verbunden sind, wenn man die alle entfernt bleiben die beiden Wolken als 2 nicht mehr verbundene Teile übrig. Wenn man jetzt von jeder Brücke den Knoten an einem Ende entfernt zerfällt der Graph auch, man muss jetzt nur aufpassen, das ja mehrere Brücken vom gleichen Knoten ausgehen könnten, und das beide Menge danach nicht leer sind. Das gilt auch allgemein ohne Knotengrad 3. Die andere Ungleichung geht so ähnlich, wieder 2 'Wolken' mit N Knoten dazwischen. Jeder der Knoten ist mit einer Kante an die eine Wolke und mit 2 an der anderen verbunden, wenn man jetzt die einzelne Kante entfernt (bei jedem Knoten) zerfällt der Graph. Mit dieser Grundidee sollte es klappen, man muss nur noch mal genauer gucken wo etwas schiefgehen könnte. |
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
|
