Glosar al teoriei grafurilor

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 17 august 2022; verificările necesită 2 modificări .

Aici sunt colectate definiții ale termenilor din teoria grafurilor . Referințele la termenii din acest dicționar (pe această pagină) sunt scrise cu caractere cursive .

# A B C D E F F G I K L M N O P R S T U V W Y Z _ _ _ _ _ _

A

Automorfism - Un izomorfism al unui grafic cu el însuși.
Un grafic aciclic este un grafic fără cicluri .

B

O bază de graf este un subset minim al setului de vârfuri de graf de la care este accesibil orice vârf de graf.
Un grafic infinit este un grafic care are infinit de vârfuri și/sau muchii.
Bigraf - vezi graficul bipartit .
Un bloc este un grafic fără balamale .
Proiectarea blocului cu parametrii (v, k, λ) este o acoperire cu multiplicitatea λ a unui grafic complet pe v vârfuri de către grafice complete pe k vârfuri.

În

Valența vârfului - vezi gradul vârfului .
Conceptul de vârf , nod de bază : un punct în care muchiile și/sau arcele pot converge/ieși. Mulțimea vârfurilor unui graf G se notează cu V(G).
O acoperire de vârfuri este un set de vârfuri dintr-un grafic astfel încât fiecare muchie este incidentă la cel puțin un vârf din acest set.
Greutatea unei muchii este valoarea atribuită unei muchii date a unui grafic ponderat . De obicei, greutatea este un număr real , caz în care poate fi interpretată ca „ lungimea ” marginii.
Un grafic ponderat este un grafic , căruia fiecărei margini i se atribuie o anumită valoare ( greutatea marginii ). Vezi graficul etichetat .
Un vârf suspendat este un vârf al cărui grad este egal cu 1 (adică ). $d(v)=1$

Un grafic complet deconectat este un grafic obișnuit de grad 0, adică un grafic fără muchii .
Înălțimea unui copac este calea cea mai lungă de la rădăcină la frunză .

G

Un grafic hamiltonian este un grafic care are un ciclu hamiltonian .
O cale hamiltoniană este o cale simplă într-un grafic care conține toate vârfurile graficului exact o dată.
Un ciclu hamiltonian este un ciclu simplu dintr-un grafic care conține toate vârfurile graficului exact o dată.
O realizare geometrică este o figură ale cărei vârfuri corespund vârfurilor graficului, muchiile - muchiile graficului și muchiile din figură conectează vârfurile corespunzătoare vârfurilor din grafic.
Un grafic geometric este o figură plată de vârfuri - puncte ale planului și muchii - linii care leagă unele perechi de vârfuri. Poate reprezenta orice grafic în mai multe moduri.
Un hipergraf este o colecție de un set de vârfuri și un set de hipermuchii (o submulțime a celei de-a n-a puteri euclidiene a mulțimii de vârfuri, adică hipermuchiile conectează un număr arbitrar de vârfuri).
Graficele homeomorfe sunt grafice obținute dintr-un singur grafic folosind o succesiune de subdiviziuni de muchii.
O față este o zonă delimitată de muchii într- un graf plan și nu conține vârfuri și muchii ale grafului. Partea exterioară a avionului formează și o față.
Graficul este un concept de bază. Include un set de vârfuri și un set de muchii care este un subset al pătratului cartezian al mulțimii de vârfuri (adică fiecare muchie conectează exact două vârfuri).
Un grafic al genului g este un grafic care poate fi reprezentat fără intersecții pe o suprafață a genului g și nu poate fi reprezentat fără intersecții pe orice suprafață a genului g -1. În special, graficele plane au genul 0.

D

