Din când în când, pe CodeForces există întrebări despre centru, raza și diametrul graficului (ar putea fi doar google despre copac, deși a existat mai multe). În acest subiect sunt date definiții pentru aceste concepte și sunt descrise și algoritmi pentru găsirea lor.
Sarcina. Având în vedere un grafic nedirecționat G = (V. E). unde V este setul de vârfuri și E este setul de muchii. Este necesar să se găsească raza, diametrul și centrul.
Definiți di. j ca cea mai scurtă distanță dintre o pereche de vârfuri. Apoi, diametrul graficului este definit ca fiind maximul posibil dintre toate distantele cele mai scurte dintre o pereche de noduri:
De asemenea, introducem noțiunea de excentricitate a unui vârf ca distanța maximă de la vârf la un altul:
Cunoscând excentricitatea tuturor vârfurilor, putem determina și raza graficului, deoarece minimul dintre ele:
Puteți observa imediat că diametrul graficului este excentricitatea maximă din grafic, și anume:
Centrul graficului este definit ca toți vârfurile cu o excentricitate egală cu raza graficului:
Definițiile sunt date și un algoritm trivial ajunge să găsească centrul, raza și diametrul pentru un grafic arbitrar folosind algoritmul Floyd-Warshell:
Acum vom schimba puțin afirmația problemei: să presupunem că graficul G este un copac. Pentru un arbore nu este dificil să se demonstreze următorul fapt: numărul de vârfuri din centrul unui copac este egal cu unul sau două.
Pe CodeForces o dată am auzit următorul algoritm pentru a găsi centrul arborelui: cu ajutorul BFS, și de la fiecare nod (notat cu v 1), pentru a găsi cel mai îndepărtat din partea de sus a v 1 (notată cu V 2), apoi executați BFS din v 2. alege orice vârf cel mai îndepărtat de v 2 (let be v 3). Vertex (s) la jumătatea distanței dintre v 2 și v 3 formează un centru al graficului, distanța dintre ele - diametrul. Raza este jumătate din diametrul rotunjit: (diam (G) + 1) / 2. Punerea în aplicare a acestui algoritm nu va fi dat aici, deoarece mi se părea destul de greoaie. În schimb, vă voi da un alt algoritm care părea mai ușor de implementat.
Teoremă: Fie L setul tuturor frunzelor din grafic. Dacă | V | ≤ 2. atunci L este centrul graficului, altfel puteți șterge toate frunzele și centrul graficului nu se va schimba:
Această teoremă ne conduce la următorul algoritm: vom elimina frunzele arborelui, strat cu strat, până când vor rămâne ≤ 2 vârfuri. Aceste noduri vor fi centrul graficului. Implementarea acestui algoritm este foarte asemănătoare cu căutarea în lățime:
Nu este dificil să se demonstreze că după executarea acestui algoritm centrul arborelui va fi în setul c. și rad (G) = (diam (G) + 1) / 2.
Puzzle-uri pe tema:
Vă mulțumesc pentru atenție, despre greșeli, vă rugăm să scrieți în PM.
diametru. raza. copac. Count. centrul de copaci
Trimiteți-le prietenilor: