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

Grafuri

• parcurgere în adâncime
• cele patru tipuri de muchii (forward, back, tree, cross)
• timpii de descoperire / părăsire a nodului, d[u] / f[u]
  • posibilități de intersectare pentru d[u], f[u], d[v], f[v] în funcție de ordinea parcurgerii lui u și v

Arbori parțiali minimi

• definiție
• algoritmi greedy
• tăieturi
  • tăieturi care respectă un set de muchii
• safe edges
• algoritmii lui Kruskal și Prim
  • analize de complexitate

Probleme

• problema celebrității O(n)
• găsirea unui ciclu O(n)
• test dacă un graf este bipartit O(n)
• adevărat sau fals? dacă u ⇝ v și d[u] < d[v], atunci v descendent al lui u - fals (u⇝v poate fi pe back edge)
• adevărat sau fals? dacă u ⇝ v, atunci d[v] ≤ f[u] - fals (idem)
• adevărat sau fals? dacă v are muchii care intră și muchii care ies, atunci v nu poate fi singur în arborele lui DFS - fals
• demonstrați că muchia minimă dintr-un graf este parte dintr-un MST
• actualizarea APM la adăugarea unei muchii, la adăugarea unui nod