Grafic dual . Un grafic A se numește dual unui grafic plan B dacă vârfurile graficului A corespund fețelor graficului B și două vârfuri ale graficului A sunt legate printr-o muchie dacă și numai dacă fețele corespunzătoare ale graficului B au cel puțin o margine comună.
Un graf bipartit (sau bigraf , sau un graf par ) este un grafastfel încât mulțimea de vârfuri V este împărțită în două submulțimi care nu se intersecteazăși, iar orice muchie E este incidentă la un vârf de lași un vârf de la(adică, conectează un vârf dela un vârf de la). Adică, colorarea corectă a graficului se realizează cu două culori. Mulțimileșisunt numite „părți” ale unui graf bipartit. Un graf bipartit se numește „complet” dacă oricare două vârfuri înșisunt adiacente. Dacă,, atunci graficul bipartit complet este notat cu. $G(V,E)$ $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$ $V_{1}$ $V_{2}$ $\left|V_{1}\right|=a$ $\left|V_{2}\right|=b$ $K_{{a,b}}$
Un graf dublu conectat este un graf conectat care nu are balamale .
Un arbore este un grafic conectat care nu conține cicluri .
Diametrul graficului este distanța maximă dintre vârfuri pentru toate perechile de vârfuri. Distanța dintre vârfuri este cel mai mic număr de muchii dintr-o cale care leagă două vârfuri. $\mathrm {diam} (G)$
Lungimea traseului - numărul de margini din traseu (cu repetări). Dacă ruta este , atunci lungimea lui M este egală cu k (notat cu ). $M=v_{0},e_{1},v_{1},e_{2},v_{2},...,e_{k},v_{k}$ $\left|M\right|=k$
Lungimea traseului este numărul de arce ale căii (sau suma lungimilor arcelor sale, dacă acestea din urmă sunt date). Deci, pentru calea v 1 , v 2 , …, v n lungimea este n-1.
Arcul este o muchie orientată .
Un complement de graf este un grafic peste același set de vârfuri ca și cel original, dar vârfurile sunt conectate printr-o muchie dacă și numai dacă nu există muchie în graficul original.

E

Murul unui graf nedirecționat G este o familie de subgrafe conectate ale grafului G care sunt tangente unul la celălalt.

W

Graficul stea este un grafic bipartit complet. $K_{{1,b}}$

Și

Un vârf izolat este un vârf al cărui grad este 0 (adică nu există margini incidente cu acesta).
Izomorfism . Se spune că două grafice sunt izomorfe dacă există o permutare a vârfurilor astfel încât acestea să fie aceleași. Cu alte cuvinte, două grafice se numesc izomorfe dacă există o corespondență unu-la-unu între vârfurile și muchiile lor care păstrează adiacența și incidența (graficele diferă doar prin numele vârfurilor lor).
Un invariant de grafic este o caracteristică numerică a unui grafic sau a vectorului lor ordonat care caracterizează structura graficului în mod invariant în raport cu renumerotarea vârfurilor.
Un grafic de interval este un grafic ale cărui vârfuri pot fi atribuite unu-la-unu segmentelor de pe axa reală, astfel încât două vârfuri să fie incidente cu aceeași muchie dacă și numai dacă segmentele corespunzătoare acestor vârfuri se intersectează.
Incident este un concept folosit doar în relație cu o muchie sau un arc și un vârf: dacă sunt vârfuri și a este o muchie care le conectează, atunci vârful și muchia sunt incidente, iar vârful și muchia sunt de asemenea incidente. Două vârfuri (sau două muchii) nu pot fi incidente. Pentru a desemna cele mai apropiate vârfuri (margini), se folosește conceptul de adiacență . $v_{1},v_{2}$ $e=(v_{1},v_{2})$ $v_{1}$ $e$ $v_{2}$ $e$

K

