Ez miért igaz, hogy lehetne bizonyítani?
A BFS (szélességi bejárás) után gráfél nem ugorhat át faélt,azaz ha v1, v2,…vn egy elérési sorrend és i<j<k<=l
(i, j, k, l azok elért csúcsok, ilyen sorrendben, először i, aztán j, majd k és l)
ha vj, vk faél akkor a vi, vl nem lehet éle a gráfnak
Következménye:
BFS után nincs előreél, tehát irányítatlan BFS után az élek csak faélek vagy keresztélek lehetnek, hiszen irányítatlan esetben a visszaél ugyanaz mint az előreél
Ezt hogy lehetne bizonyítani, hogy gráfél nem ugorhat át faélt?
válasza:A BFS az egy lerövidebb utak fáját találja meg, tehát az r gyökércsúcsból bármely csúcsba a fán/faéleken keresztül a lehető legrövidebb út vezet bármely v csúcsba.
Ha lenne ilyen gráfél ami fáélt ugrana át, akkor lenne a grában egy rövidebb út, mint ami a fában van. És ez ellentmondás.
Ez így jó lehet, vagy máshogy kellene?
válasza:Hát ugye a legrövidebb út az a BFS fa éleiből épül fel, amiket faél alkot. Egy előreél pedig egy olyan gráfél, ami faéleken keresztül vezet.
Így milyen?
válasza:Ezt valahogy nem tudom megérteni.
A BFS-ről annyit tudok, hogy amikor kiválaszt egy csúcsot, azt addig nem engedi el, amíg a csúcsnak az összes szomszédját el nem érte. És mindig az elérési sorrendben azt a csúcsot választja, ami még nincs befejezve és legelöl van.
Tehát ha kiválasztunk egy csúcsot 1.-nek, akkor ebből elérek egy másik csúcsot, ekkor ez a másik csúcs lesz elérve 2.-nak. Ezután muszáj az 1.-nek elért csúcsot választanom, mert az a legkisebb csúcs ami még nincs befejezve. Ezt addig csinálom amíg már nem tudok belőle több csúcsot elérni, ekkor befejezem. Majd a második csúcsnak a 2.-ként elértet muszáj választanom.
De ebből nekem valamiért nem egyértelmű, hogy miért nincs olyan gráfél, ami faélt ugrik át. Azaz, hogy miért nincs előreél.
válasza:Rajzolj négy csúcsot - mindegy, hogy a lapon hogyan helyezkednek el egymáshoz képest -, nevezd el őket i,j,k,l-nek és kösd össze őket ebben a sorrendben! Tételezd fel, hogy i-t éppen elérte a bejárás és képzeld el a további lépéseket. Részletesen, ahogy az imént leírtad. Számozd meg a csúcsokat abban a sorrendben, ahogy a bejárás felfedezi őket; jelöld meg, melyik él kerül be a szélességi fába! Be is színezheted a befejezett csúcsokat, lerajzolhatod a sor tartalmát is, vagy bármit, ami segít. Aztán játszd el ugyanezt úgy is, hogy kezdetben i is össze van kötve l-lel.
(i,l) és a (j,k) él bekerülhet egyszerre a fába? Fogalmazd meg, miért nem!
Ebben nem vagyok teljesen biztos, de szerintem vagy félreértettem amit írtál, vagy valami nem stimmel, mert nekem bekerült minden él a fába:
A felső képen az 1. eset látszódik, amikor i és l nincs összekötve, csak i,j,k és l van sorrendben.
Zölddel jelöltem az elérési sorrendet, kék színű tollal a befejezésit és világos kékkel az éleket amin keresztül elértem a csúcsokat.
Ugye az i csúcsból elértem a szomszédját a j-t, i-ből nem tudtam mást elérni, így be kellett fejeznem. Ezután j-t kellett választanom, annak elértem a szomszédját, a k-t. Ezután megint j-t kellett választani, de abból nem tudtam elérni semmit, ezért befejeztem. Ezután jött a k, abból elértem az l-et. Majd k-ból nem lehetett elérni semmit, ezért befejeztem és az l-ből sem lehetett elérni semmit, így azt is befejeztem.
A 2. esetnél ugyanez volt, csak ott i-ből az l-et is el lehetett érni.
válasza:Ja bocs, igen, (i,l) és (k,l) nem lehet egyszerre a fában. A feladat kiírása is csak úgy stimmel, hogy k = l.
Arra a felismerésre akar a feladat rávezetni, hogy az (i,l) gráfél nem ugorhatja át a (k,l) faélt, hiszen ha (i,l) benne van a gráfban, akkor a fába is az kerül (k,l) helyett. Ezért nem lehetnek előreélek, ennyi az egész.
Ha csak a téves számozás miatt nem értetted, akkor minden rendben.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!