Most je grana čijim uklanjanjem se graf raspada na dva dela, a artikulacioni čvor je čvor čijim uklanjanjem se to dešava. To su „slabe tačke“ mreže: jedan put, jedan ruter ili jedna raskrsnica od koje zavisi povezanost. Svi se nalaze jednim DFS obilaskom (Tarjanov algoritam).
1 --- 2 5 --- 6
\ / |
\ / |
3 --------- 4
Grane 1–2, 2–3, 1–3 čine ciklus, pa nijedna od njih nije most. Grane 3–4, 4–5 i 5–6 su mostovi. Artikulacioni čvorovi su 3, 4 i 5.
Tokom DFS-a svakom čvoru dodelimo tin[v] – redni broj ulaska. Zatim računamo low[v]: najmanji tin do koga se iz podstabla čvora v može stići, koristeći grane DFS stabla nadole i jednu „povratnu“ granu ka već posećenom čvoru.
v – u (u je dete u DFS stablu) je most ako je low[u] > tin[v]: iz podstabla čvora u nema drugog puta do v ili iznad njega.v (koji nije koren) je artikulacioni ako ima dete u sa low[u] >= tin[v].#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> graf;
vector<int> tin, low;
vector<bool> artikulacioni;
vector<pair<int, int>> mostovi;
int vreme = 0;
void dfs(int v, int roditelj) {
tin[v] = low[v] = ++vreme;
int dece = 0;
for (int u : graf[v]) {
if (u == roditelj) continue;
if (tin[u]) { // povratna grana ka posećenom čvoru
low[v] = min(low[v], tin[u]);
} else { // grana DFS stabla
dfs(u, v);
dece++;
low[v] = min(low[v], low[u]);
if (low[u] > tin[v]) mostovi.push_back({min(u, v), max(u, v)});
if (roditelj != 0 && low[u] >= tin[v]) artikulacioni[v] = true;
}
}
if (roditelj == 0 && dece >= 2) artikulacioni[v] = true; // koren
}
int main() {
int n, m;
cin >> n >> m;
graf.resize(n + 1);
tin.assign(n + 1, 0);
low.assign(n + 1, 0);
artikulacioni.assign(n + 1, false);
for (int i = 0; i < m; i++) {
int u, v;
cin >> u >> v;
graf[u].push_back(v);
graf[v].push_back(u);
}
for (int v = 1; v <= n; v++)
if (!tin[v]) dfs(v, 0); // graf može biti nepovezan
sort(mostovi.begin(), mostovi.end());
cout << "Mostovi:";
for (auto [a, b] : mostovi) cout << " " << a << "-" << b;
cout << endl << "Artikulacioni:";
for (int v = 1; v <= n; v++) if (artikulacioni[v]) cout << " " << v;
cout << endl;
return 0;
}
Složenost je O(n + m) – jedan obilazak. Ovaj program pretpostavlja da između dva čvora postoji najviše jedna grana; ako ih može biti više, umesto roditelja treba preskakati samo granu (po rednom broju) kojom smo došli.
Za svaki zadatak postoji primer, uputstvo i rešenje. Rešenja su provereno tačna na primerima iz teksta.
Mreža puteva između n sela je povezana. Put je kritičan ako bi njegovim zatvaranjem neka sela ostala odsečena. Ispiši broj kritičnih puteva.
6 6
1 2
2 3
1 3
3 4
4 5
5 633 3
1 2
2 3
3 10low[u] > tin[v], a za artikulacione čvorove low[u] >= tin[v].1. Šta je most u grafu?
2. Da li grana koja leži na ciklusu može biti most?
3. Kada je koren DFS stabla artikulacioni čvor?
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.
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)
Tarjan koristi DFS obilazak i za svaki čvor računa:
Ako važi:
low[to] > tin[v] → (v, to) je most
low[to] >= tin[v] → v je artikulacioni čvor (uz dodatne uslove)
#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);
}
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.
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)
1 ---- 2 ---- 3
| |
| |
4 ---- 5
Brzim pregledom možemo zaključiti:
Potvrda DFS-om dolazi iz uslova low[to] i tin[v].
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)