Lista de probleme 38

Se dă un număr natural n. Construiți toate grafurile neorientate cu n vârfuri.

Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n, precum si o mulțime A de vârfuri ale grafului. Considerăm mulțimea B formată din vărfurile grafului care nu aparțin lui A. Să se verifice dacă graful este bipartit peste partiția formată din mulțimile A și B.

Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n. Să se verifice dacă graful este bipartit.

Se dă lista muchiilor unui graf neorientat cu n vârfuri, etichetate de la 1 la n. Să se verifice dacă graful este bipartit.

Se dă un graf neorientat cu n vârfuri și un număr natural q. Să se determine toate lanțurile elementare formate din cel puțin o muchie, cu extremitatea finală în vârful q.

Pentru a face LevelUP, Capra din Ohio mai are nevoie de 100XP, de aceea s-a decis sa meargă la școală ca să obține cele 100XP. La ora de informatică, în schimbul a 100XP, are de rezolvat următoarea problemă: Se dă un graf neorientat cu n vârfuri și m muchii. Să se afișeze în ordine lexicografică toate lanțurile hamiltoniene ale grafului dat. Cum habar nu are despre grafuri și lanțuri, vă roagă să o ajutați. Recompensa va fi un video special de mulțumire.

Se consideră două mulţimi nevide A şi B, cu proprietatea că formează o partiție a mulțimii {1,2,...,n}. Să se construiască un graf bipartit complet cu n vârfuri, bipartit peste partiţia formată din mulțimile A și B.

Se dă lista muchiilor unui graf neorientat cu n vârfuri și o succesiune de k vârfuri. Să se verifice dacă vârfurile din succesiune formează un lanț.

Se dă lista muchiilor unui graf neorientat cu n vârfuri și două vârfuri p q. Să se determine toate lanțurile elementare cu extremitățile p și q.

Se dă lista muchiilor unui graf neorientat cu n vârfuri și un vârf q. Să se determine cel mai lung lanț elementar cu extremitatea finală în q.