Glosar al teoriei graficelor

LA

Aciclic grafic care nu conține un ciclu . Adiacenta o listă de adiacență este o structură de date formată dintr-un tablou al cărui element -th corespunde listei de vecini cu vârful -th.eu{\ displaystyle i}eu{\ displaystyle i} Adiacenta o matrice de adiacență este o matrice pătrată de obicei notată , cu dimensiuni , fiecare element fiind egal cu numărul de muchii incidente (având pentru extremități) la vârfurile indicilor și (pentru un grafic simplu neponderat ). În cazul unui grafic ponderat, fiecare element este egal cu suma greutății marginilor incidente.LA{\ displaystyle A}|V|×|V|{\ displaystyle | V | \ times | V |}LAeuj{\ displaystyle A_ {ij}}eu{\ displaystyle i}j{\ displaystyle j}LAeuj∈{0,1}{\ displaystyle A_ {ij} \ in \ {0.1 \}} Adiacenta o relație de adiacență proprietate a două vârfuri de a fi conectate de aceeași margine (numite vârfuri adiacente ) sau proprietate a două margini de a avea un capăt comun (numite margini adiacente ). Numită și relație de vecinătate. Adjunct un grafic adjunct este sinonim cu grafic liniar . Admitere un alt nume pentru o matrice laplaciană . Aleatoriu un grafic este aleatoriu sau nedeterminist, de îndată ce construcția sa implică probabilități . Copac grafic conectat și aciclic . Echivalent cu un grafic de vârfuri și margini conectate .nu{\ displaystyle n}nu-1{\ displaystyle n-1} Arborele înrădăcinat sau structura arborelui grafic aciclic direcționat în care distingem o rădăcină de grad de intrare zero și unde toate celelalte vârfuri sunt de gradul de intrare 1. Arc marginea într-un grafic direcționat. O altă formulare: pereche (set ordonat de două elemente) de vârfuri conectate printr-o margine într-un grafic neorientat. Arc-tranzitiv un grafic G este tranzitiv arc dacă grupul său de automorfisme acționează tranzitiv asupra mulțimii arcurilor sale. Date fiind cele două margini , există două automorfisme și cum ar fi , și , , , .e1=tu1v1,e2=tu2v2∈G{\ displaystyle e_ {1} = u_ {1} v_ {1}, e_ {2} = u_ {2} v_ {2} \ în G}(fV,fE):G→G{\ displaystyle (f_ {V}, f_ {E}): G \ rightarrow G}(gV,gE):G→G{\ displaystyle (g_ {V}, g_ {E}): G \ rightarrow G}fE(e1)=e2{\ displaystyle f_ {E} (e_ {1}) = e_ {2}}gE(e1)=e2{\ displaystyle g_ {E} (e_ {1}) = e_ {2}}fV(tu1)=tu2{\ displaystyle f_ {V} (u_ {1}) = u_ {2}}fV(v1)=v2{\ displaystyle f_ {V} (v_ {1}) = v_ {2}}gV(tu1)=v2{\ displaystyle g_ {V} (u_ {1}) = v_ {2}}gV(v1)=tu2{\ displaystyle g_ {V} (v_ {1}) = u_ {2}} Os de peşte conexiune între două vârfuri și . În cazul graficelor direcționate, vorbim despre un arc . Termenul „margine” este apoi folosit pentru a desemna setul de două arce , adică despre viermi și , adică despre viermi . A nu se confunda cu muchia în geometrie .LA{\ displaystyle A}B{\ displaystyle B}(LA,B){\ displaystyle (A, B)}LA{\ displaystyle A}B{\ displaystyle B}(B,LA){\ displaystyle (B, A)}B{\ displaystyle B}LA{\ displaystyle A} Marginea multiplă ansamblu de margini paralele referitoare la o pereche de vârfuri. Marginea paralelă muchia având pentru capete aceleași vârfuri ca o altă margine. Noi vorbim de margine s paralele s . Edge-tranzitiv un grafic este tranzitiv de margine dacă grupul său de automorfisme acționează tranzitiv pe toate marginile sale. O altă formulare a condiției: pentru orice pereche de margini, cel puțin un automorfism trimite prima componentă la a doua. Toate muchiile joacă exact același rol în interiorul graficului. Exemplu: un grafic complet . Automorfism izomorfismul unui grafic pe sine. Fiecare grafic are cel puțin un automorfism: identitate. Setul de automorfisme ale unui grafic formează un grup .

B

Biconnex se spune că un grafic nedirecționat este biconectat dacă, prin eliminarea oricărui vârf al acestuia, rămâne conectat. Aceasta înseamnă a spune că graficul nu are niciun punct de articulare . Bipartit se spune că un grafic este bipartit dacă există o partiție a setului său de vârfuri în două subseturi și astfel încât două vârfuri adiacente să fie în două părți diferite. Aceasta înseamnă a spune că graficul este bicolor .U{\ displaystyle U}V{\ displaystyle V} Bipartit complet se spune că un grafic este bipartit complet dacă este bipartit și există o margine între fiecare vârf al și al . Notăm graficul bipartit complet astfel încât și .U{\ displaystyle U}V{\ displaystyle V}Km,nu{\ displaystyle K_ {m, n}}|U|=m{\ displaystyle | U | = m}|V|=nu{\ displaystyle | V | = n} Biregular un grafic se spune biregular este bipartisan și dacă fiecare dintre părțile sale și are doar vârfuri de același grad. Spunem - regulat dacă și .U{\ displaystyle U}V{\ displaystyle V}(la,b){\ displaystyle (a, b)}deg(U)=la{\ displaystyle deg (U) = a}deg(V)=b{\ displaystyle deg (V) = b} Blob  componentă fără punte în limba engleză, set de vârfuri care nu conțin un istm . bloc  ansamblu de vârfuri care nu conțin un punct de articulare . Buclă creasta începând de la un vârf și ajungând pe sine.

