Induktion zur Breitensuche Benötige Hilfe

[Paniomania]

Hey, habe momentan an der UNI das Thema "Breiten- & Tiefensuche im Graphen" & habe bei einer Teilaufgabe Schwierigkeiten. Hoffe jemand von euch kann mir bei der Beweisführung helfen.

Die Aufgabe Lautet:

"Sei G = (V,E) ein ungerichteter Graph. Zeige, dass die Breitensuche aus einem Startknoten q Element von V kürzeste Wege von q zu den anderen Knoten liefert. (Zeige dabei durch Induktion, dass in der Warteschlange zu jedem Zeitpunkt der Abstand zu q monoton wächst und sich zwischen aufeinanderfolgenden knoten um höchstens 1 unterscheidet. Schließe daraus, dass der korrekte Abstand berechnet wird.)"

Ich habs echt nicht so mit Beweisführungen und stehe mehr- oder weniger ratlos da. Freue mich sehr über Hilfe.

Gruß
Panio

 

[voodoo44]

Weißt du denn, wie du einen Beweis durch Induktion zu führen hast?

 

[Paniomania]

WIe es im grunde geht weiß ich, aber in dem Beispiel weiß ich es nicht.