Connectivitat (teoria de grafs)

En la teoria de grafs i l’anàlisi de xarxes socials, la connectivitat d'un graf o xarxa social fa referència al nombre mínim d’elements (vèrtexs o arestes) que es necessiten, i que quan s'eliminen, divideix el graf o la xarxa en components aïllats. Aquests vèrtexs crítics o arestes s’anomenen vèrtexs o arestes de tall, respectivament.

La connectivitat d’un graf és una mesura de la seva cohesió o robustesa. Intuïtivament, un graf és cohesionat si té moltes arestes, si els vèrtexs tenen graus relativament alts, si té molts camins curts en parells de vèrtexs o si té distàncies petites (i per tant un diàmetre petit) en relació amb la seva mida. Per contra, un graf més «vulnerable» corre el risc de desconnectar-se si s'eliminen algunes arestes o vèrtexs.

Connectivitat dels vèrtexs i de l'aresta

La connectivitat de vèrtexs, nodes o punts d'un graf $G$, denotat $\kappa (G)$, és el nombre mínim nodes tallats $\kappa$.Plantilla:Harvnp Així, si el gràfic no està connectat, llavors $\kappa (g)=0$, perquè no s'ha de treure cap vèrtex; Si el gràfic té un punt de tall, aleshores $\kappa (g)=1$, perquè n'hi ha prou amb eliminar un sol vèrtex de manera que el graf no estiga connectat, etc. A més, per a qualsevol valor $k\le \kappa (G)$, es diu que el graf és $\kappa -connex$. Tingueu en compte que un graf complet $K_n$ no té punts de tall i que l'única manera de desconnectar-lo és eliminar els vèrtexs $N-1$, que obté el graf trivial. Per tant, κ$(K_n)=n-1$.

De la mateixa manera, la connectivitat de les arestes o la connectivitat lineal, $\lambda (g)$, és el nombre mínim $\lambda$ per al qual el graf té un tall d'arestes-$\lambda$.Plantilla:Harvnp A més, per a qualsevol valor $l\le \lambda (G)$, es diu que el gràfic és $l$-linealment connex.

Donat un graf dirigit, un parell de vèrtexs són:

• Feblement connectats, si estan units per una semi camí (és a dir, un camí que no considera la direcció de les arestes);
• Connectats unilateralment, si estan units per un camí que va d’un a l’altre;
• Fortament connectats, si estan units per almenys dos camins, un que va d’un a l’altre, i viceversa;
• Connectat recursivament, si estan fortament connectats i el camí d'un a l'altre utilitza els mateixos vèrtexs i arestes que els del camí invers.

Si es compleixen algun d'aquests tipus de connexions, es compleixen tots els tipus anteriors.

Connectivitat dels vèrtexs en grafs ponderats

En el context de l’anàlisi de xarxes socials, per a les xarxes socials representades com a grafs ponderats, és a dir, amb pesos a les arestes, el valor d’una ruta o semi camí es pot definir com el valor mínim de totes les arestes que conté. Un camí nivell C és un camí entre un parell de vèrtexs de manera que totes les arestes que conté són majors o iguals al valor C. Els dos vèrtexs són accessibles al nivell C si hi ha un camí al nivell C entre ells.

Connectivitat de grafs

Un graf no dirigit on tots els seus vèrtexs estan connectats per un camí és un graf relacionat. Per a un graf dirigit, es distingeix entre els següents tipus de connectivitat:

• Dèbilment relacionat, si tots els parells de vèrtexs estan dèbilment connectats;
• Relacionats unilateralment, si tots els parells de vèrtexs estan connectats unilateralment;
• Fortament relacionat, si tots els parells de vèrtexs estan fortament connectats;
• Relacionat recursivament, si tots els parells de vèrtexs estan connectats recursivament.

Aplicacions

En l'anàlisi de les xarxes socials, la connectivitat d'una xarxa social és un concepte important, ja que està relacionat amb el concepte de cohesió social, estudiada en àrees de ciències socials com la sociologia o la psicologia. La noció de connectivitat està relacionada amb les propietats dels vincles interpersonals. Per a les xarxes socials representades com a grafs ponderats, els conceptes de camí C i l'accessibilitat al nivell C s’utilitzen per estudiar subgrups cohesionats per a relacions valorades.

Bibliografia

• Plantilla:Ref-llibre
• Plantilla:Ref-llibre