QUÈ ÉS UNA MATRIU D'ADJACÈNCIA

En aquest article, parlarem de la matriu d'adjacència juntament amb la seva representació.

classe abstracta java

Definició de la matriu d'adjacència

En teoria de grafs, una matriu d'adjacència és una manera densa de descriure l'estructura del graf finit. És la matriu 2D que s'utilitza per mapar l'associació entre els nodes del gràfic.

Si un gràfic té n nombre de vèrtexs, llavors la matriu d'adjacència d'aquest gràfic és n x n , i cada entrada de la matriu representa el nombre d'arestes d'un vèrtex a un altre.

Una matriu d'adjacència també s'anomena com matriu de connexió . De vegades també s'anomena a Matriu vèrtex .

Representació de la matriu d'adjacència

Si un gràfic no dirigit G consta de n vèrtexs, aleshores la matriu d'adjacència d'un gràfic és n x n matriu A = [aij] i es defineix per -

a_ij= 1 {si hi ha un camí existeix des de V_ia V_j}

a_ij= 0 {En cas contrari}

Vegem alguns dels punts importants pel que fa a la matriu d'adjacència.

Si hi ha una aresta entre el vèrtex V_ii V_j, on i és una fila i j és una columna, llavors el valor de a_ij= 1.
Si no hi ha cap aresta entre el vèrtex V_ii V_j, aleshores el valor de a_ij= 0.
Si no hi ha bucles autònoms al gràfic simple, aleshores la matriu de vèrtex (o matriu d'adjacència) hauria de tenir 0 a la diagonal.
Una matriu d'adjacència és simètrica per a un gràfic no dirigit. Especifica que el valor de i^thfila i j^thcolumna és igual al valor de j^thfila i^th
Si la matriu d'adjacència es multiplica per si mateixa, i si hi ha un valor diferent de zero hi ha present a la i^thfila i j^thcolumna, després hi ha la ruta des de V_ia V_jamb una longitud equivalent a 2. El valor diferent de zero a la matriu d'adjacència representa que hi ha el nombre de camins diferents.

Nota: En una matriu d'adjacència, 0 representa que no hi ha associació entre dos nodes, mentre que 1 representa que hi ha una associació entre dos nodes.

Com crear una matriu d'adjacència?

Suposem que hi ha un gràfic g amb n nombre de vèrtexs, aleshores la matriu de vèrtex (o matriu d'adjacència) ve donada per -

A = a₁₁a₁₂. . . . . a_1na₂₁a₂₂. . . . . a_2n. . . . . . . . . a_n1a_n2. . . . . a_nn

On l'a_ijés igual al nombre d'arestes des del vèrtex i fins a j. Com s'ha esmentat anteriorment, la matriu d'adjacència és simètrica per a un gràfic no dirigit, de manera que per a un gràfic no dirigit, un_ij= a_ji.

Quan els gràfics són simples i no hi ha pesos a les vores o múltiples arestes, aleshores les entrades de la matriu d'adjacència seran 0 i 1. Si no hi ha autobucles, aleshores les entrades diagonals de la matriu d'adjacència seran 0.

transmissió de mitjans

Ara, vegem la matriu d'adjacència per a un gràfic no dirigit i per a gràfics dirigits.

Matriu d'adjacència per a un gràfic no dirigit

En un gràfic no dirigit, les arestes no estan associades amb les direccions amb elles. En un gràfic no dirigit, si hi ha una aresta entre el vèrtex A i el vèrtex B, els vèrtexs es poden transferir d'A a B així com de B a A.

Considerem el gràfic no dirigit a continuació i intentem construir-ne la matriu d'adjacència.

Al gràfic, podem veure que no hi ha un bucle propi, de manera que les entrades diagonals de la matriu adjacent seran 0. La matriu d'adjacència del gràfic anterior serà -

Matriu d'adjacència per a un gràfic dirigit

En un gràfic dirigit, les arestes formen un parell ordenat. Les arestes representen un camí específic des d'un vèrtex A a un altre vèrtex B. El node A s'anomena node inicial, mentre que el node B s'anomena node terminal.

Considerem el gràfic dirigit a continuació i intentem construir-ne la matriu d'adjacència.

comanda de Windows arp

Al gràfic anterior, podem veure que no hi ha un bucle propi, de manera que les entrades diagonals de la matriu adjacent seran 0. La matriu d'adjacència del gràfic anterior serà -

Propietats de la matriu d'adjacència

Algunes de les propietats de la matriu d'adjacència s'enumeren de la següent manera:

Una matriu d'adjacència és una matriu que conté files i columnes utilitzades per representar un gràfic etiquetat senzill amb els números 0 i 1 en la posició de (V_jo, IN_j), segons la condició de si els dos V_ii V_jsón adjacents.
Per a un gràfic dirigit, si hi ha una aresta entre el vèrtex i o V_ial vèrtex j o V_j, aleshores el valor de A[V_i][IN_j] = 1, en cas contrari el valor serà 0.
Per a un graf no dirigit, si hi ha una aresta entre el vèrtex i o V_ial vèrtex j o V_j, aleshores el valor de A[V_i][IN_j] = 1 i A[V_j][IN_i] = 1, en cas contrari el valor serà 0.

Vegem algunes preguntes de la matriu d'adjacència. Les preguntes següents són sobre els gràfics dirigits i no dirigits ponderats.

NOTA: Es diu que un gràfic és el gràfic ponderat si a cada aresta se li assigna un nombre positiu, que s'anomena pes de l'aresta.

Pregunta 1 - Quina serà la matriu d'adjacència per al gràfic ponderat no dirigit a continuació?

Solució - A la pregunta donada, no hi ha un bucle propi, de manera que està clar que les entrades diagonals de la matriu adjacent per al gràfic anterior seran 0. El gràfic anterior és un gràfic no dirigit ponderat. Els pesos a les vores del gràfic es representaran com les entrades de la matriu d'adjacència.

executa l'intèrpret d'ordres de l'script

La matriu d'adjacència del gràfic anterior serà -

Pregunta 2 - Quina serà la matriu d'adjacència per al gràfic ponderat dirigit a continuació?

Solució - A la pregunta donada, no hi ha un bucle propi, de manera que està clar que les entrades diagonals de la matriu adjacent per al gràfic anterior seran 0. El gràfic anterior és un gràfic dirigit ponderat. Els pesos a les vores del gràfic es representaran com les entrades de la matriu d'adjacència.