VS

Centralitate un indicator de centralitate este o măsură menită să surprindă noțiunea de importanță într-un grafic, prin identificarea celor mai semnificative vârfuri. Lanţ într-un grafic nedirecționat, un lanț este o secvență finită non-goală de vârfuri astfel încât fiecare pereche de vârfuri consecutive din secvență să fie o margine a graficului; secvența (un minus în lungime) a muchiilor astfel obținute caracterizează și lanțul. Noțiunea corespunzătoare într-un grafic direcționat este cea a unei căi. Lungimea unui lanț este cea a seriei sale de margini (una mai mică decât lungimea seriei sale de vârfuri). Sursa lanțului este primul său de vârf, iar ei obiectiv este ultimul vârf. Se spune că un lanț este elementar dacă niciun vârf nu apare de mai multe ori în secvență, cu excepția sursei și a obiectivului lanțului care pot coincide. cale într-un grafic direcționat, o cale este o secvență finită non-goală de vârfuri astfel încât fiecare pereche de vârfuri consecutive din secvență să fie un arc al graficului; secvența arcurilor astfel obținute caracterizează și calea. Noțiunea corespunzătoare dintr-un grafic neorientat este cea a unui lanț. Lungimea unei căi este cea a seriei sale de arcuri (una mai mică decât lungimea seriei sale de vârfuri). Sursa traseului este primul vârf, iar ei obiectiv este ultimul vârf. Se spune că o cale este elementară dacă niciunul dintre vârfuri nu apare de mai multe ori ca sursă și nici de mai multe ori ca obiectiv al unui arc al căii (dar sursa și scopul căii pot coincide). Omidă este un copac în care toate vârfurile sunt la distanța 1 de o cale centrală. Circumferinţă lungimea celui mai lung ciclu. Număr cromatic numărul minim de culori pentru a colora un grafic fără vârfuri adiacente de aceeași culoare. Număr cromatic care nu se repetă numărul minim de culori pentru a colora un grafic ale cărui șiruri sunt fără factori de culoare repetați. Clic subgraf indus complet, adică un subset de vârfuri astfel încât fiecare să fie conectat la toate celelalte. O clică este un set independent (sau stabil ) al graficului complementar . Colorare funcție care asociază o culoare cu orice vârf, astfel încât două vârfuri adiacente au o culoare diferită (adică partiționează vârfurile în seturi independente). k -colorare colorarea unui grafic în k culori distincte. Complementar complementul (sau inversul sau complementul ) unui grafic simplu este un grafic simplu care are aceleași vârfuri ca G , conectat dacă și numai dacă nu sunt conectate în graficul original, adică .G¯{\ displaystyle {\ bar {G}}}G=(V,E){\ displaystyle G = (V, E)}G¯=(V,[V]2∖E){\ displaystyle {\ bar {G}} = (V, [V] ^ {2} \ backslash E)} Deplin într-un grafic complet fiecare vârf este conectat la toate celelalte. Notăm graficul complet cu n vârfuri.Knu{\ displaystyle K_ {n}} Componenta o componentă a unui grafic este un subgraf conectat maxim. Legate de un grafic este conectat dacă există o cale între orice pereche de vârfuri. Când vorbim de conectivitate pentru un grafic direcționat, nu luăm în considerare acest grafic, ci graficul neorientat corespunzător. Acest lucru poate fi determinat, de exemplu, cu un algoritm de scanare aprofundată . Se spune că un grafic direcționat este puternic conectat dacă, pentru orice pereche de vârfuri (u, v) ale graficului, există o cale de la u la v și de la v la u . k -related-edge un grafic este conectat la margini k dacă încetează să fie conectat numai atunci când eliminăm k margini; acest lucru poate fi verificat prin prezența a k lanțuri disjuncte (care nu împart nicio margine) între fiecare vârf. k -conectat-sus (sau k -conectat ) un grafic este k -summit-conectat dacă încetează să fie conectat numai atunci când eliminăm k vârfuri. Conține un grafic conține si este un subgraf indus de .G{\ displaystyle G}H{\ displaystyle H}H{\ displaystyle H}G{\ displaystyle G} Contracție elimină o margine dintr-un grafic prin fuzionarea celor două capete ale acestuia. Adică, contractarea unei muchii la un vârf face ca vârful să fie adiacent tuturor vecinilor anteriori ai .G/e{\ displaystyle G / e}eXy{\ displaystyle e_ {xy}}X{\ displaystyle x}X{\ displaystyle x}y{\ displaystyle y} Frânghie margine conectând două vârfuri neadiacente ale unui ciclu. Cospectral două grafice sunt cospectrale dacă au același spectru. Deoarece acest spectru se poate baza pe mai multe matrice, putem specifica A-cospectral pentru spectrul matricei de adiacență și L-cospectral pentru spectrul matricei laplaciene. Tăiat partiția vârfurilor în două subseturi. Se poate referi și la setul de margini având un capăt în fiecare subset. Acoperire de vârf Un vârf sau acoperire transversală a unui grafic G este un set C de vârfuri ale lui G astfel încât fiecare margine a graficului este incidentă la cel puțin un vârf al lui C. Acoperire un subgraf unui grafic se referă ( de asemenea , cunoscut ca este o acoperire subgrafic sau un grafic parțială a ) tuturor vârfurilor sunt ( ).H{\ displaystyle H}G{\ displaystyle G} G{\ displaystyle G}G{\ displaystyle G}G{\ displaystyle G}H{\ displaystyle H}VH=VG{\ displaystyle V_ {H} = V_ {G}} Gol un grafic gol are un număr mic de muchii (sau arcuri) în comparație cu numărul de vârfuri. Cub 3-grafic regulat. Ciclu șir cu aceleași vârfuri de început și sfârșit. Cu alte cuvinte, să fie o cale ale cărei margini sunt  : ciclul este apoi definit de . Într-un grafic direcționat, vom vorbi mai degrabă de un circuit decât de un ciclu, chiar dacă terminologia nu este destul de stabilizată.E={s0s1,...,sk-2sk-1}{\ displaystyle E = \ {s_ {0} s_ {1}, ..., s_ {k-2} s_ {k-1} \}}E∪{sk-1s0}{\ displaystyle E \ cup \ {s_ {k-1} s_ {0} \}} Ciclomatic numărul ciclomatic al unui grafic este , unde este numărul de componente conectate. Este, de asemenea, dimensiunea spațiului de cicluri.G=(V,E){\ displaystyle G = (V, E)}M=|E|-|V|+P{\ displaystyle M = | E | - | V | + P}P{\ displaystyle P}

