A gráfokban mit jelent pontosan a keresztél, előreél és a visszaél fogalom?
Előreél: A fában az ősből a leszármazottba vezető gráfél
Visszaél: A fában a leszármazottból az ősbe vezető gráfél
Keresztél: Minden más
Itt mit jelent az, hogy ős, meg leszármazott, ezt hogy kell érteni?
Illetve milyen fáról van szó, meg mi az, hogy a keresztél az minden más?
A gráf bejárása után ugye azok az élek amelyekkel a csúcsokat elértünk egy fát, "bejárási fát" alkotnak, erre a fára gondolnak?
válasza:Itt valamilyen speciális gráfról lehet szó, mert az "ős" és "leszármazott" fogalom csak abban lehet.
Először azt kéne tisztáznod, hogy milyen gráfokról van itt szó.
válasza:Igen, arra a fára gondolnak.
v leszármazottja u-nak, ha van a fában u-ból induló v-ben végződő út; őse, ha fordítva.
A minden más azt jelenti, hogy nem előreél és nem visszaél, kifejtve végpontjai nem leszármazottjai vagy ősei egymásnak.
válasza:#2 =>
Akkor itt irányított gráfokról lehet csak szó. A kérdezett fogalmakat #2 elmagyarázta.
Így néz ki a gráf amin bemutatták a fogalmakat:
A piros élek ugye azok amelyek mentén az eléretlen csúcsok elértté váltak, ezeket faéleknek hívják. És a piros élek által alkotott gráfot pedig a bejárási fának. A számok pedig azt jelzik, hogy melyik csúcsot hányadikként értük el, illetve fejeztük be. (piros: elérési szám, szürke: befejezési szám)
Azonban azt mondták, hogy az a->d él az előreél.
És ezt nem értem, hogy itt bejelöltem sárgával az a->d élt: [link]
De ez az él ez nem éle a bejárás fájának, mert ugye a bejárás fájának az élei azok a piros élek. Ennek a sárga élnek a segítségével pedig nem értünk el másik csúcsot.
A definíció meg azt mondja, hogy a "fában" olyan ... él.
Ez miért előreél, ha nem éle a bejárási fának?
válasza:Előreél, visszaél és keresztél a fán kívüli élek tudnak lenni. A fában szereplő éleket, ahogy írtad is, faélnek (tree-edge) nevezzük, csak a fenti felsorolásból ez a kategória valamiért lemaradt.
Ja, azért áll ott, hogy "a fában", mert az él végeinek a fában kell leszármazottnak és ősnek lennie; nem az élnek kell a benne lennie a fában.
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!