O celulă este un grafic regulat al celei mai mici circumferințe pentru un anumit grad de vârfuri.
O clică este un subset de vârfuri de graf care sunt complet conectate între ele, adică un subgraf care este un graf complet .
- Numărul clicei este numărul (G) de vârfuri din cea mai mare clică. Alte nume sunt densitate, densitate.
- Clica maximă este clica cu numărul maxim posibil de vârfuri dintre clicurile graficului.
O roată (notată cu W n ) este un grafic cu n vârfuri (n ≥ 4) format prin conectarea unui singur vârf la toate vârfurile unui ciclu ( n -1).
O tolbă este doar un grafic direcționat.
Un grafic finit este un grafic care conține un număr finit de vârfuri și muchii.
Enumerarea constructivă a graficelor - obținerea unei liste complete de grafice dintr-o clasă dată.
O componentă conexă a unui graf este o submulțime a vârfurilor grafului , pentru oricare două vârfuri din care există o cale de la unul la altul și nu există nicio cale de la vârful acestei submulțimi la un vârf care nu este din această submulțime .
O componentă puternic conectată a unui graf , un strat este setul maxim de vârfuri ale unui graf direcționat , astfel încât pentru oricare două vârfuri din această mulțime există o cale atât de la primul la al doilea, cât și de la al doilea la primul.
Un contur este o cale închisă într-un digraf .
Rădăcina arborelui este nodul selectat al arborelui ; într-un digraf , un vârf cu un grad de intrare zero.
Un cociclu este o tăietură minimă , un set minim de muchii, a cărui eliminare face graficul deconectat.
Muchiile multiple sunt muchii multiple care sunt incidente aceleiași perechi de vârfuri. Găsit în multigrafe .
Un grafic cubic este un grafic obișnuit de gradul 3, adică un grafic în care exact trei muchii sunt incidente la fiecare vârf.
un graf k-partit este un graf G al cărui număr cromatic c(G)=k
Un graf k-conectat este un graf conex în care nu există un setde vârfuri sau mai puține, astfel încât eliminarea tuturor vârfurilor și a muchiilor incidente cu acestearupe conexiunea grafului. În special, un graf conectat este 1-conectat, iar un graf dublu conectat este 2-conectat. $V'$ $k-1$ $V'$

L

Un graf Laman cu n vârfuri este un grafic G astfel încât, în primul rând, pentru fiecare k , orice subgraf al lui G care conține k vârfuri are cel mult 2 k - 3 muchii și, în al doilea rând, graficul G are exact 2 n -3 muchii.

Pădurea este un grafic nedirecționat fără cicluri. Copacii sunt componentele de conectivitate ale unei păduri .
O frunză de copac este un vârf de copac cu o singură muchie sau arc de intrare .
Gradul local al unui vârf este numărul de muchii incidente cu acesta. Bucla contribuie cu „2” la gradul vârfului.

M

Maxi-code este un invariant grafic complet greu de calculat, obținut prin scrierea valorilor binare ale matricei de adiacență într-o linie, urmată de conversia numărului binar rezultat în formă zecimală. Maxi-codul corespunde unei astfel de ordine de rânduri și coloane, în care valoarea rezultată este maxima posibilă. $\mu _{max}$
Potrivirea maximă din grafic. O potrivire se numește maximă dacă orice altă potrivire are mai puține margini.
O rută într-un grafic este o secvență alternativă de vârfuri și muchii în care sunt incidente oricare două elemente adiacente . Dacă , atunci ruta este închisă , altfel este deschisă . $v_{0},e_{1},v_{1},e_{2},v_{2},...,e_{k},v_{k}$ $v_{0}=v_{k}$
Matricea de accesibilitate a unui digraf este o matrice care conține informații despre existența căilor între vârfuri dintr-un digraf.
Matricea de incidență a unui grafic este o matrice ale cărei valori ale elementelor sunt caracterizate de incidența vârfurilor corespunzătoare ale graficului (vertical) și a marginilor acestuia (orizontal). Pentru un grafic nedirecționat, un element ia valoarea 1 dacă vârful și muchia corespunzătoare sunt incidente. Pentru un grafic dirijat , elementul ia valoarea 1 dacă vârful incident este începutul unei muchii, valoarea -1 dacă vârful incident este capătul unei muchii; în alte cazuri (inclusiv for loops ), valorii elementului i se atribuie 0 .
Matricea de adiacență a unui graf este o matrice ale cărei valori ale elementelor sunt caracterizate de adiacența vârfurilor grafului. În acest caz, valorii elementului de matrice i se atribuie numărul de muchii care leagă vârfurile corespunzătoare (adică care sunt incidente la ambele vârfuri).
Mini-codul este un invariant de grafic complet greu de calculat, obținut prin scrierea valorilor binare ale matricei de adiacență într-o linie și apoi conversia numărului binar rezultat în formă zecimală. Mini-codul corespunde unei astfel de ordine de rânduri și coloane, în care valoarea rezultată este cea mai mică posibilă. $\mu _{min}$
Cadrul minim (sau cadrul de greutate minimă , arborele de întindere minim ) al unui grafic este un set aciclic (fără cicluri) de muchii dintr-un grafic conectat, ponderat și nedirecționat care conectează toate vârfurile acestui grafic, în timp ce suma greutăților tuturor marginile din el este minimă.
Mulțimea de adiacență a unui vârf v este mulțimea de vârfuri adiacente vârfului v . Desemnat . $\Gamma ^{+}(v)$
Un grafic minor este un grafic care poate fi obținut din graficul original prin eliminarea și contractarea arcurilor.
O punte este o muchie a cărei îndepărtare crește numărul de componente conectate din grafic.
Un multigraf este un grafic în care poate exista o pereche de vârfuri care sunt conectate prin mai mult de o muchie (nedirecționată) sau mai mult de două arce de direcții opuse.

