Az alábbi ábrán például az x2 pont apja x1, a gyökér, ez minden más pontnak is elődje, az x2 pont fiai az x3 és x4 pontok, további utódai x5, x6 és x9. Ez utóbbinak nincs utódja, apja viszont az x6 pont.
FÁVAL KAPCSOLATOS DEFINÍCIÓK
Egy fában az x pont apjának nevezzük azt a pontot, amellyel az alacsonyabb szintű pontok közül össze van kötve. Ez a pont nyilván egyértelműen meg van határozva (egyetlen ilyen pont van és az az i–1-edik szinten van). Az x pont fiának nevezzük az összes olyan i+1-edik szintű pontot, amellyel a fában (!) össze van kötve. Vagyis amelyiknek ő az apja. Egy pont utódai fiai, fiainak fiai, stb., tehát minden olyan magasabb szintű pont, amellyel út köti össze; elődei az apja, az apjának az apja, stb., tehát azok a pontok, amelyek a pontból a gyökérhez vezető úton vannak (így maga a gyökér is). Két pont összehasonlítható pontja a fának, ha az egyik elődje a másiknak (és a másik utódja az egyiknek).
Az alábbi ábrán például az x2 pont apja x1, a gyökér, ez minden más pontnak is elődje, az x2 pont fiai az x3 és x4 pontok, további utódai x5, x6 és x9. Ez utóbbinak nincs utódja, apja viszont az x6 pont.
Adott egy összefüggő gráf, G. Szeretnénk olyan favázat keresni, amelyre igaz a következő: ha e=xy éle G-nek, akkor x és y a faváznak vagy azonos, vagy szomszédos szintjén van. Vagyis a gráf minden éle a favázon azonos vagy szomszédos szintek között fut. Milyen G gráfokra van ilyen faváz?
| TARTALOMJEGYZÉK |