## Ce sunt wormholes?
Un wormhole (în română: „gaură de vierme”) este un concept teoretic din fizică ce descrie un tunel prin spațiu-timp care ar putea conecta două puncte foarte îndepărtate din Univers.
Ideea apare din ecuațiile teoriei relativității generale formulate de Albert Einstein. În 1935, el și Nathan Rosen au descris o structură numită „pod Einstein-Rosen”, considerată primul model teoretic de wormhole.
—-
## 🌀 Cum ar arăta un wormhole?




Un wormhole este adesea reprezentat ca:
Dacă Universul ar fi o foaie de hârtie, un wormhole ar fi ca și cum ai îndoi foaia și ai face o gaură direct între două puncte.
—-
## 🔬 Există wormholes în realitate?
Până în prezent:
Unii cercetători cred că la nivel cuantic ar putea exista micro-wormholes extrem de mici, dar nu există dovezi experimentale clare.
—-
## 🚀 Wormholes în filme și cultură
Conceptul a devenit popular în literatura și filmele SF, unde este folosit pentru călătorii interstelare rapide.
Un exemplu celebru este filmul Interstellar, unde un wormhole permite explorarea altor galaxii.
—-
## 🧠 Sunt posibile călătoriile în timp?
Teoretic, unele modele sugerează că wormholes ar putea permite și deplasarea în timp, nu doar în spațiu. Totuși:
Deocamdată, rămân doar o ipoteză fascinantă.
—-
## ✨ Concluzie
Wormholes reprezintă una dintre cele mai interesante idei din fizica teoretică. Deși nu știm dacă există cu adevărat, ele ne ajută să explorăm limitele cunoașterii despre Univers, spațiu și timp.
Poate într-o zi, ceea ce azi pare science-fiction va deveni realitate. 🌠
Această problemă combină trei concepte fundamentale din teoria grafurilor: arbori de acoperire minimi, drumuri minime și componente conexe. Este o problemă complexă care testează înțelegerea profundă a algoritmilor pe grafuri și capacitatea de a combina soluții diferite pentru a rezolva cerințe multiple.
Considerăm o rețea de transport formată din N orașe conectate prin M drumuri bidirecționale. Fiecare drum are două atribute importante: o lungime (relevantă pentru distanțe) și un cost de întreținere (relevant pentru construcția rețelei).
Guvernul dorește să optimizeze rețeaua de transport urmând trei obiective distincte:
Primul obiectiv este să construim un arbore de acoperire (MST – Minimum Spanning Tree) cu cost total minim, dar cu o constrângere suplimentară: fiecare oraș poate avea cel mult K drumuri directe în rețeaua finală.
Această constrângere transformă problema clasică MST într-o variantă mai complexă care necesită algoritmi modificați.
Al doilea obiectiv este să calculăm distanța minimă între două orașe date folosind lungimile drumurilor. Aceasta este o aplicație clasică a algoritmului Dijkstra pe grafuri ponderate.
Al treilea obiectiv analizează robustețea rețelei prin eliminarea tuturor drumurilor cu cost de întreținere mai mare decât o valoare X. Trebuie să determinăm câte componente conexe rămân în rețeaua rezultată.
Pentru prima cerință, folosim o variantă modificată a algoritmului Kruskal:
1. Sortăm toate muchiile după cost crescător
2. Iterăm prin muchiile sortate
3. Pentru fiecare muchie (u, v):
- Verificăm dacă u și v sunt în componente diferite
- Verificăm dacă grad[u] < K și grad[v] < K
- Dacă ambele condiții sunt true:
* Adăugăm muchia în MST
* Unim componentele (DSU)
* Incrementăm gradele
Complexitate: O(M log M) pentru sortare + O(M α(N)) pentru DSU
Pentru distanțe minime, implementăm Dijkstra standard:
1. Inițializăm distanțe cu infinit 2. Setăm dist[sursa] = 0 3. Folosim un min-heap (nod, distanță) 4. Extragem nodul cu distanță minimă 5. Relaxăm muchiile adiacente 6. Repetăm până ajungem la destinație
Complexitate: O(M log N) folosind priority queue
Pentru componente conexe, folosim DSU cu optimizări:
class DSU:
def __init__(self, n):
self.parent = [i for i in range(n)]
self.rank = [0] * n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x])
return self.parent[x]
def unite(self, a, b):
a, b = self.find(a), self.find(b)
if a b: return False
if self.rank[a] < self.rank[b]:
a, b = b, a
self.parent[b] = a
if self.rank[a] self.rank[b]:
self.rank[a] += 1
return True
Complexitate: O(M α(N)) unde α este funcția inversă Ackermann
struct Edge {
int to, cost, length;
bool operator<(const Edge& other) const {
return cost > other.cost; // pentru min-heap
}
};
class DSU {
private:
vector parent, rank;
public:
DSU { /* inițializare */ }
int find(int x) { /* path compression */ }
bool unite(int a, int b) { /* union by rank */ }
};
Funcția main() orchestrează cele trei etape:
int main() {
// Citire date
// 1. MST cu constrângere de grad
// 2. Dijkstra pentru distanțe
// 3. DSU pentru componente conexe
// Afișare rezultate
}
Python oferă o sintaxă mai concisă și biblioteci integrate pentru structuri de date complexe:
import heapq # pentru priority queue from collections import defaultdict
MST modificat: O(M log M) – dominat de sortare
Dijkstra: O(M log N) – eficient pentru grafuri rare
Componente conexe: O(M α(N)) – aproape liniar
Total: O(M log M + M log N) – acceptabil pentru constrângerile date
Graf: O(N + M) – listă de adiacență
DSU: O(N) – vectori parent și rank
Muchii: O(M) – pentru sortare și procesare
Total: O(N + M) – optim pentru N, M ≤ 10000
Input: 6 9 3 2 50 1 2 10 20 1 3 15 30 2 4 25 60 3 5 30 45 4 6 40 70 5 6 45 65 1 6
Output:
185 # Cost MST cu grad ≤ 3
75 # Distanța minimă 1→6
2 # Componente conexe după eliminare cost > 50
MST: Muchiile (1,2,20), (1,3,30), (2,4,60), (3,5,45), (4,6,70) = 225
Dijkstra: Drumul 1→2→4→6 = 10+25+40 = 75
Componente: Eliminăm muchiile cu cost > 50, rămân 2 componente
Algoritmi alternativi: Prim modificat pentru MST cu constrângeri
Optimizări: Early termination în Dijkstra când ajungem la destinație
Paralelizare: Procesare paralelă a componentelor conexe
Rețele de comunicare: Design de rețele cu constrângeri de grad
Transport urban: Planificare rute optime
Infrastructură: Analiza robusteței rețelelor critice
Această problemă demonstrează importanța combinării mai multor algoritmi de grafuri pentru a rezolva probleme complexe din lumea reală. Constrângerile suplimentare fac problema mai interesantă și mai apropiată de scenariile practice unde resursele sunt limitate.
Soluția prezentată este eficientă și scalabilă, putând gestiona rețele de dimensiuni moderate cu performanțe bune atât în C++ cât și în Python.