H

Un graf direcționat este un graf direcționat în care două vârfuri sunt conectate prin cel mult un arc.
- Un graf aciclic direcționat este un graf direcționat fără contururi .
O mulțime de vârfuri independentă (cunoscută și ca o mulțime stabilă în interior ) este o mulțime de vârfuri a unui grafic G în care oricare două vârfuri nu sunt adiacente (nicio pereche de vârfuri nu este conectată printr-o muchie).
- O mulțime independentă se numește maximă atunci când nu există altă mulțime independentă în care ar fi inclusă. Complementul celei mai mari mulțimi independente se numește acoperirea minimă a vârfurilor graficului.
- Cea mai mare multime independenta este cea mai mare multime independenta.
Vârfurile independente sunt vârfuri neadiacente perechi ale graficului. [unu]
Un graf inseparabil este un graf conex, nevid, fără puncte de articulație. [2] .
Un graf normat este un graf direcționat fără cicluri .

Un graf nul ( un graf gol ) este un graf fără vârfuri .

Oh

Circumferința este lungimea celui mai mic ciclu din grafic.
Uniunea de grafice (grafice etichetateși) este un graf acărui mulțime de vârfuri este, iar mulțimea de muchii este. $G_{1}=(X_{1},U_{1})$ $G_{2}=(X_{2},U_{2})$ $G_{1}\cup G_{2}$ $X_{1}\cup X_{2}$ $U=U_{1}\cup U_{2}$
O vecinătate de ordin k este o mulțime de vârfuri la o distanță k de un vârf dat v ; uneori interpretată în sens larg ca o mulțime de vârfuri separate de v la o distanță nu mai mare de k .
Mediul este un set de vârfuri adiacente celui dat.
Un digraf , un grafic direcționat G = (V,E) este o pereche de mulțimi, unde V este o mulțime de vârfuri (noduri), E este o mulțime de arce (margini direcționate). Un arc este o pereche ordonată de vârfuri (v, w), unde vârful v se numește început și w este sfârșitul arcului. Putem spune că arcul v → w duce de la vârful v la vârful w, în timp ce vârful w este adiacent vârfului v.
Un arbore de întindere ( schelet ) al unui grafic conectat (nedirecționat) este orice grafic parțial care este un arbore . $G=(V,E)$ $S=(V,T)$
Un subgraf care se întinde este un subgraf care conține toate vârfurile.

P