D

Grad în cazul neorientat și neponderat, gradul vârfului este numărul de muchii ale . În cazul unui grafic direcționat, gradul de intrare este numărul de arce către , în timp ce gradul de ieșire este numărul de arce de ieșire . Se notează gradul maxim și gradul minim . În cazul ponderat, gradul unui vârf este suma greutății marginilor incidente acestui vârf.d(s){\ displaystyle d (s)}s{\ displaystyle s}s{\ displaystyle s} d-(s){\ displaystyle d ^ {-} (s)}s{\ displaystyle s} d+(s){\ displaystyle d ^ {+} (s)}s{\ displaystyle s}Δ(G){\ displaystyle \ Delta (G)}δ(G){\ displaystyle \ delta (G)} Pe jumătate pătrat subgraful indus pe unul dintre cele două subseturi de vârfuri ale pătratului unui grafic bipartit. Numit și jumătate bipartit . Jumătate grafic un grafic bipartit care are aproximativ jumătate din marginile unui grafic bipartit complet pe vârfurile sale. Gradele (matrice) matricea de grade a unui grafic este o matrice pătrată de dimensiune astfel încât și .G{\ displaystyle G}|V|×|V|{\ displaystyle | V | \ times | V |}∀eu,Deueu=deg(eu){\ displaystyle \ forall i, D_ {ii} = deg (i)}∀eu,j,eu≠j,Deuj=0{\ displaystyle \ forall i, j, i \ neq j, D_ {ij} = 0} Dens un grafic dens are un număr de muchii (sau arce) apropiate de numărul maxim. Densitate densitatea unui grafic este raportul dintre numărul de muchii (sau arcuri) împărțit la numărul de margini (sau arcuri) posibile. În cazul unui grafic nedirecționat, simplu și finit , acesta este raportul .G=(V,E){\ displaystyle G = (V, E)}2|E||V|⋅(|V|-1){\ displaystyle {\ frac {2 | E |} {| V | \ cdot (| V | -1)}}} Diametru excentricitatea maximă a vârfurilor, notată .D{\ displaystyle D} Dilatare într-o încastrare în care vârfurile unui grafic sunt asociate cu cele ale unui grafic , dilatația este distanța maximă dintre imagini de către doi vârfuri adiacente în . Cu alte cuvinte, dacă două vârfuri sunt vecine într-un grafic, imaginile lor pot fi separate printr-o cale care, prin urmare, mărește distanța dintre ele, iar cea mai mare creștere este dilatarea.f{\ displaystyle f}G{\ displaystyle G}H{\ displaystyle H}f{\ displaystyle f}G{\ displaystyle G} Dimensiune dimensiunea minimă a unui spațiu euclidian, astfel încât un grafic să poată fi reprezentat acolo cu muchii care au toate lungimea 1. Dimensiunea euclidiană sau dimensiunea fidelă dimensiunea minimă a unui spațiu euclidian, astfel încât un grafic să poată fi reprezentat în așa fel încât vârfurile să fie la distanța 1 dacă și numai dacă sunt conectate. Dimensiunea bipartidă numărul minim de subgrafe bipartite complete necesare pentru acoperirea tuturor muchiilor unui grafic. Dimensiune metrică numărul minim de vârfuri ale unui subgraf de astfel încât toate celelalte vârfuri sunt determinate în mod unic de distanța lor față de vârfurile .S{\ displaystyle S}G{\ displaystyle G}S{\ displaystyle S} Distanţă distanța dintre și este lungimea celui mai scurt traseu dintre aceste vârfuri; numită și distanță geodezică .dG(X,y){\ displaystyle d_ {G} (x, y)}X{\ displaystyle x}y{\ displaystyle y} Distanță (matrice de) matrice de elemente a ij corespunzătoare lungimii celei mai scurte căi (distanța) dintre vârfurile indicilor i și j. Distanță-regulat un grafic este regulat la distanță dacă pentru toate vârfurile , numărul vârfurilor vecine ale la distanță și numărul vârfurilor vecine ale la distanță depind numai de și de distanța dintre și . În mod formal, cum ar fi șitu,v∈V{\ displaystyle u, v \ in V}tu{\ displaystyle u}eu{\ displaystyle i}v{\ displaystyle v}j{\ displaystyle j}eu,j{\ displaystyle i, j}d(tu,v){\ displaystyle d (u, v)}tu{\ displaystyle u}v{\ displaystyle v}∃beu,vs.eu∈NU,eu=0 ...d{\ displaystyle \ există b_ {i}, c_ {i} \ în N, i = 0 ... d}vs.0=0{\ displaystyle c_ {0} = 0}∀eu≥1,vs.eu=|NU(v)∩NUeu-1(tu)|,beu=|NU(v)∩NUeu+1(tu)|{\ displaystyle \ forall i \ geq 1, c_ {i} = | N (v) \ cap N_ {i-1} (u) |, b_ {i} = | N (v) \ cap N_ {i + 1 } (u) |} Dominant (sau absorbant) un set de vârfuri este dominant dacă vreun vârf face parte din acesta sau este aproape de un vârf care face parte din el. Duritate duritatea este o măsură a conectivității unui grafic. Se spune că un grafic este -hard pentru un număr real dat dacă, pentru orice număr întreg , nu poate fi împărțit în componente conectate prin îndepărtarea mai puțin a vârfurilor.G{\ displaystyle G}t{\ displaystyle t}t{\ displaystyle t}k>1{\ displaystyle k> 1}G{\ displaystyle G}k{\ displaystyle k}tk{\ displaystyle tk}

