[PDF] [PDF] Matrices and Graphs - math - Ryerson University

Adjacency Matrix

Let G be a connected graph with vertices {1, ,n} and let A be the adjacency matrix of G If i, j are vertices of G with d(i, j) = m, then the matrices I,A,

[PDF] Adjacency Matrices

Matrix notation and computation can help to answer these questions The adjacency matrix for a graph with n vertices is an n×n matrix whose (i,j) entry is 1 if the 

[PDF] Graphs and Matrices 1 The Adjacency Matrix of a Graph 2 Powers of

The adjacency matrix A of a graph is defined by numbering the vertices, say from 1 up to n, and then putting aij = aji = 1 if there is an edge from i to j, and

[PDF] Graphs with Circulant Adjacency Matrices* - CORE

l INTRODUCTION A number of recent papers [1-10] have dealt with directed or undirected graphs whose adjacency matrices are circulants A circulant matrix is

[PDF] On the inverse of the adjacency matrix of a graph - CORE

Here we consider only × adjacency matrices {G} of parent graphs {G} (and their vertex–deleted subgraphs) where G is a non–singular matrix with zero diagonal

[PDF] Matrices and Graphs - math - Ryerson University

Obviously the incidence matrix or adjacency matrix provide a useful way of holding a graph in an array One disadvantage to using an array is that it is wasteful, 

[PDF] The adjacency matrix - TELCOM2125: Network Science and Analysis

etc ○ These relations are captured through directed networks/ graphs ○ The adjacency matrix of a directed graph 

[PDF] adjacency matrix directed graph

[PDF] adjacency matrix example

[PDF] adjacency matrix squared meaning

[PDF] adjacencymatrix

[PDF] adjacent vertex in directed graph

[PDF] adjacent vertex in graph

[PDF] adjacent vertices meaning in english

[PDF] adjacent_vertices boost graph

[PDF] adjectif masculin et feminin pdf

[PDF] adjectif possessif demonstratif exercices

[PDF] adjectif possessif et demonstratif exercices

[PDF] adjectif possessif et démonstratifs

[PDF] adjectif possessif exercises

[PDF] adjectif possessifs exercices pdf

[PDF] adjectif pour décrire le ciel

Matrices and Graphs

P. Danziger

1 Matrices and Graphs

Definition 1Given a digraphGwe can representG= ({v1,v2,...,vn},E)by a matrixA= (aij) whereaij=the number of edges joiningvitovj.Ais called the inidence matrixofG. If the edges ofG. Clearly if a digraph,G= (V,E), satisfies (vi,vj)?E?(vj,vi)?E(A=At) thenGis equivalent to an undirected graph. SoGis a graph (as opposed to a digraph) if and only if its incidence matrix is symmetric. (i.e. the matrix is equal to its transpose,A=AT). Alternatively, we can create a digraph from an undirected graph by replacing each edge{u,v}of the undirected graph by the pair of directed edges (u,v) and (v,u). Definition 2A weighted graphis a graph in which each edge has an associated weight or cost. In a weighted graph we usually denote that weight of an edgeebyw(e), or ife=uvwe can write w(u,v). If no explicit weight is given we assume that each edge has weight 1 and each non edge weight 0. Definition 3Given a weighted graphG, the adjacency matrixis the matrixA= (aij), where a ij=w(vi,vj). For most purposes the adjacency matrix and incidence matrix are equivalent. Note that ifGis not connected then the connected components ofGform blocks in the adjacency matrix, all other entries being zero. Theorem 4LetGbe a graph with connected componentsG1,...,Gk. Letnibe the number of vertices inGi, and letAibe the adjacency matrix ofGi, then the adjacency matrix ofGhas the form A

10...0

0A20 0Ak Theorem 5Given Two graphs,GandH, with adjacency matricesAandBrespectively,G≂=H if and only if there is a permutation of the row and columns ofAwhich givesB. Isomorphism is just a relabeling of the rows and columns of the adjacency matrix. 1

Matrices and Graphs P. Danziger

2 Storing Graphs

We wish to be able to store graphs in computer memory. Obviously the incidence matrix or adjacency matrix provide a useful way of holding a graph in an array. One disadvantage to using an

array is that it is wasteful, each edge information is stored twice, once asa[i][j] and once asa[j][i].

Further just to specify the adjacency matrix requiresO(n2) steps. There are two other (related) standard methods for storing graph in computer memory, adjacency lists and adjacency tables. We use a list rather than an array, for each vertex we list those vertices adjacent to it. Note that in practice this can be done either as a matrix or a list. If it is done as a matrix then the matrix has sizen×Δ and is called an adjacency table. In an adjacency listthe vertices adjacent to a cvertexiare stored as a list, usually the end of the list is indicated by a non valid value. Thus for eachi L(i,0) gives the adjacent vertex number, L(i,1), gives a pointer to the next list entry, or 0 for none.

Example 6

4? 1 3? 2? ((0 0 1 0

0 0 1 0

1 1 0 1

0 0 1 0)

))13 23

31 2 4

43
((3-1-1 3-1-1 1 2 4

3-1-1)

))iL(i,0)L(i,1)130 230
315
430
526
640

Adjacency MatrixAdjacency TableAdjacency List

The maximum number of edges in a simple graph isO(n2), a graph with relatively few edges, say o(n2), is called a sparse graph.

2.1 Matrices and Walks

Definition 7Given a walkv1e1...ek-1vkin a graphG, the lengthof the walk is the number of edges it contains (k-1). Problemgiven a positive integerk, a (directed) graphGand two verticesviandvjinG, find the number of walks fromvitovjof lengthk. Theorem 8IfGis a graph with adjacency matrixA, and verticesv1,...,vn, then for each positive integerktheijthentry ofAkis the number of walks of lengthkfromvitovj. 2

Matrices and Graphs P. Danziger

ProofLetGbe a graph with adjacency matrixA, and verticesv1,...,vn.

We proceed by induction onkto obtain the result.

Base CaseLetk= 1.A1=A.

a ij= the number of edges fromvitovj= the number of walks of length 1 fromvitovj.

Inductive StepAssume true fork.

Letbijbe theijthentry ofAk, and letaijbe theijthentry ofA. By the inductive hypothesisbijis the number of walks of lengthkfromvitovj. Consider theijthentry ofAk+1=AAk=ai1b1j+ai2b2j+...+ainb2n=?n m=1aimbmj.

Considerai1b1j

= number of walks of lengthkfromv1tovjtimes the number of walks of length 1 fromvitov1 = the number of walks of lengthk+ 1 fromvitovj, wherev1is the second vertex. This argument holds for eachm, i.e.aitbtj= number of walks fromvitovjin whichvmis the second vertex. So the sum is the number of all possible walks fromvitovj.?

There is a related method for finding the shortest path between any specified pair of points. Suppose

that the points have been orderedV={v1,v2,...,vn}, for each pairi,jfrom 1 tonlet W

0(i,j) =?

?The weight of the edgevivjifvivj?E

0 ifi=j

∞ifvivj??E and for eachkfrom 0 ton-1 define W k+1(i,j) = min(Wk(i,j), Wk(i,k) +Wk(k,j)) Theorem 9Wn(i,j)is the length of the shortest path fromvitovj. Proof:For a given value ofkletSk={v1,...vk}. We show thatWk(i,j) is the length of the shortest path fromvitovjusing only the vertices in the subsetSkby induction onk. Base CaseWhenk= 0,W0(i,j) is the weight of the edgevivj, if it exists. Inductive StepNow assume thatWk(i,j) is the length of the shortest path fromvitovjusing only the vertices inSk. ConsiderWk+1(i,j), if there is a shortervivj-path using the vertexvk+1as well, it will have length equal to the shortestvivk+1-path using only vertices fromSkplus the length of the shortest v k+1vj-path using only vertices fromSk, that isWk(i,k+ 1)+Wk(k+1,j). On the other hand, if there is no shorter path usingvk+1, the valueWk(i,j) will remain unchanged.

Now,Sn=V, so the result follows.?

This suggests an algorithm for building the shortest path list.

Initialization:

InitialiseW

Iteration:

for k = 1 ton for i = 1 ton for j = 1 ton W k(i,j) = min(Wk-1(i,j), Wk-1(i,k-1) +Wk-1(k-1,j))

This algorithm has running timeO(n3).

3quotesdbs_dbs20.pdfusesText_26