Mostovi i Artikulisani čvorovi (Tarjanov algoritam)
Mostovi i artikulisani čvorovi su ključni koncepti u teoriji grafova, posebno u problemima pouzdanosti mreža, analizi infrastrukture i otkrivanju "kritičnih tačaka" u sistemima.
Koriste se kada želimo da pronađemo elemente grafa čijim uklanjanjem dolazi do povećanja broja komponenti povezanosti.
Definicije
Most (bridge) je grana čijim uklanjanjem graf postaje nepovezan (raspada se na više komponenti).
Artikulacioni čvor (articulation point) je čvor čijim uklanjanjem graf postaje nepovezan.
Primer neusmerenog grafa:
(1) ---- (2) ---- (3)
|
(4)
- Mostovi: (1–2) i (1–4)
- Artikulacioni čvorovi: 1 i 2
Tarjanov algoritam — ideja
Tarjan koristi DFS obilazak i za svaki čvor računa:
- tin[v] — vreme ulaska u DFS
- low[v] — najranije tin[] koje može da se dosegne povratnom granom
Ako važi:
low[to] > tin[v] → (v, to) je most
low[to] >= tin[v] → v je artikulacioni čvor (uz dodatne uslove)
C++ kod — Mostovi
#include
using namespace std;
const int MAXN = 100005;
vector g[MAXN];
int tin[MAXN], low[MAXN];
bool visited[MAXN];
int timer = 0;
void dfs(int v, int p = -1){
visited[v] = true;
tin[v] = low[v] = ++timer;
for(int to : g[v]){
if(to == p) continue;
if(visited[to]){
low[v] = min(low[v], tin[to]);
} else {
dfs(to, v);
low[v] = min(low[v], low[to]);
if(low[to] > tin[v]){
cout << "Most: " << v << " - " << to << "\n";
}
}
}
}
int main(){
int n, m; cin >> n >> m;
for(int i = 0; i < m; i++){
int a, b; cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
for(int i = 1; i <= n; i++)
if(!visited[i]) dfs(i);
}
C++ kod — Artikulisani čvorovi
vector isCut(MAXN, false);
void dfs_ap(int v, int p = -1){
visited[v] = true;
tin[v] = low[v] = ++timer;
int children = 0;
for(int to : g[v]){
if(to == p) continue;
if(visited[to]){
low[v] = min(low[v], tin[to]);
} else {
dfs_ap(to, v);
low[v] = min(low[v], low[to]);
if(low[to] >= tin[v] && p != -1)
isCut[v] = true;
children++;
}
}
if(p == -1 && children > 1)
isCut[v] = true;
}
Napomena: poseban slučaj korena DFS-a kada ima više od 1 dete → artikulacioni je.
Python verzija — Mostovi (skraćeno)
from collections import defaultdict
g = defaultdict(list)
tin = {}
low = {}
timer = 0
visited = set()
def dfs(v, p = -1):
global timer
visited.add(v)
timer += 1
tin[v] = low[v] = timer
for to in g[v]:
if to == p: continue
if to in visited:
low[v] = min(low[v], tin[to])
else:
dfs(to, v)
low[v] = min(low[v], low[to])
if low[to] > tin[v]:
print("Most:", v, "-", to)
n, m = map(int, input().split())
for _ in range(m):
a, b = map(int, input().split())
g[a].append(b)
g[b].append(a)
for i in range(1, n+1):
if i not in visited:
dfs(i)
Praktični primer — ASCII graf
1 ---- 2 ---- 3
| |
| |
4 ---- 5
Brzim pregledom možemo zaključiti:
- Artikulacioni čvorovi: 2 i 1
- Mostovi: (1–2) i (2–3)
Potvrda DFS-om dolazi iz uslova low[to] i tin[v].
Zadaci za vežbu
- Naći sve mostove u nasumično generisanom grafu.
- Napisati program koji računa broj komponenti nakon uklanjanja svakog artikulacionog čvora.
- Primeniti Tarjana na mrežni prikaz labirinta.
- Odrediti da li graf ima tačno jedan kritičan čvor.
Zaključak
Tarjanovi algoritmi su osnova za napredno gradivo u grafovima i direktno povezuju DFS sa strukturom grafa. Ovi koncepti se redovno pojavljuju na takmičenjima, posebno u kombinaciji sa dinamičkim programiranjem i teorijom mreža.
□ Preporučeno sledeće: SCC — Kosaraju i Tarjan (Komponente jake povezanosti)