Calcularea distanțelor și a defini rute într-un grafic este una dintre problemele cele mai evidente și practice care apar în teoria graficelor. Să ne introducă niște definiții necesare.
Excentricitatea vertex - la distanța maximă de la vârful său. Pentru un grafic, care nu determină greutatea marginilor sale, distanța este definită ca numărul de muchii.
Contorizarea raza - excentricitatea minimă a vertex, iar diametrul graficului - excentricitatea maximă a nodului.
Centrul graficului formează nodurile a căror excentricitate este egală cu raza. Count Centrul poate consta dintr-una sau mai multe sau toate nodurile.
noduri periferice au un diametru egal excentricitate.
Lungimea lanțului de simplu egal cu diametrul graficului, numit diametrală.
Teorema 12.1.V grafic conectat diametru este mai mare decât gradul de matricea sa de adiacență.
Teorema 12.2. (Jordan) Fiecare copac are un centru format din unul sau două vârfuri adiacente.
Diametrul arborelui Teorema 12.3.Esli este chiar, atunci copacul are un singur centru, și toate căile diametrale trec prin ea, în cazul în care diametrul este impar, atunci centrul a două diametrale și toate lanțurile au un avantaj conectarea acestora.
Valoarea practică Evidentă a Centrului Count. Dacă, de exemplu, este un grafic cu noduri rutiere, orașe, centrul matematic este recomandabil să se plaseze centrul administrativ, depozite, etc. Aceeași abordare poate fi aplicată la un grafic ponderat, în cazul în care distanța - este greutatea a coastelor. Ca o greutate puteți lua euclidian la distanță, timp, sau costul transportului între puncte.
Exemplul 12.5. Găsiți raza, diametrul și centrul graficului prezentat în Fig. 12.1.
Decizie. Această problemă este convenabil de a folosi elementul de matrice distanța S. Această matrice simetrică pătrat este egală cu distanța dintre vârfuri i și j vertex. Pentru graficul prezentat în Fig. 12.1 matrice distanță are următoarea formă:
Se calculează excentricitatea fiecărui nod. Această valoare poate fi definită ca coloana maximă a elementului de matrice a distanțelor corespunzătoare (sau rânduri - din matricea S simetrică). obține
Raza graficului r - vârfuri minime ale excentricității. În acest caz, r = 2. Excentricitatea are noduri № 2, № № 4 și 5. Aceste vârfuri formează centrul graficului. Diametrul graficului D - excentricitatea maximă a nodului. În acest caz, d = 3. Această excentricitate are noduri № № 1 și 3, acest grafic periferie. În coloana investigate vârfurile au fost fie centrale sau periferice. Coloanele de ordin superior, există alte vârfuri.
Excentricitatea vârfurile graficului mici pentru a calcula cu ușurință calculul direct al figurii. Cu toate acestea, nu li se acordă întotdeauna modelul său grafic. În plus, graficul poate fi mare. Prin urmare, aveți nevoie de un alt mod de a rezolva problema anterioară. Următoarea teoremă.
Teorema 12.4.Pust - matricea de adiacență a unui grafic G fără bucle și unde. Apoi, egal cu numărul de rute de lungime k de la vârf la vârf.
Solutia problemelor de teoria grafelor prin intermediul diferitelor transformări ale matricei adiacență se numește metoda algebrică.
Exemplul 12.6. Găsiți matricea distanță a graficului prezentat în Fig. 12.1, metoda algebrică.
Decizie. Matricea de adiacență a graficului este:
Vom umple matricea la distanță, având în vedere gradul de matricea de adiacenta. matrice Unitățile adiacență prezintă o pereche de vârfuri separate de o distanță egală cu unu (adică, acestea sunt conectate printr-o muchie).
Elementele diagonale ale matricei distanțelor - zero. Matricea de adiacență se multiplica:
Conform teoremei între nodurile 2 și 3, 1 și 4, etc. există o serie de căi de lungime 2 (matrice, deoarece gradul egal cu doi). Numărul de rute nu sunt utilizate, important este faptul unei rute și lungimea acestuia, și indică faptul că într-un element de matrice nenulă măsură, nu coincide cu elementul marcat la lungimea traseului calculat. 2 este aplicată elementelor goale ale matricei distanță și a obține următoarea apropiere:
Rămâne distanța necunoscută între nodurile 1 și 3. Să se multiplica matricea de adiacență pe sine, atâta timp cât matricea nu este un element non-zero, apare. Apoi, elementul corespunzător al matricei de distanțe egale cu gradul de matrice adiacență :. În etapa următoare vom obține
Prin urmare. și în cele din urmă
Matricea rezultată coincide cu matricea S distanța (12.2), găsit prin calcul direct pe imagine.
Toate subiectele acestei secțiuni:
definiții de bază
Count - o combinație de două seturi: noduri
lanț Euler
neografe Route în care toate marginile sunt diferite, numit un lanț. Circuit în grafic se numește Euler în cazul în care acesta conține toate muchiile și vârfuri ale graficului.
grafic cu linii
Luați în considerare două grafice G și L (G). Un grafic G are o formă arbitrară, iar nodurile L (G) situate pe marginile graficului G. In acest caz, graficul L (G) se numește
Grafic colorat, polinomul cromatic
Să presupunem că avem o sarcină: pentru a picta harta lumii, astfel încât fiecare țară a avut propria sa culoare. Pentru că în lume există mai multe sute de state, în mod natural, consumato
Contele polinomul Locul
Grafic Locul este determinat ca. unde n - numărul de noduri, k - numărul componentelor conectate ale graficului. la
definiții de bază
O margine într-un grafic G poate fi orientat și să aibă un început și un sfârșit. O astfel de muchie se numește
Trasee în digraph
Sarcini legate de rutele din digraph, sunt de o mare importanță practică, care dă un impuls pentru dezvoltarea și îmbunătățirea metodelor de rezolvare a acestora. Cel mai adesea există o întrebare cu privire la minim și maxim
închidere tranzitiv
produs Direct (cartezian) de mulțimi A și B este multimea
Componente grafic puternic conectat
Conceptul de conectivitate puternică se aplică numai digraphs. Digraph bază - neograf cu aceleași vârfuri, dar nervurile în locul arcurilor corespunzătoare. apeluri digraph
definiții de bază
Arbore - conectat grafic fără cicluri. Lemn (sau aciclic grafic) - neograf fără cicluri. Componentele forestiere sunt copaci.
centroidul copac
Filiala la partea de sus a arborelui v - este subgraful maxim care conține v ca pandantiv topuri. greutate
codare zecimal
Copacii sunt o formă importantă de grafice. Folosind baza de date cu arbore descris, algoritmi de arbori model și programe care sunt utilizate în inginerie electrică și chimie. Una dintre sarcinile urgente