O potrivire este un set de muchii neadiacente în perechi.
O buclă este o muchie al cărei început și sfârșit sunt la același vârf.
Intersecția graficelor (grafice etichetateși) este un grafical cărui set de vârfuri este, iar setul de muchii este. $G_{1}=(X_{1},U_{1})$ $G_{2}=(X_{2},U_{2})$ $G_{1}\cap G_{2}$ $X_{1}\cap X_{2}$ $U=U_{1}\cap U_{2}$
Enumerarea graficelor - numărarea numărului de grafice neizomorfe dintr-o clasă dată (cu caracteristici date).
Un vârf periferic este un vârf a cărui excentricitate este egală cu diametrul graficului.
Un grafic plan este un grafic care poate fi desenat ( stivuit ) pe un plan fără margini încrucișate. Este izomorf cu un graf plan, adică este un graf cu intersecții, dar care permite așezarea lui plană, prin urmare poate diferi de un graf plan printr-o imagine pe un plan. Astfel, poate exista o diferență între un grafic plan și un grafic plan atunci când este reprezentat pe un plan.
Un graf plan este un graf geometric în care două muchii nu au puncte comune, cu excepția vârfului incident la ambele (ele nu se intersectează). Este un grafic stivuit pe plan.
Un subgraf al graficului original este un grafic care conține un anumit subset de vârfuri ale graficului dat și un anumit subset de muchii incidente cu acestea. (cf. sugraf .) În ceea ce privește un subgraf, graficul original se numește supergraf
Un grafic complet este un grafic în care pentru fiecare pereche de vârfuri, există o muchie, incidentși incident(fiecare vârf este conectat printr-o muchie de orice alt vârf). $v_{1},v_{2}$ $v_{1}$ $v_{2}$
Un invariant de grafic complet este o caracteristică numerică a unui grafic sau a vectorului lor ordonat, ale cărui valori sunt necesare și suficiente pentru a stabili izomorfismul graficului
Un graf bipartit complet este un graf bipartit în care fiecare vârf al unei submulțimi este conectat printr-o muchie de fiecare vârf al altei submulțimi
Gradul în - din digraf pentru un vârf este numărul de arce care intră în vârf. Notat cu , , sau . $v$ $d^{+}(v)$ $\mathrm {grade} ^{+}(v)$ $\mathrm {indeg} (v)$ $d_{t}(v)$
Gradul de exterior din digraf pentru un vârf este numărul de arce care ies din vârf. Notat cu , , sau . $v$ $d^{-}(v)$ $\mathrm {grade} ^{-}(v)$ $\mathrm {outdeg} (v)$ $d_{o}(v)$
Un grafic etichetat este un grafic căruia îi sunt atribuite vârfuri sau arce un fel de etichetă, de exemplu, numere naturale sau simboluri ale unui alfabet.
Un subgraf generat este un subgraf generat de un set de muchii din graficul original. Nu conține neapărat toate vârfurile graficului, dar aceste vârfuri sunt conectate prin aceleași muchii ca și în grafic.
Ordinea graficului este numărul de vârfuri ale graficului. [3]
O colorare adecvată a unui grafic este o colorare astfel încât fiecare clasă de culori este un set independent. Cu alte cuvinte, într-o colorare adecvată, oricare două vârfuri adiacente trebuie să aibă culori diferite.
Un produs de grafice - pentru grafice date , un produs este un grafic ale cărui vârfuri sunt produsul cartezian al mulțimilor de vârfuri ale graficelor originale. $G_{1}=(V_{1},E_{1})$ $G_{2}=(V_{2},E_{2})$ $G=(V,E)$ $V(G)=V_{1}\time V_{2}$
O cale simplă este o cale în care toate vârfurile sunt distincte.
Un grafic simplu este un grafic care nu are mai multe muchii sau bucle .
O cale simplă este o cale ale cărei toate vârfurile sunt distincte perechi [4] . Cu alte cuvinte, o cale simplă nu trece de două ori prin același vârf.
- Un ciclu simplu este un ciclu care nu trece de două ori prin același vârf.
Un pseudograf este un grafic care poate conține bucle și/sau mai multe muchii.

Un grafic gol ( graf nul ) este un grafic fără muchii .
O cale este o secvență de muchii (într-un grafic nedirecționat) și/sau arce (într-un grafic direcționat), astfel încât sfârșitul unui arc (margine) să fie începutul altui arc (margine). Sau o succesiune de vârfuri și arce (muchii), în care fiecare element este incident cu precedentul și următorul [4] . Poate fi considerat ca un caz special al unui traseu .
O cale într-un digraf este o succesiune de vârfuri v 1 , v 2 , …, v n , pentru care există arce v 1 → v 2 , v 2 → v 3 , …, v n-1 → v n . Se spune că această cale începe la vârful v 1 , trece prin vârfurile v 2 , v 3 , …, v n-1 și se termină la vârful v n .

R

Raza graficului este minimul excentricităților vârfurilor unui graf conectat; vârful la care se atinge acest minim se numește vârf central.
Împărțirea unui grafic este o reprezentare a graficului original ca un set de subseturi de vârfuri în conformitate cu anumite reguli.
Vârful divizat este același cu balamaua și punctul de articulare .
Desfăşurarea unui graf este o funcţie definită pe vârfurile unui graf direcţionat.
Un grafic etichetat este un grafic pentru care sunt date un set de etichete S, o funcție de etichetare a vârfurilor f : A → S și o funcție de etichetare a arcului g : R → S. Grafic, aceste funcții sunt reprezentate prin etichete pe vârfuri și arce. Setul de etichete poate fi împărțit în două subseturi care nu se suprapun de etichete de vârf și etichete de arc.
O tăietură este un set de muchii , a căror eliminare face graficul deconectat .
Un grafic cadru este un grafic care poate fi desenat într-un plan în așa fel încât orice față mărginită să fie un patrulater și orice vârf cu trei sau mai puțini vecini să fie incident cu o față nemărginită. [5]
Colorarea graficelor este împărțirea vârfurilor în mulțimi (numite culori). Dacă, în plus, nu există două vârfuri adiacente care aparțin aceleiași mulțimi (adică două vârfuri adiacente sunt întotdeauna de culori diferite), atunci o astfel de colorare se numește regulată.
Distanța dintre vârfuri este lungimea celui mai scurt lanț (în digraful căii) care leagă vârfurile date. Dacă un astfel de lanț (cale) nu există, se presupune că distanța este egală cu infinitul.
O acoperire de margine este un set de muchii ale graficului astfel încât fiecare vârf este incident cu cel puțin o muchie din acest set.
Graficul liniare al unui grafic nedirecționat este un grafic care reprezintă vecinătatea muchiilor graficului.
Edge este un concept de bază. O muchie conectează două vârfuri ale unui grafic.
Un graf obișnuit este un graf ale cărui grade ale tuturor vârfurilor sunt egale. Gradul de regularitate este un invariant de grafic. Nedefinit pentru grafice neregulate. Graficele obișnuite prezintă o provocare specială pentru mulți algoritmi. $r(G)$ $r(G)$
- Un grafic obișnuit de grad 0 ( grafic complet deconectat , grafic gol , grafic nul ) este un grafic fără muchii .

C

Un graf auto-dual este un graf izomorf cu graficul său dual .
Un copac hiperzvelt (în formă de stea) este un copac care are un singur vârf de grad mai mare de 2.
Conectivitate . Două vârfuri dintr-un grafic sunt conectate dacă există o cale (simplu) care le conectează .
Un graf conex este un graf în care toate vârfurile sunt conectate.
O secțiune a unui grafic este un set de muchii a căror eliminare împarte graficul în două subgrafe izolate, dintre care unul, în special, poate fi un grafic trivial.
O rețea este, în principiu, aceeași cu un graf , deși rețelele sunt de obicei numite grafuri ale căror vârfuri sunt etichetate într-un anumit fel.
- O rețea direcționată este un grafic direcționat care nu conține contururi.
Conectivitate puternică . Două vârfuri dintr-un graf direcționat sunt puternic conectate dacă există o cale de la primul la al doilea și de la al doilea la primul.
- Un digraf puternic conectat este un digraf în care toate vârfurile sunt puternic conectate.
Adjacență - un concept folosit în relație cu doar două muchii sau doar două vârfuri : Două muchii incidente unui vârf sunt numite adiacente ; două vârfuri incidente la aceeași muchie se mai numesc și adiacente . (cf. Incident .)
Un grafic mixt este un grafic care conține atât muchii direcționate, cât și nedirecționate .
O potrivire perfectă este o potrivire care conține toate vârfurile graficului.
Legătura dintre două grafuri și , care nu au vârfuri comune, se numește graf . [6] $G_{1}=(V_{1},E_{1})$ $G_{2}=(V_{2},E_{2})$ $G_{1}+G_{2}=(V_{1}\cup V_{2},E_{1}\cup E_{2}\cup V_{1}\times V_{2}\cup V_{2} \times V_{1})$

Din definiție se poate observa că legătura grafurilor are proprietățile comutativității și asociativității

