Grafuri neorientate. Probleme propuse

1. Fie un graf neorientat memorat prin matricea de adiacente si o succesiune de k noduri. Sa se determine daca succesiunea citita este un lant din graf
2. Din fisierele mat1.in si mat2.in se citesc doua matrici patratice associate grafurilor g1 si g2. Sa se deremine daca g2 este graf partial pentru g1
3. Fie o harta cu n orase. Cele n orase se citesc din fisier. Intre cele n orase exista m drumuri. Se cunosc distantele celor n drumuri.
1. Sa se determine daca orasul x si orasul y sunt vecine
2. Sa se afiseze lungimile tuturor localitatilor intre care exista drum direct
3. Sa se determine lungimea minima a drumului dintre doua localitati citite de la tastatura
4. La o receptie sunt invitate n personae. Se cunosc numele celor n persoane .  Intre anumite persoane exista relatii de colaborare. Sa se determine daca se pot dispune cele n personae la o masa rotunda astfel incat intre oricare doua personae alaturate sa existe relatii. Se citesc : numele persoanelor si cele m relatiile sub forma de perechi de nume
5. Un eschimos locuieste la iglul cu numarul z. El are o harta pe care sunt marcate iglu-urile din zona (numerotate de la 1 la n) si distantele dintre acestea. Stiind ca din cauza frigului eschimosul nu poate sa parcurga o distanta mai mare de 20 km fara oprire, afisati o varianta de a ajunge  la prietenul lui care locuieste la iglul cu numarul w, eventual cea mai scurta varianta care indeplineste cerinta data. Cati kilometri  a parcurs eschimosul?
6. Un graf neorientat este bipartit daca exista o partitie a multimii nodurilor in doua multimi A si B astfel incat oricare doua varfuri din aceeasi multime sa nu fie adiacente. Sa se scrie un program care verifica daca un graf este bipartit si in caz afirmativ sa se tipareasca multimile A si B
7. Problema colorarii unei harti. Se citesc 4 culori (siruri de caractere) si denumirile a n tari (siruri de caractere) . Sa se coloreze harta astfel incat sa nu existe doua tari alaturate avand aceeasi culoare.  Se va afisa o solutie : tara-culoare, tare-culoare etc.
8. Sa se coloreze un graf astfel incat oricare doua muchii incidente cu acelasi nod sa fie colorate diferit. Care este numarul minim de culori necesar.
9. O pestera are n incaperi, fiecare situata la o adancime h. Configuratia pesterii este data de cele m culoare de acces intre camerele pesterii (culoarele sunt date ca extremitati). In incaperea s exista un izvor de apa sulfuroasa. Se dau n, m, cele m culoare (ca perechi x-y), s si adancimile h ale camerelor. Determinati incaperile inundate si culoarele umezite.
10. Fie un graf neorientat. Sa se determine daca graful contine cicluri.