Kapitel 2Aufbau25 Min.
Extremalwidersprüche
Extremalwiderspruch und kleinste Gegenbeispiele · Abschnitt 5 von 64
Gelöstes Beispiel
Eine Verbesserung widerspricht der Wahl
Idee: Eine Sehne im kürzesten Zyklus würde einen noch kürzeren Zyklus erzeugen – also kann es keine Sehne geben.
Gelöstes Beispiel
Das kleinste Gegenbeispiel kann nicht kleiner werden
Eine gültige Reduktion auf einen kleineren falschen Fall widerspricht der Minimalität – so fällt das kleinste Gegenbeispiel.
Gelöstes Beispiel
Extrem entfernen und zurückbauen
Idee: Ein Blatt, Endpunkt oder kleinstes Element erzeugt oft eine kleinere Instanz mit denselben Voraussetzungen – dann baust du die Lösung zurück.