Graph Representations, Incidence Matrix, Adjacency Matrix

Graph Representations(ग्राफ का प्रतिनिधित्व ):-

Generally, there are two representations of directed or undirected graph G with matrix in memory i.e..incidence matrix and adjacency matrix representation.

समान्यतः दो रिप्रजेंटेशन का प्रयोग कर डायरेक्टेड एवं अनडायरेक्टेड ग्राफ G को मैट्रिक्स के साथ मेमोरी में दर्शाया जा सकता है ये है इन्सिडेन्स मैट्रिक्स एवं ऐडजेसेन्सी मैट्रिक्स प्रतिनिधित्व। 

  

(a) Representation of the Directed Graph G1 (डायरेक्टेडग्राफ  G1 का प्रतिनिधित्व):-

1.) incidence matrix representation (इन्सिडेन्स मैट्रिक्स प्रतिनिधित्व) :-

If a directed graph G consists of n vertices and m edges, then the incidence matrix is an n x m matrix 

C = [c_ij] such that 

यदि एक डायरेक्टेड ग्राफ G , n वर्टेक्स एवं m एजेस रखता है तब इन्सिडेन्स मैट्रिक्स n x m का एक मैट्रिक्स

C = [c_ij] इस प्रकार होगा कि

             0, if Vi is not incident on edge ej (यदि Vi से ej एज नहीं है )

c_ij =      1, if Vi is the initial vertex of edge ej (यदि Vi , ej एज का प्रारंभिक वर्टेक्स है)

            -1, if Vi is the final vertex of edge ej  (यदि Vi , ej एज का अंतिम वर्टेक्स है)

for above directed graph G1, incidence matrix representation is as follows:-

उपर्युक्त डायरेक्टेड ग्राफ G1 का  इन्सिडेन्स मैट्रिक्स प्रतिनिधित्व निम्न है:-

2.) adjacency matrix representation (ऐडजेसेन्सी मैट्रिक्स प्रतिनिधित्व):-

If a directed graph G consists of n vertices then the adjacency matrix of a graph is an n x n matrix A = [aij] such that 

यदि एक डायरेक्टेड ग्राफ G , n वर्टेक्स रखता है तब ऐडजेसेन्सी मैट्रिक्स n x n का एक मैट्रिक्स A = [aij] इस प्रकार होगा कि

aij =   0, If there is no edge between Vi and Vj (यदि Vi एवं Vj के मध्य कोई एज नहीं है )

          1, if {Vi,Vj} is an edge, Vi is initial vertex and Vj is final vertex  (यदि {Vi ,Vj} एक एज है जिसमे Vi प्रारंभिक एवं Vj अंतिम वर्टेक्स है )

for above directed graph G1 adjacency matrix representation is as follows:-

उपर्युक्त डायरेक्टेड ग्राफ G1 का ऐडजेसेन्सी  मैट्रिक्स प्रतिनिधित्व निम्न है:-

(b) Representation of the Undirected Graph G2(अनडायरेक्टेडग्राफ  G2 का प्रतिनिधित्व):-

1.) incidence matrix representation (इन्सिडेन्स मैट्रिक्स प्रतिनिधित्व):-

If an undirected graph G consists of n vertices and m edges, then the incidence matrix is an n x m matrix C = [c_ij] such that 

यदि एक अनडायरेक्टेड ग्राफ G , n वर्टेक्स एवं m एजेस रखता है तब इन्सिडेन्स मैट्रिक्स n x m का एक मैट्रिक्स

C = [cij] इस प्रकार होगा कि

                       

c_ij =    1, if Vi is incident on edge ej (यदि Vi से ej एज है)

           0, otherwise (अन्यथा)

for above undirected graph G2, incidence matrix representation is as follows:-

उपर्युक्त अनडायरेक्टेड ग्राफ G2 का  इन्सिडेन्स मैट्रिक्स प्रतिनिधित्व निम्न है:-

2.) adjacency matrix representation (ऐडजेसेन्सी मैट्रिक्स प्रतिनिधित्व):-

If a undirected graph G consists of n vertices then the adjacency matrix of a graph is an n x n matrix A = [aij] such that 

यदि एक अनडायरेक्टेड ग्राफ G , n वर्टेक्स रखता है तब ऐडजेसेन्सी मैट्रिक्स n x n का एक मैट्रिक्स A = [aij] इस प्रकार होगा कि

aij =     0, If there is no edge between Vi and Vj (यदि Vi एवं Vj के मध्य कोई एज नहीं है)

            1, if {Vi,Vj} is an edge between Vi and Vj (यदि Vi एवं Vj के मध्य एक एज है)

for above undirected graph G2, adjacency matrix representation is as follows:-

उपर्युक्त अनडायरेक्टेड ग्राफ G2 का ऐडजेसेन्सी मैट्रिक्स प्रतिनिधित्व निम्न है:-