E

Spaţiu sau un grafic . Spațiul vârfurilor este spațiul vectorial cu ca bază , adică un spațiu de dimensiune . În același mod, spațiul marginilor este spațiul vectorial cu o bază similară , adică un spațiu de dimensiune . Principiul 0 și 1 este că obținem 1 pentru un vârf (sau margine) aparținând spațiului și 0 în caz contrar.G=(V,E){\ displaystyle G = (V, E)}{0,1}{\ displaystyle \ {0.1 \}}{v1,...,vnu}{\ displaystyle \ {v_ {1}, ..., v_ {n} \}}nu{\ displaystyle n}{0,1}{\ displaystyle \ {0.1 \}}{e1,...,em}{\ displaystyle \ {e_ {1}, ..., e_ {m} \}}m{\ displaystyle m} Etichetare funcție care asociază fiecare vârf cu o etichetă, care poate fi în orice set (numere reale, cuvinte, culori ...). Eulerian o cale euleriană este o cale care trece prin toate marginile exact o dată. Un ciclu eulerian este o cale euleriană în care vârfurile de început și de sfârșit sunt aceleași. Un grafic în care putem construi un ciclu eulerian se numește grafic eulerian; dacă putem construi numai căi eulerian, atunci graficul este semi-eulerian. Un grafic este eulerian dacă fiecare vârf este de grad egal. Excentricitate excentricitatea unui vârf este distanța sa maximă față de toate celelalte vârfuri. Expander (grafic) expander graph în engleză. Fie G = (V, E) un grafic cu n vârfuri. Pentru un subset de noduri W ⊆ V , numita frontieră W și este notat ∂ (W) toate muchiile G pornind de la un vârf de W și care nu conduc la un vârf de W . G este un grafic de expansiune în raportul γ dacă, pentru orice subset de vârfuri W de cardinalitate | W | ≤ n / 2 , avem | ∂ (W) | ≥ γ | W | . Expansiune dacă este minor de (adică rezultă dintr-o serie de contracții) atunci este o extindere a . O operațiune de expansiune înlocuiește un vârf cu două vârfuri conectate printr-o margine și sunt conectate la toți vecinii din . În cazul încorporării unui grafic în , o expansiune are o altă semnificație: este raportul dintre dimensiunea celor două grafice, adică .H{\ displaystyle H}G{\ displaystyle G}H{\ displaystyle H}G{\ displaystyle G}H{\ displaystyle H}s{\ displaystyle s}s1,s2{\ displaystyle s_ {1}, s_ {2}}s1{\ displaystyle s_ {1}}s2{\ displaystyle s_ {2}}s{\ displaystyle s}G1=(V1,E1){\ displaystyle G_ {1} = (V_ {1}, E_ {1})}G2=(V2,E2){\ displaystyle G_ {2} = (V_ {2}, E_ {2})}|V2||V1|{\ displaystyle {\ frac {| V_ {2} |} {| V_ {1} |}}}

F

Poştaş un -factor este un subgraf obișnuit.k{\ displaystyle k}k{\ displaystyle k} Frunze vârf de gradul 1 într-un copac. Terminat un grafic este finit dacă numărul muchiilor și vârfurilor sale este finit. Un grafic infinit al cărui vârf are un grad finit se spune că este local finit . Putere a unui grafic, analogul durității pentru margini. pădure grafic aciclic neorientat . Fiecare componentă conexă a unei păduri formează un copac . Limita marginii muchiile care conduc de la o parte a unui grafic la restul graficului. Limita interioară a vârfurilor vârfurile unei părți a unui grafic conectat la restul graficului. Limita exterioară a vârfurilor vârfurile restului unui grafic conectat la o parte a graficului.

G

Grafic structură compusă din abstracții matematice numite obiecte (sau vârfuri sau noduri sau puncte) în care anumite perechi de obiecte sunt legate de margini (sau legături sau linii). Raft de sârmă grafic grilă

H

Hamiltoniană un grafic este hamiltonian dacă are cel puțin un ciclu care trece prin toate vârfurile exact o dată, iar acest ciclu se numește ciclu hamiltonian . Un ciclu hamiltonian este, de asemenea, un ciclu elementar de aceeași ordine ca graficul. Homeomorfi (grafice) se spune că două grafice G și H sunt homeomorfe dacă putem ajunge la același grafic I subdivizând unele dintre muchiile lor (nu trebuie confundate cu noțiunea de homomorfism). Hipergraf generalizează noțiunea de grafic permițând unei muchii să conecteze mai mult de două vârfuri.

Eu

Impact matricea de incidență a unui grafic este matricea dimensiunilor în care intrarea este 1 dacă vârful este un capăt al marginii , 2 dacă este o buclă și 0 în caz contrar. În cazul orientat, avem dacă iese și 1 dacă revine.G=(V,E){\ displaystyle G = (V, E)}|V|×|E|{\ displaystyle | V | \ times | E |}beuj{\ displaystyle b_ {ij}}veu{\ displaystyle v_ {i}}Xj{\ displaystyle x_ {j}}Xj{\ displaystyle x_ {j}}veu{\ displaystyle v_ {i}}beuj=-1{\ displaystyle b_ {ij} = - 1}Xj{\ displaystyle x_ {j}}veu{\ displaystyle v_ {i}} Independent două vârfuri sunt independente dacă nu sunt conectate, adică nu adiacente. Un set de vârfuri este independent (sau stabil ) dacă nu există două dintre vârfurile sale adiacente. Indicele cromatic (numărul cromatic de margini) numărul minim de culori necesar pentru a colora marginile unui grafic nu trebuie confundat cu numărul cromatic (al vârfurilor). Indicele Hosoya sau indicele Z numărul de cuplaje ale unui grafic. Induse se spune că un subgraf al unui grafic este indus atunci când, pentru orice pereche de vârfuri de , este conectat la în dacă și numai dacă este conectat la în . O altă formulare a condiției: setul de margini al corespunde setului de margini ale celor două vârfuri accidentale ale .H{\ displaystyle H}G{\ displaystyle G}(X,y){\ displaystyle (x, y)}H{\ displaystyle H}X{\ displaystyle x}y{\ displaystyle y}H{\ displaystyle H}X{\ displaystyle x}y{\ displaystyle y}G{\ displaystyle G}H{\ displaystyle H}G{\ displaystyle G}H{\ displaystyle H} Infinit opus finitului . Interval un grafic de interval este un grafic G astfel încât să putem asocia cu fiecare dintre vârfurile sale un interval peste mulțimea de reali și astfel încât pentru fiecare vârf u și v al lui G să existe o margine între u și v dacă și numai dacă intersecția dintre intervalele lor asociate nu sunt zero, Invariant proprietatea graficului în funcție doar de structura sa ( adică independentă de etichetarea sa). De exemplu, gradul mediu al graficului sau spectrul acestuia. Izolat vârf de grad 0, adică neavând vecin. Izomorfism un izomorfism grafic este un morfism grafic bijectiv (sau inversabil). Izomorf două grafice sunt izomorfe dacă există un izomorfism al graficelor de la unul la altul. Adică, dacă au exact aceeași structură. Este suficient să înlocuiți etichetele vârfurilor, astfel încât un grafic să fie o copie a celuilalt. Isospectral vezi cospectral . Istm muchia unui grafic a cărui eliminare mărește numărul de componente conectate ale graficului.

J

Twin doi vârfuri sunt gemeni dacă au același vecinătate. Dintre gemenii adevărați întâmpină mai mult stres pentru a fi apropiați unul de altul și dacă această constrângere este încălcată atunci când vorbim despre gemeni falși . Noțiunea de vecinătate poate fi generalizată pentru o distanță mai mare de 1: definim vecinătatea de până la distanță de , iar doi gemeni au atunci .s∈V{\ displaystyle s \ în V}r{\ displaystyle r}NUr={tu∈V|d(tu,s)≤r}{\ displaystyle N_ {r} = \ {u \ în V | d (u, s) \ leq r \}}s1,s2∈V{\ displaystyle s_ {1}, s_ {2} \ în V}NUs1=NUs2{\ displaystyle N_ {s_ {1}} = N_ {s_ {2}}}

K

L

Laplacienne o matrice laplaciană este o matrice în care este matricea de grade și matricea de adiacență; obținem forma normalizată prin , unde denotă matricea identității . Este utilizat în teoria spectrală a graficelor .L=D-LA{\ displaystyle L = DA}D{\ displaystyle D}LA{\ displaystyle A}L′{\ displaystyle L '}L′=D-1/2LD-1/2=Eu-D-1/2LAD-1/2{\ displaystyle L '= D ^ {- 1/2} LD ^ {- 1/2} = ID ^ {- 1/2} AD ^ {- 1/2}}Eu{\ displaystyle I} Fără scară un grafic este liber de scară dacă distribuția gradelor sale este apropiată de o lege a puterii . Această noțiune provine din fizică, iar divergențele locale sau abaterea distribuției de la o lege a puterii nu sunt specificate. Grafic liniar linia graficului unui grafic este graficul unde inversăm noduri și muchii, adică două vârfuri adiacente în linie grafic corespund cu două muchii incidente la același vertex în G.G{\ displaystyle G}L(G){\ displaystyle L (G)}

M

Plasă girth în engleză, lungimea celui mai scurt ciclu . Dacă un grafic este aciclic , rețeaua sa este considerată infinită. Seara a ochiurilor de plasă (respectiv cu ochiuri impar ) este lungimea cel mai scurt ciclu de lungime chiar (respectiv impar). Minor un grafic este minor dacă este izomorf pentru un grafic care poate fi obținut prin contractarea zero sau mai multe muchii ale .H{\ displaystyle H}G{\ displaystyle G}G{\ displaystyle G} Morfism aplicație între două grafice care respectă structura acestor grafice. Moară un grafic de moară este o sumă de grafice complete care împart un vârf central. Multigraf grafic cu una sau mai multe muchii sau bucle multiple .

NU

Nodul vârf într-o rețea. Un nod intern este un vârf într-un copac de grad mai mare de 1, adică nu este o frunză. Număr cromatic numărul minim de culori pentru a colora un grafic. Se notează numărul cromatic al unui grafic .G{\ displaystyle G}χ(G){\ displaystyle \ chi (G)} Miezul atât subsetul de vârfuri stabil cât și dominant . Nu un grafic nul este fie un grafic care nu conține vârf, fie un grafic în care toate vârfurile sunt izolate (adică fără margini sau arcuri).

O

Ordin numărul de vârfuri ale graficului. Orientat un grafic este orientat dacă marginile au o semnificație, de exemplu indică faptul că există un arc de la la . Un grafic nu este direcționat dacă marginile sale nu au sens: indică faptul că există o margine între și .etuv{\ displaystyle e_ {uv}}tu{\ displaystyle u}v{\ displaystyle v}etuv{\ displaystyle e_ {uv}}tu{\ displaystyle u}v{\ displaystyle v} Exterior-plan vezi planul exterior .

P

Perfect un grafic este perfect dacă numărul cromatic al fiecăruia dintre subgrafele sale induse este egal cu dimensiunea clicei maxime a .H{\ displaystyle H}H{\ displaystyle H} Parțial Un grafic este un grafic parțial al lui if . Un subgraf parțial al lui este un grafic , cu și .(V,F){\ displaystyle (V, F)}(V,E){\ displaystyle (V, E)}F⊆E{\ displaystyle F \ subseteq E}(V,E){\ displaystyle (V, E)}(W,F){\ displaystyle (W, F)}W⊆V{\ displaystyle W \ subseteq V}F⊆E{\ displaystyle F \ subseteq E} Partiție separarea vârfurilor graficului în seturi de vârfuri disjuncte două câte două și nu goale a căror unire face posibilă găsirea tuturor vârfurilor. În mod formal, o partiție a unui grafic în părți separă setul de vârfuri într-un set care îndeplinește următoarele trei proprietăți: și  ;  ; și .G{\ displaystyle G}k{\ displaystyle k}V{\ displaystyle V}Pk={V1,...,Vk}{\ displaystyle P_ {k} = \ {V_ {1}, ..., V_ {k} \}}∀Veu∈Pk,Veu≠∅{\ displaystyle \ forall V_ {i} \ în P_ {k}, V_ {i} \ neq \ emptyset}Veu⊂V{\ displaystyle V_ {i} \ subset V}∪eu=1 ..kVeu=V{\ displaystyle \ cup _ {i = 1..k} V_ {i} = V}∀(Veu,Vj)∈Pk2,eu≠j⇒Veu∩Vj=∅{\ displaystyle \ forall (V_ {i}, V_ {j}) \ în P_ {k} ^ {2}, i \ neq j \ Rightarrow V_ {i} \ cap V_ {j} = \ emptyset} Lume mica un grafic are fenomenul lumii mici dacă coeficientul său de grupare este mare și distanța medie între două vârfuri este mică. Această noțiune provine din fizică și nu există o definiție exactă a ceea ce este ridicat și a ceea ce este scăzut; considerăm că distanța medie este mică atât timp cât nu depășește logaritmul numărului de vârfuri. Planar un grafic este plan dacă poate fi desenat într-un plan fără a traversa două muchii. Un grafic este plan dacă nu conține și ca minori.K5{\ displaystyle K_ {5}}K3,3{\ displaystyle K_ {3,3}} Exterior plan într-un grafic plan, considerăm regiunile (sau fețele ) înconjurate de margini ca fiind interne . Prin urmare, întregul grafic este înconjurat de o regiune externă . Dacă toate vârfurile sunt pe fața exterioară, atunci graficul este plan exterior. Plonjând să fie două grafice și , o încorporare este o funcție injectivă a în astfel încât fiecare margine a să corespundă unei căi disjuncte a . O încorporare ne permite să spunem că putem folosi un grafic pentru a simula capacitățile celuilalt în ceea ce privește conexiunea: dacă există o margine ( adică o cale dedicată) între două vârfuri, atunci o vom găsi în graficul de simulare din forma unei căi dedicate (dar poate fi mai lungă).G1=(V1,E1){\ displaystyle G_ {1} = (V_ {1}, E_ {1})}G2=(V2,E2){\ displaystyle G_ {2} = (V_ {2}, E_ {2})}V2{\ displaystyle V_ {2}}V1{\ displaystyle V_ {1}}V2{\ displaystyle V_ {2}}G1{\ displaystyle G_ {1}} Punctul de articulare într-un grafic conectat, se spune că un vârf este de articulație dacă subgraful obținut prin ștergerea acestuia nu este conectat. Polinom caracteristic polinomul matricei de adiacență a unui grafic G este polinomul său caracteristic și îl denotăm .|λEu-LA|{\ displaystyle | \ lambda IA ​​|}LA{\ displaystyle A}PG(λ){\ displaystyle P_ {G} (\ lambda)} Ponderat un grafic ponderat este un grafic la care adăugăm o funcție de evaluare. Un grafic poate fi ponderat / valorificat pe vârfurile sale, precum și pe margini. Notăm (resp. ) Greutatea unui vârf (resp. ) Și (resp. ) Greutatea unei muchii (resp. ).p(v){\ displaystyle p (v)}p(eu){\ displaystyle p (i)}v{\ displaystyle v}eu{\ displaystyle i}p(v,v′){\ displaystyle p (v, v ')}p(eu,j){\ displaystyle p (i, j)}(v,v′){\ displaystyle (v, v ')}(eu,j){\ displaystyle (i, j)} Pod într-un grafic conectat, o punte este o margine a cărei îndepărtare deconectează graficul. Produs produsul a două grafice și (posibil îndeplinirea anumitor condiții) este un al treilea grafic obținut din și prin aplicarea anumitor reguli. Distingem produsul cartezian , produsul tensor (în) , produsul lexicografic (în) , produsul puternic (în) , produsul conormal , produsul modular (în) , produsul înrădăcinat (în) și produsul în zig-zag . graficelor.G{\ displaystyle G}H{\ displaystyle H}G{\ displaystyle G}H{\ displaystyle H}      Mers pe jos numit și traseu; vezi calea (considerată în general ca neelementară). O plimbare închisă (sau parcurs închis ) este un circuit. Bine într-o problemă a fluxului, vârf consumând fluxul. De obicei, are un grad de ieșire zero, dar nu neapărat.

Î

R

Rădăcină vârf special al unui copac din care există o cale unică către toate celelalte vârfuri ale graficului. Ray excentricitatea minimă a vârfurilor, notată .R{\ displaystyle R} Ray într-un grafic infinit, un lanț simplu infinit; un astfel de lanț există dacă graficul este conectat și local finit.(s0,s1,...){\ displaystyle (s_ {0}, s_ {1}, \ ldots)} Regulat un grafic este -regular dacă fiecare dintre vârfurile sale este de grad .k{\ displaystyle k}k{\ displaystyle k} Relația Djokovìc-Winkler două margini și sunt în relația Djokovìc-Winkler și o denotăm dacă avem inegalitatea . Această relație este reflexivă și simetrică.eXy{\ displaystyle e_ {xy}}etuv{\ displaystyle e_ {uv}}eXyΘetuv{\ displaystyle e_ {xy} \ Theta e_ {uv}}dG(X,tu)+dG(y,v)≠dG(X,v)+dG(y,tu){\ displaystyle d_ {G} (x, u) + d_ {G} (y, v) \ neq d_ {G} (x, v) + d_ {G} (y, u)} Rețea de flux sau rețea de transport un arc valorificat grafic care modelează o problemă de transport. Mărăcine O mărăcină este o colecție de subgrafe conectate în care oricare două subgrafe au un vârf în comun sau fiecare include un capăt al unei margini. Ordinea unei mărăcini este cea mai mică dimensiune a unui set de vârfuri care are o intersecție fără gol cu ​​toate subgrafele. Lățimea arbore a unui grafic este ordinea maximă a unuia dintre mărăcini sale.

S

