Jeder Digraph hat einen Semi-Kernel |
| 28.12.2017, 22:05 | Kruemelix | Auf diesen Beitrag antworten » |
| Jeder Digraph hat einen Semi-Kernel ich sitze gerade über folgendem Beweis (link.springer.com/content/pdf/10.1007%2FBFb0066192.pdf) und zerbreche mir über einen Punkt den Kopf: Was meint der Autor mit "By the induction hypothesis there is a set S' which works for G' "? Vielen Dank schon im Voraus, Thomas |
||
| 29.12.2017, 08:08 | Elvis | Auf diesen Beitrag antworten » |
Der Autor meint: "Nach Induktionsvoraussetzung gibt es eine Menge S', die man auf G' anwenden kann." Wenn jetzt einer von uns beiden das Buch lesen würde, könnte er diesen Satz vielleicht verstehen. |
||
| 29.12.2017, 08:58 | Kruemelix | Auf diesen Beitrag antworten » |
danke für die Antwort, aber den Schlater im Kopf hat es immer noch nicht umgelegt. Das Ganze ist nicht einmal ein Buch sondern lediglich ein extrem kurzes Paper, müsste also selbsterklärend sein. Insofern stört es mich umso mehr, dass ich nicht dahinterkomme. Die Behauptung ist im Grunde nicht schwer zu verstehen, es wird lediglich eine Knotenmenge S in einem gerichteten Graphen gesucht, sodass alle Knoten in S mindestens einen Abstand 2 zueinander haben (mindestens ein Knoten dazwischen), auf der anderen Seite alle übrigen Knoten einen Abstand von höchstens 2 zu den Knoten in S. Ich versuuche den Beweis mal aufzudröseln: - By induction on the number of vertices of G. Let w be a vertex of G: Ok, da fängt man halt mit einem Knoten an und nimmt immer mehr dazu - let G' be the subgraph of G induced by : Jetzt wird es schon komisch, ich betrachte also nicht w selber, sondern alle Knoten, welche von w mindestens einen Abstand von 2 haben und den dadurch induzierten Subgraphen G'. Schon mal komisch, aber ok. - By the induction hypothesis, there is a set S' which works for G': Und jetzt setzt es aus - ich sehe weder eine Induktionsannahme noch instinktiv wieso es klappen könnte. Wenn ich mit einem Knoten w starte, kann G' fast so groß wie der ursprüngliche Graph G sein. Das ist für mich keine Induktion... Vielleicht kommt ein anderer dahinter.... |
||
| 29.12.2017, 09:50 | Elvis | Auf diesen Beitrag antworten » |
G' ist kleiner als G, weil w nicht in G' liegt und alle u aus G mit d(u,w)=1 auch nicht. Das gibt eine prima Induktion, bei der vorausgesetzt wird, dass die Behauptung für alle Graphen erfüllt ist, die kleiner sind als G. G' ist kleiner, also existiert S'. Eventuell ist dir nicht bewußt, dass man das Prinzip der vollständigen Induktion auf unterschiedliche Weise definieren kann. Die 2. Version ist in der Graphentheorie besonders beliebt. Man muss nicht so genau zählen, es genügt, wenn sich eine Eigenschaft von kleineren Graphen auf größere Graphen vererbt. |
||
| 29.12.2017, 16:18 | Kruemelix | Auf diesen Beitrag antworten » |
Hallo, danke, die zweite Schreibweise war mir in der Tat nicht bekannt. Ziemlich ärgerlich, dass uns diese nie im Studium beigebracht wurde. Nur damit ich es richtig verstanden habe: Für den Induktionsanfang sind demnach sowohl G, G', S und S' leer? Nochmals danke für die prompte Antwort! |
||
| 29.12.2017, 17:41 | Elvis | Auf diesen Beitrag antworten » |
"Induktion mit beliebigem Anfang" und "Induktion mit mehreren Vorgängern" kennt auch Wikipedia : https://de.wikipedia.org/wiki/Vollst%C3%A4ndige_Induktion Man lernt das spätestens beim Studium der "elementaren Zahlentheorie". Edmund Landau hat ganz sicher genug dazu gesagt. Über den Induktionsanfang weiß ich nichts. Du hast bisher nur vom Induktionsschritt gesprochen. Was sagt das Paper dazu ? |
||
| Anzeige | ||
|
|
||
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
|
| Die Neuesten » |
