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

[PDF] Adjacency Matrices

Another example of a graph is the route map that most airlines (or railways) produce A copy of the northern route map for Cape Air from May 2001 is Figure 2 This 

Adjacency Matrix

Let G be a graph with V(G) = {1, ,n} and E(G) = {e1, ,em} The adjacency matrix of G, denoted by A(G), is the n×n matrix defined as follows If i = j then the (i, j)-entry of A(G) is 0 for vertices i and j nonadjacent, and the (i, j)-entry is 1 for i and j adjacent

[PDF] Adjacency matrices - Ma/CS 6b

1 fév 2015 · each of its cells Problem Let = , be a graph with adjacency matrix Describe 

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

The powers of the adjacency matrix counts things In particular, entry i, j in As gives the number of walks from i to j of length s The proof is by induction argument

[PDF] Graphs

Adjacency List Incidence matrix Adjacency matrix: In this representation, the adjacency matrix of a graph G is a two dimensional n x n

[PDF] Adjacency and Incidence Matrices

The adjacency matrix of a graph is symmetric The degree of a vertex in a graph is the number of edges incident on that vertex A vertex is odd if its degree is odd; 

[PDF] Matrices and Graphs - math - Ryerson University

Definition 3 Given a weighted graph G, the adjacency matrix is the matrix A = (aij) , where aij = w(vi,vj) For most purposes the adjacency matrix and incidence 

[PDF] directed graph

Adjacency matrices can also be used to represent graphs with loops and multiple Example: We give the adjacency matrix of the pseudograph shown here 

[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

[PDF] adjectif pour décrire le front

[PDF] adjectif pour décrire le nez

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_dbs17.pdfusesText_23