[D&A] BFS oefeningen

Forum voor de keuzevakken over alle jaren heen.

Moderator: Praesidium

mrdckx
Posts: 7

[D&A] BFS oefeningen

Post#1 » Wed May 26, 2010 2:14 pm

Hey ik had nog enkele vragen over de BFS oefeningen op pagina 6.

Bij de tweede vraag zou de oplossing zijn:
BFS uitvoeren en als er een edge (u,v) gevonden wordt waarvoor u en v grijs en d(u) en d(v) beide even/oneven dan niet bipartite. Ik begrijp deze oplossing niet. Zie deze tekening: (getallen zijn moment van discovery)
Image
Op die moment gaan we de buren van de node met d(u)=3 onderzoeken. We vinden dan een node met d=5 (want deze was al ontdekt door een andere node en ziet dus grijs) Volgens de oplossing is deze graph dan niet bipartite ?

Bij de derde vraag zou de oplossing zijn:
Lengte van path van alle vertices naar alle vertices bepalen door BFS en daar het maximum uit halen. Bij de volgende tekening zou de oplossing 3 geven, terwijl de diameter volgens mij 4 is.
Image

Wat doe ik hier verkeerd?

Alvast bedankt voor de hulp!

JR
Posts: 23

Post#2 » Thu May 27, 2010 5:43 pm

1.) Volgens mij is uw notie van d(u) fout. Ik denk dat die waarde aangeeft op welke afstand van uw source iedere vertex zicht bevindt, en bijgevolg zijn uw d's niet (1,2,3,4,5) maar (0,1,1,2,2).

2.) Hier moet ge de "maximale kortste afstand" bepalen, dus het maximum van alle kortste paden. De diameter is dan inderdaad drie, want het pad met vier edges is een "omweg".

Return to “Keuzevakken”

Who is online

Users browsing this forum: No registered users and 6 guests

cron