Spectrul unui grafic este mulțimea tuturor valorilor proprii ale matricei de adiacență, ținând cont de mai multe muchii.
Gradul vârfului este numărul de muchii ale graficului G care sunt incidente cu vârful x . Desemnat. Gradul minim al unui vârf al unui grafic G se notează cu. iar maximul este. $d(x)$ $\delta (G)$ $\Delta (G)$
Contracția muchiei graficului - înlocuirea capetelor muchiei cu un singur vârf, vecinii acestor capete devin vecinii noului vârf. Graficul este contractabil dacă aldoilea poate fi obținut din primul printr-o succesiune de contracții de margine. $G_{1}$ $G_{2}$
Un subgraf ( graf parțial ) al graficului original este un grafic care conține toate vârfurile graficului original și un subset al muchiilor acestuia . (cf. subgraf .)
Supergraf - orice grafic care conține graficul original (adică, pentru care graficul original este un subgraf )

T

Theta-graph este un grafic format din unirea a trei căi care nu au vârfuri comune în interior și au aceleași vârfuri de capăt [7]
Graficul theta al unui set de puncte din planul euclidian este construit ca un sistem de conuri care înconjoară fiecare vârf cu o muchie pentru fiecare con adăugată la punctul mulțimii a cărui proiecție pe axa centrală a conului este minimă.

Un grafic de identitate este un grafic pentru care este posibil un singur automorfism - graficul de identitate . Figurat vorbind, graficul de identitate este un grafic „absolut nesimetric”.
Punctul de articulare este același cu balamaua și vârful de separare .
Triangularea suprafeței - așezarea unui grafic pe o suprafață , împărțindu-l în regiuni triunghiulare; un caz special de triangulare topologică .
Un graf trivial este un graf care are cel mult un vârf .
Un turneu este un grafic direcționat în care fiecare pereche de vârfuri este conectată printr-o singură muchie.

Wu

Un nod este același cu un Vertex .
Stivuire sau încorporare grafică : un grafic este stivuit pe o suprafață dacă poate fi desenat pe această suprafață, astfel încât marginile graficului să nu se intersecteze. (Consultați Graficul planar , Graficul planar .)
Un adăpost este un anumit tip de funcție pe seturile de vârfuri ale unui grafic nedirecționat. Dacă există acoperire, ea poate fi folosită de fugar pentru a câștiga jocul de urmărire-evaziune pe grafic folosind această funcție la fiecare pas al jocului pentru a determina seturi sigure de vârfuri la care să meargă.
Un grafic ordonat este un grafic în care muchiile care ies din fiecare vârf sunt numerotate în mod unic, începând de la 1. Muchiile sunt considerate a fi ordonate în ordinea crescătoare a numerelor. În reprezentarea grafică, muchiile sunt adesea considerate a fi ordonate în ordinea unei traversări standard (de exemplu, în sens invers acelor de ceasornic ).

F

Factorul n al unui grafic este un subgraf regulat de grad . $n$
n-factorizarea unui grafic - împărțirea unui grafic în n-factori independenți .

X

Numărul cromatic al unui grafic este numărul minim de culori necesare pentru a colora vârfurile unui grafic astfel încât orice vârfuri conectate printr-o muchie să fie colorate în culori diferite.
Polinomul caracteristic al unui grafic este polinomul caracteristic al matricei sale de adiacență .

C

Centrul graficului este mulțimea vârfurilor, pentru care egalitatea este adevărată:, unde este excentricitatea vârfului și este raza graficului. $W=\left\{u_{1},u_{2},...,u_{n}\right\}$ $\forall i=1,...,n:\varepsilon (u_{i})=r(G)$ $\varepsilon$ $r$
Un lanț dintr-un grafic este un traseu , ale cărui margini sunt distincte. Dacă toate vârfurile (și, prin urmare, muchiile) sunt diferite, atunci un astfel de lanț se numește simplu ( elementar ). Într-un lanț, vârfurile și se numesc capete ale lanțului. Un lanț cu capete u și v leagă vârfurile u și v . Lanțul care leagă vârfurile u și v este notat cu . Pentru digrafe, un lanț se numește orlanț. $v_{0},e_{1},...,e_{k},v_{k}$ $v_{0}$ $v_{k}$ $\left\langle u,v\right\rangle$ În unele surse , un lanț simplu este un lanț ale cărui margini sunt distincte, ceea ce este o condiție mai slabă.
Ciclul este un circuit închis. Pentru digrafe, un ciclu se numește contur .
- Un ciclu ( ciclu simplu ) într-un digraf este o cale simplă de lungime de cel puțin 1 care începe și se termină la același vârf.
- Ciclul Hamilton este același cu ciclul Hamilton .
Numărul ciclomatic al unui grafic este numărul minim de muchii care trebuie eliminate pentru a face graficul aciclic . Pentru un graf conex, există o relație:unde este numărul ciclomatic, este numărul de componente conectate ale grafului, este numărul de muchii și este numărul de vârfuri . $p_{1}(G)=p_{0}(G)+|E(G)|-|V(G)|,$ $p_{1}(G)$ $p_{0}$ $|E(G)|$ $|V(G)|$

