[D&A] BFS oefeningen

[mrdckx]

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)

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.


Wat doe ik hier verkeerd?

Alvast bedankt voor de hulp!

[JR]

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".