Glosar de teoria grafurilor

Acest articol prezintă un index al conceptelor din teoria grafurilor.

A

• adiacență
• arbore - graf neorientat, conex și fără cicluri.

B

• biconex - graf 2-conex, v. graf k-conex.
• bipartit - graf ale cărui noduri pot fi împărțite în două mulțimi disjuncte.

C

• chimic - graf care reprezintă formula structurală a unui compus chimic.
• ciclu - drum în care de la un nod se ajunge la el însuși.
• clică - submulțime de noduri ale unui graf neorientat cu proprietatea că subgraful indus de ele este complet.
• coardă -
• complet - graf neorientat în care fiecare pereche de noduri este conectată printr-o muchie unică.
• componentă (conexă) - subgraf indus în care oricare două noduri sunt legate între ele prin drumuri, și care nu este legată la niciun nod suplimentar din restul grafului.
• conexitate - numărul minim de noduri sau muchii care trebuie eliminate pentru a separa nodurile rămase în două sau mai multe subgrafuri izolate.

D

• diametru
• drum - șir finit sau infinit de muchii care unesc o succesiune de noduri care sunt distincte.

E

• excentricitate

G

• Gabriel - graf în care muchiile leagă noduri adiacente.
• graf - ansamblu a două mulțimi disjuncte, între care s-a stabilit o corespondență și reprezentat ca un grup de puncte pentru noduri, iar acestea sunt unite două câte două de linii sau curbe pentru muchii.

K

• k-conex - graf cu mai mult de k noduri și care rămâne conex ori de câte ori sunt eliminate mai puțin de k noduri.

M

• muchie - segment de dreaptă sau arc care unește două noduri.
• multigraf - graf la care sunt admise muchii multiple și bucle.

N

• nod - element punctual dintr-un graf, legat sau nu de alte noduri prin muchii.

O

• orientare - ordinea de parcurgere a nodurilor unei muchii.
• orientat - graf ale cărui muchii au asociat un sens.

P

• pădure
• planar - graf care poate fi încorporat într-un plan, astfel încât muchiile sale să se intersecteze doar în noduri.

• planar cu muchii drepte - graf planar la care muchiile sale sunt segmente de dreaptă.

• poliedric - graf 3-conex, v. graf k-conex.
• pseudograf - v. multigraf

R

• rădăcină
• regulat - graf la care fiecare nod are același număr de vecini.

S, Ș

• simplex - graf derivat din clicile altui graf.
• subgraf indus (al unui graf) - alt graf, format dintr-o submulțime a nodurilor grafului și din toate muchiile (din graful originar) care conectează perechile de noduri din acea submulțime.

T, Ț

• teoria grafurilor - disciplină care studiază proprietățile grafurilor.
• triconex - graf 3-conex, v. graf k-conex.
• turneu - graf complet, orientat.