fejléc
Gyakori kérdések Belépés Új kérdés Véletlen kérdés
Keresés
Kezdőoldal » Közoktatás, tanfolyamok » Házifeladat kérdések » Ez miért igaz, hogy lehetne...

Ez miért igaz, hogy lehetne bizonyítani?

Figyelt kérdés

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?



#bizonyítás #bejárás #gráf
2023. febr. 20. 10:54
❮ 1 2
 11/14 A kérdező kommentje:

Lehet megértettem.

Nem lehet olyan gráfélem ami i-t és l-et összekötné, mivel ha van ilyen él, akkor azt a bejárás során, amikor az i csúcsot néztem, akkor ezt az élt bevettük volna a gráfélek közé. Mert amikor az i csúcsnál vagyunk akkor minden belőle kilépő élt végignézünk ami olyan csúcsba vezet ami még eléretlen, és ekkor az adott eléretlen csúcsot azt az adott él mentén elérjük.

Tehát lenne i-ből l-be ezető él a gráfban, akkor az biztos faél lenne.


Így helyes?

2023. febr. 25. 15:11
 12/14 A kérdező kommentje:
"amikor az i csúcsot néztem, akkor ezt az élt bevettük volna a faélek közé." faélt akartam írni, nem gráfélt.
2023. febr. 25. 15:13
 13/14 anonim ***** válasza:
Pontosan, így már jó.
2023. febr. 25. 18:20
Hasznos számodra ez a válasz?
 14/14 A kérdező kommentje:
Rendben, köszönöm szépen a sok segítséget, ment a zöld.
2023. febr. 25. 18:24
❮ 1 2

Kapcsolódó kérdések:

Közoktatás, tanfolyamok főkategória kérdései »
Közoktatás, tanfolyamok - Házifeladat kérdések kategória kérdései »



Minden jog fenntartva © 2025, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu

A weboldalon megjelenő anyagok nem minősülnek szerkesztői tartalomnak, előzetes ellenőrzésen nem esnek át, az üzemeltető véleményét nem tükrözik.
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!