Note de curs, clasele 9-10, 2 noiembrie 2012

Grafuri

• definiții: noduri, muchii, orientat, neorientat, adiacență, grad (in/out/total), cale, accesibil, ciclu, simplu, conex, componente conexe
• grafuri speciale: complet, bipartit, arbore / pădure, dag
• reprezentări:
  • matrice de adiacență (testare vecinătate O(1) / spațiu O(n²)
  • liste de adiacență (spațiu O(m))
  • posibil și vector de adiacență, când se poate prealoca
  • exemplu: calculul gradelor la intrare / ieșire prin ambele metode.
• parcurgere în lățime:
  • culori (conceptuale): alb (nedescoperit), gri (în coadă), negru (parcurs complet)
  • algoritm cu coadă
  • propoziție: calculează distanțele minime de la s la toate celelalte
  • demonstrație

Probleme

• implementare BFS
• suma gradelor este 2 m
• într-un graf neorientat cu >= 2 noduri există două noduri cu același grad
• într-un graf cu 6 noduri există un subgraf cu trei noduri sau un subgraf fără muchii
• problema celebrității O(n)