A II/12. feladat megoldása:

Bármely ponthoz tartozó bármely szélességi faváz megfelel. Ez következik a szélességi faváz definíciójából. Tegyük fel ugyanis, hogy az xy él alacsonyabb szintű végpontja – legyen ez x az i-edik szinten van és tegyük fel, hogy y magasabb szintre került. De ekkor biztosan felkerült az i+1-edik szintre, hiszen erre a szintre az összes olyan pontot feltesszük, amely (legalább) egy i-edik szintű ponttal össze van kötve.

Megjegyzés a szélességi faváz keresésének számítógépes megvalósításáról

A szélességi faváz a pontok távolságával kapcsolatban merült fel. Most még pár oldalról megvizsgáljuk a gráfban definiált távolságfogalmat.

TARTALOMJEGYZÉK