H

Un grafic parțial este același cu un sugraf .
Un graf par este același cu un graf bipartit .
Număr acoperire vârf — dimensiunea celui mai mic acoperire vârf din grafic.
Numărul de independență este dimensiunea celui mai mare set independent de vârfuri din grafic.
Numărul de potrivire este dimensiunea celei mai mari potriviri din grafic.
Număr acoperire margine — dimensiunea celui mai mic capac margine din grafic.

W

O balama este un vârf al unui grafic , în urma căruia, împreună cu toate muchiile incidente cu acesta,numărul componentelor conectate din grafic crește ca urmare a înlăturării acestuia.
Un angrenaj (notat cu ) este un grafic obținut dintr -o roată prin plasarea de vârfuri suplimentare între fiecare pereche de vârfuri adiacente ale perimetrului . Angrenajele aparțin familiei graficelor cadru și joacă un rol important în descrierea subgrafelor interzise ale graficelor cadru [8] $G_{n}$

E

Un grafic Euler este un grafic în care există un ciclu care conține toate muchiile graficului o dată (vârfurile pot fi repetate).
Lanțul Euler (sau ciclul Euler ) - un lanț ( ciclu ) care conține toate marginile graficului (vârfurile pot fi repetate).
Excentricitatea unui vârf este maximul tuturor distanțelor minime de la alte vârfuri la un vârf dat.
O cale elementară este o cale ale cărei vârfuri, cu posibila excepție a primului și ultimului, sunt diferite. Cu alte cuvinte, o cale simplă nu trece de două ori prin același vârf, ci poate începe și se termină la același vârf, caz în care se numește ciclu (ciclu elementar).
Următoarea procedură se numește contracție elementară : luăm o muchie (împreună cu vârfurile incidente acesteia , de exemplu, u și v) și o „contractăm”, adică îndepărtăm muchia și identificăm vârfurile u și v. Vârful obţinut în acest fel este incident cu acele muchii (altele decât) la care u sau v au fost incidente iniţial.

Link -uri

↑ Distel R. Teoria grafurilor Per. din engleza. - Novosibirsk: Editura Institutului de Matematică, 2002. - P. 17.
↑ Harari F. Teoria grafurilor. - M.: Mir, 1972. - S. 41.
↑ Distel R. Teoria grafurilor Per. din engleza. - Novosibirsk: Editura Institutului de Matematică, 2002. - P. 16.
↑ 1 2 Kuznetsov O. P., Adelson-Velsky G. M. / Matematică discretă pentru un inginer. / M .: Energie, 1980-344 p., ill. Pagină 120-122
↑ A. V. Karzanov. Extensii de metrici finite și problema plasării echipamentelor // Proceedings of the ISA RAS. - 2007. - T. 29 . - S. 225-244 (241) .
↑ M. B. Abrosimov. Pe vârful minim 1-extensii de conexiuni ale graficelor de o formă specială. // Teoria aplicată a graficelor - 2011. - Ediția. 4 .
↑ JA Bondy. . - Springer, 1972. - T. 303. - S. 43–54. — (Note de curs la matematică). - doi : 10.1007/BFb0067356 .
↑ H.-J. Bandelt, V. Chepoi, D. Eppstein. Combinatorica și geometria grafelor pătrate finite și infinite // SIAM Journal on Discrete Mathematics . - 2010. - T. 24 , nr. 4 . - S. 1399-1440 . - doi : 10.1137/090760301 . - arXiv : 0905.4537 . .

Literatură

Distel R. Teoria grafurilor Per. din engleza. - Novosibirsk: Editura Institutului de Matematică, 2002. - 336 p.
Harari F. Teoria grafurilor. — M .: URSS , 2003. — 300 p. — ISBN 5-354-00301-6 .