Despică un grafic este împărțit ( split graph în engleză) dacă vârfurile sale pot fi partiționate într-o clică și stabilă . Prag Un grafic are un prag dacă există un număr real și, pentru fiecare vârf , o greutate (număr real) astfel încât pentru două vârfuri perechea este o margine dacă și numai dacă .S{\ displaystyle S}v{\ displaystyle v}p(v){\ displaystyle p (v)}tu,v{\ displaystyle u, vb}(tu,v){\ displaystyle (u, v)}p(tu)+p(v)>S{\ displaystyle p (u) + p (v)> S} Separator Este un subset al setului de vârfuri ale unui grafic astfel încât subgraful indus de nu este conectat.X{\ displaystyle X}V{\ displaystyle V}G∖X{\ displaystyle G \ setminus X} Simplu numit și Schlicht ), grafic finit, nedirectat , fără bucle sau muchii multiple. varf de munte un grafic este alcătuit din vârfuri conectate prin arcuri sau muchii. Numit și nod sau mai rar punct . Summit-tranzitiv un grafic este vertex-tranzitiv dacă grupul său de automorfisme acționează tranzitiv asupra setului vârfurilor sale. O altă formulare a condiției: pentru orice pereche de vârfuri, cel puțin un automorfism trimite prima componentă la a doua. Toate vârfurile joacă exact același rol în interiorul graficului. Un grafic tranzitiv la vârf este astfel neapărat regulat. Sursă într-o problemă a fluxului, vârf care produce fluxul. Un astfel de vârf este de obicei de zero grade de intrare, dar nu neapărat. Despică un grafic este împărțit dacă există o partiție a lui V în două subseturi S și C astfel încât S este un set de G și C este o clică a lui G. Denotăm .G=(V,E){\ displaystyle G = (V, E)}G=(S,VS,E){\ displaystyle G = (S, C, E)} Subgraf grafic conținut într-un alt grafic. În mod formal, cu notații intuitive, un grafic este un subgraf al lui if și . Este indusă totuși .H=(VH,EH){\ displaystyle H = (V_ {H}, E_ {H})}G=(VG,EG){\ displaystyle G = (V_ {G}, E_ {G})}VH⊂VG{\ displaystyle V_ {H} \ subset V_ {G}}EH⊂EG{\ displaystyle E_ {H} \ subset E_ {G}}EH=EG∩VH×VH{\ displaystyle E_ {H} = E_ {G} \ cap V_ {H} \ times V_ {H}} Cheie acoperind subgraful căruia încercăm să minimalizăm numărul de muchii ( adică densitatea) menținând în același timp proprietăți bune la distanță. Într-o cheie aditivă (respectiv multiplicativă ), distanța dintre două vârfuri poate fi mărită (respectiv multiplicată ) până la un anumit factor numit întârziere (respectiv dilatarea ). Spectru set de valori proprii ale unei matrice reprezentând graficul. Matricea poate fi Laplace sau adiacență . Relațiile dintre spectrul graficului și proprietățile acestuia fac obiectul teoriei spectrale a graficelor . Grajd un set stabil este un set de 2 până la 2 vârfuri independente. Sinonim: set independent. Subdiviziune subdiviziunea unui grafic constă în adăugarea de vârfuri pe margini, adică înlocuirea muchiilor cu căi. Subdiviziune baricentrică subdiviziunea unui grafic în care fiecare margine a fost înlocuită de o cale de lungime două prin inserarea unui vârf în fiecare margine.G{\ displaystyle G}G{\ displaystyle G} Simetric un grafic este simetric dacă este atât tranzitiv la margine, cât și tranzitiv la vârf. Acest lucru echivalează cu verificarea faptului că toate muchiile și vârfurile sale nu se pot distinge în termeni de izomorfism grafic. Exemplu: graficul Petersen .

T

A tăia numărul de muchii (sau arce) ale graficului. Tehnica spectrală tehnică care implică spectrul graficului. Turneu un grafic direcționat obținut prin orientarea fiecărei muchii a unui grafic complet. Transpus transpunerea unui grafic direcționat este același grafic, dar ale cărui margini au fost inversate. Transversal transversal (sau capac nodal sau purtător ) a unui grafic este un subset de vârf T astfel încât orice margine a graficului este incident la-puțin un vârf al T . Complementul unei transversale este un grajd. Triunghi lungimea ciclului trei. Triangulat un grafic este triunghiular dacă nu conține un ciclu de lungime patru fără șir ca minor. Arborii și graficele de intervale în special sunt triangulate. Triconectat se spune că un grafic nedirecționat este triconectat dacă, prin îndepărtarea oricărui dintre vârfurile sale, rămâne conectat. Aceasta înseamnă a spune că graficul nu are niciun punct de articulare . Banal un grafic este banal dacă are un singur ( grafic singleton ) sau nu are vârf ( grafic nul ). Putem folosi un grafic banal pentru a începe o dovadă prin inducție, dar sunt implicit excluși din teoremele cărora ar constitui uneori contraexemple neinteresante.

U

V

Evaluare funcție care asociază o greutate cu fiecare margine și / sau vârf al graficului. Vorbim apoi despre un grafic valoros. Consultați definiția graficului ponderat mai devreme în această pagină. Vector de intersecție secvența unui grafic distanță-regulat.{b0,b1,...bD,vs.1,vs.2,...,vs.D}{\ displaystyle \ {b_ {0}, b_ {1}, ... b_ {D}, c_ {1}, c_ {2}, ..., c_ {D} \}} Gol un grafic gol este un grafic fără margini, vezi graficul nul . Cartier vecinătatea unui vârf v este setul de vârfuri adiacente lui v (și, eventual, subgraful indus)

W

X

Da

Z

Note și referințe

1. Gambette, Philippe, Metode combinatorii de reconstrucție a rețelelor filogenetice (teză de doctorat), Universitatea din Montpellier II - Sciences et Techniques du Languedoc,2010, p.  16
2. (în) Irène Charon, Iiro Honkala Hudry Olivier și Antoine Lobstein - Proprietăți structurale ale graficelor twin-free, The electronic journal of combinatorics , Volumul 14, 2007.
3. „ray” în engleză.
4. (în) D. Djokovic - Subgrafe de conservare a distanței hipercuburilor, Journal of Combin. Teorie. Ser. B , numărul 14, paginile 263-267, 1973.
5. (în) Dragos Cvetkovic și Michael Doob și Horst Sachs - Spectre of Graphs, Heidelberg , Leipzig, 1994 ( ISBN  3335004078 ) .

Vezi și tu

<img src="https://fr.wikipedia.org/wiki/Special:CentralAutoLogin/start?type=1x1" alt="" title="" width="1" height="1" style="border: none; position: absolute;">