~ info project ~

Mai 5, 2010

Matricea vârfuri – arce

Filed under: 2. Grafuri Orientate,I. Grafuri — Maura Trocan @ 12:48 pm
Tags: , ,

Este o matrice b cu n linii şi m coloane, în care fiecare element b[i,j] este:

–         1, dacă nodul i este o extremitate iniţială a arcului uj;

–         -1, dacă nodul i este o extremitate finală a arcului uj;

–         0, dacă nodul i nu este o extremitate a arcului uj.

Exemplu:

Pentru graful de mai jos cu n=4 noduri şi m=5 arce, matricea vârfuri – arce este:

Pentru a exemplifica construcţia matricei, vom deduce elementele liniei 3:

–         a[3,1]= 0 pentru că nodul 3 nu este o extremitate a arcului u1. Analog, a[3,3]= 0 deoarece nodul 3 nu este extremitate a arcului u3.

–         a[3,5]= -1 pentru că nodul 3 este o extremitate finală a arcului u5.

–         a[3,2]= 1 şi a[3,4]= 1 întrucât nodul 3 este o extremitate iniţială a arcului u2 respectiv u4.

Observaţii:

Pe fiecare coloană j (aferentă arcului uj), avem exact două elemente nenule: un 1 (linia i pe care se află reprezintă extremitatea iniţială a arcului uj) şi un -1 (linia i pe care se află reprezintă extremitatea finală a arcului uj)

Numărul valorilor de 1 de pe linia i, reprezintă gradul exterior al nodului i (numărul arcelor ce au ca extremitate iniţială pe i), iar numărul valorilor de -1 de pe linia i reprezintă gradul interior al nodului i (numărul arcelor care au ca extremitate finală pe i).

Lasă un comentariu »

Niciun comentariu până acum.

RSS feed for comments on this post. TrackBack URI

Lasă un răspuns

Completează mai jos detaliile despre tine sau dă clic pe un icon pentru autentificare:

Logo WordPress.com

Comentezi folosind contul tău WordPress.com. Dezautentificare / Schimbă )

Poză Twitter

Comentezi folosind contul tău Twitter. Dezautentificare / Schimbă )

Fotografie Facebook

Comentezi folosind contul tău Facebook. Dezautentificare / Schimbă )

Fotografie Google+

Comentezi folosind contul tău Google+. Dezautentificare / Schimbă )

Conectare la %s

Creează un sit web gratuit sau un blog la WordPress.com.

%d blogeri au apreciat asta: