Nemam puno vremena ali cu ti pokusati odgovoriti na pitanje broj 1.

Svaki BIpartitni graf je 2-obojiv. Evo uzmimo npr ili uopsteno . On izgleda ovako
(1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6) = P gdje su i cvorovi a notacija veza izmedju tacaka a i b.
Algoritam je jednostavan.
Provjeravas sve parove. Ako za sve parove iz P postoji jedan par (a, b) gde je i onda graf nije 2-obojiv. Zasto? Evo zasto. Recimo da je u P jedan par (1,2) onda imamo sljedece stanje

(1, 2) (1, 4), (1, 5), (1, 6), (2, 4), (2, 5), (2, 6), (3, 4), (3, 5), (3, 6) = P

Za prvi par (1, 2) bojimo 1 sa crvenom, 2 sa plavom.
(1, 4) 1. ostaje crvena, 4 bojimo sa plavom
...
(2, 4) postoji kolizija jer 2 je obojeno sa plavom i 4 obojeno sa plavom, moramo dodati jos jednu farbu sto u ovom slucaju graf nije 2-bojiv.

Nadam se da si skontao u cemu je problem.
To sam samo naveo za bipartitne grafove, a za ostale nije isto problem skonati mada sad nemam vremena nesto posebno

Uzdravlje
Amel

Generalno postoji nekoliko algoritama koji se najcesce koriste u prolasku kroz grafove i najprostiji su:
Dijkstra, Breadth-first, Depth-first
ostale stvari ces morati uklopis u implementacije tih algoritama
Knkretno za tvoje probleme pogledaj linkove
http://www.cs.auckland.ac.nz/~ute/220ft/graphalg/graphalg.html
http://en.wikipedia.org/wiki/Category:Graph_algorithms