Definirea graficului, H4S

graf neorientat cu șase vârfuri și șapte muchii

În teoria grafurilor matematică și graficul de calculator - un set de set nevida de vârfuri și un set de perechi de noduri.

Obiectele sunt reprezentate ca noduri. sau grafic noduri si link-uri - cum ar fi arc. sau coaste. Pentru diferite aplicații, diferite tipuri de grafice pot fi orientate, restricții cu privire la numărul de link-uri și date suplimentare cu privire la noduri sau muchii.

Multe structuri de interes practic în matematică și informatică, pot fi reprezentate prin grafice. De exemplu, structura Wikipedia pot fi modelate de un grafic direcționat (digraph), în care partea de sus - acest articol, iar arcele (muchiile orientate) - (. A se vedea harta tematică) hyperlink-uri.

defini

• V este un set nevidă de noduri sau noduri,
• E este multimea de perechi (în cazul unui graf neorientat - neordonate) noduri, numite muchii.

V (și, prin urmare, E. altfel ar fi o multiset) sunt considerate în general seturi finite. Multe rezultate bune pentru graficele finite, incorecte (sau în orice alt mod) pentru grafice infinite. Acest lucru se datorează faptului că o serie de considerații pentru a fi false în cazul seturilor infinite.

Nodurile și marginile graficului sunt, de asemenea, numite elemente ale graficului, numărul de noduri într-un grafic | V | - comandă. numărul de muchii | E | - dimensiunea graficului.

Nodurile u și v sunt numite noduri terminale (sau se termină) margini e = u, v>. Edge, la rândul său, se conectează partea de sus. Două vârfuri de capăt ale aceleiași coaste sunt numite vecini.

Două margini sunt numite adiacente. în cazul în care acestea au un nod final comun.

Două margini sunt numite multipli. în cazul în care o multitudine de noduri de capăt coincid.

O margine se numește buclă. Dacă capetele sunt aceleași, adică, e = v, v>.

Gradul de deg V V picuri se face referire la numărul de muchii pentru care este un scop (bucla este considerată de două ori).

Vertex este numit izolat. dacă nu este sfârșitul pentru orice fin, agățat (sau foaie), în cazul în care acesta este sfârșitul exact o muchie.

grafic regia

Arc - o pereche ordonată de noduri (v, w). unde vertex v este numit la început și w - end arc. Putem spune că arcul conduce la un vârf v trece prin punctul w.

Număr mixt

grafG mixt - un grafic în care pot fi orientate unele margini, iar unele - neorientate. Înregistrate ordonate triplu G. = (V, E, A), unde V. E și A sunt definiți la fel ca mai sus.

Oriented și grafice neorientate sunt cazuri speciale de amestec.

grafice izomorfe

Grafic G este numit izomorfă graficul H. Dacă există o bijectie f din multitudinea de noduri din graf G H. multitudine de noduri având următoarea proprietate: dacă graficul G are o margine din vertexul la vârful A în graficul B. H trebuie să fie o muchie din vertex f ( a) în partea de sus f (B) și invers - dacă spațiul H este o muchie de la vertex la vertex o in B. grafeG fi o muchie din vertex f - 1 (a) la vertex f - 1 (B). În acest caz, graficul regia trebuie să mențină, de asemenea, o nervură de orientare bijectie. În cazul unui grafic bijectie ponderat, de asemenea, trebuie să păstreze nervurilor în greutate.

Alte definiții corespunzătoare

Path (sau lanț) în grafic este o secvență finită de noduri, în care fiecare nod (cu excepția ultimului) este conectat la alta în secvența de noduri ale marginii.

Orientată de o digraph este o secvență finită de vârfuri vi, care pentru toate perechile (vi, vi + 1) sunt (orientate) margini.

Un ciclu este o cale în care primul și ultimul nodurile sunt aceleași. Când calea etomdlinoy (sau ciclu) este numărul de marginile sale constitutive. Rețineți că, dacă nodurile u și v sunt capetele unei margini, apoi conform definiției, o secvență (u, v, u) este un ciclu. Pentru a evita astfel de cazuri „degenerate“, introduc următoarele concepte.

Calea (sau ciclu), se numește simplu. în cazul în care marginile nu se repetă; elementar. în cazul în care acesta este un simplu și vârfuri în ea nu se repetă. Este ușor de observat că:

• Fiecare mod de a conecta cele două vârfuri conține o cale elementară care leagă aceleași două vârfuri.
• Fiecare cale simplă conține ciclu elementar non-elementar.
• Fiecare ciclu simplu, trece printr-o buclă de nod (sau nervuri) soderzhitelementarny (sub-) extinzându-se prin același vertex (sau margine).
• Buclă - ciclul elementar.

O relație binară pe mulțimea de noduri specificate ca „există o cale de la u la v», este o relație de echivalență. și, prin urmare, rupe setul de clase de echivalență, numite componente ale graficului. În cazul în care numărul este exact un component conectat, graficul este conectat. În componenta conectată poate introduce ponyatierasstoyaniya între nodurile ca lungimea minimă a căii conectarea acestor noduri.

Fiecare subgraf maximal conectat de un grafic G este o componentă conectată (sau componentă) a graficului G. Termenul „maxim“ înseamnă includerea unui maxim, care nu este conținută într-un subgraf conectat cu un număr mare de elemente

Edge a graficului este numit un pod. în cazul în care eliminarea acestuia crește numărul de componente.

Caracteristici suplimentare a graficului

• conectat. dacă pentru oricare două noduri u, v este o cale de la u la v.
• orientat puternic conectat sau conectat. în cazul în care este orientat, și de la orice nod la orice alt există o cale îndreptată.
• copac. în cazul în care este conectat și nu conține cicluri simple.
• completă. dacă oricare dintre cele două (ridicat în cazul în care bucla nu este permis), nodurile conectate de margine.
• bipartite. în cazul în care nodurile sale pot fi împărțit în două subseturi disjuncte V1 și V2, astfel încât fiecare margine se conectează un vârf al unui V1 V2 de la vârf.
• k-Dolny. în cazul în care nodurile sale pot fi împărțite în k subseturi disjuncte V1, V2. ..., Vk, astfel încât vor exista margini de conectare vârfuri ale aceluiași subset.
• bipartit complet. în cazul în care fiecare nod dintr-un subset este conectat la o margine la celălalt subset nod.
• planare. în cazul în care graficul poate fi reprezentat de diagrama pe planul fără a trece margini.
• ponderat. În cazul în care fiecare muchie este atribuit un anumit număr numit greutatea marginii.

Moduri de a reprezenta un grafic în informatică

Matricea adiacență

Tabel în care coloanele și rândurile corespund nodurile graficului. În fiecare celulă a numărului matricei este înregistrată, indicând dacă comunicarea din rândul de sus la partea superioară a coloanei (sau invers).

Dezavantajul este cerințele de memorie sunt direct proporționale cu pătratul numărului de noduri.

• Matricea bidimensional;
• Matricea cu lacune;
• implicit Referința (cu ajutorul funcției).

matrice de incidență

Fiecare linie corespunde unui nod specific al graficului, iar coloanele corespund graficului relațiilor. Celula în linie i-lea cu coloana j-a matricei este scris:

1, în cazul în care conexiunea j «afară» din punctul I. -1 dacă conexiunea „parte“ din partea de sus, 0 în toate celelalte cazuri (adică, în cazul în care relația este o buclă sau de comunicare nu este incident de la partea de sus)

Această metodă este cea mai încăpător (dimensiune este proporțională cu | E | | V |) pentru depozitare, dar este mai ușor să găsească cicluri în grafic.

Listă de coaste

Listă de margini - este un tip de reprezentare grafic în memoria unui program de calculator, se intenționează ca fiecare muchie este reprezentată de două numere - numerele vârfurile coaste. Listă de coaste este mai convenabil să pună în aplicare diferite algoritmi pe grafice, în comparație cu matricea de adiacenta.

Generalizarea conceptului a graficului

Mai abstract, graficul poate fi definit ca trei (V, E, φ), unde V și E - Unele seturi (vârfuri și muchii, respectiv, ..), și - o funcție de incidență (sau incidentor), care atribuie fiecare margine (ordonate sau neordonate) pereche vershinu și v v (toate). Cazuri particulare ale acestui concept sunt:

• grafice direcționate (digraphs) - când φ (e) este întotdeauna o pereche ordonată de noduri;
• grafice neorientate - unde φ (e) este întotdeauna o pereche de vârfuri dezordonat;
• grafice mixte - în care există ambele margini și bucle dirijate și nedirijate;
• Euler grafice - grafic în care există un traseu circular (ciclu Euler) Euler.
• multigraphs - grafice cu mai multe margini, care au capetele lor aceeași pereche de noduri;
• pseudographs - l multigraphs recunoaște existența bucle;
• grafice simple - fără bucle și margini multiple.

Definiția nu se potrivește unele dintre celelalte generalizările prezentate mai sus:

literatură