- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
If the edge (vi, vj) is in E(G), adj_mat[i][j]=1. If there is no such edge in E(G), adj_mat[i][j]=0.
The adjacency matrix for an undirected graph is symmetric; the adjacency matrix for a digraph need not be symmetric. Merits of adjacency matrix
0 1 3 2 1
0 2 3
6
Adjacent and Incident
If (v0, v1) is an edge in an undirected graph,
v0 and v1 are adjacent The edge (v0, v1) is incident on vertices v0 and v1 v0 is adjacent to v1, and v1 is adjacent from v0 The edge <v0, v1> is incident on v0 and v1 A graph may not have an edge from a vertex, i, back to itself. Such edges are known as self loops. A graph may not have multiple occurrences of the same edge. If we remove this restriction, we obtain a data object referred to as a multigraph. 0
A walk that does this is called Eulerian.
Graphs have been used in a wide variety of applications, including
analysis of electrical circuits finding shortest routes project planning the identification of chemical compounds social network analysis.
A tree is a graph that is connected and acyclic.
9
Connected Components in Directed Graph
Weakly Connected Component (WCC)
Ignore directionality and find the connected components
2
3
3
3
1
4
1
5
1
6
1
11
3
in: 1, out: 0
Adjacency Matrix
Let G=(V,E) be a graph with n vertices. The adjacency matrix of G is a two-dimensional n by n array, say adj_mat
2 G3
E(G1)={(0,1),(0,2),(0,3),(1,2),(1,3),(2,3)} E(G2)={(0,1),(0,2),(1,3),(1,4),(2,5),(2,6)} E(G3)={<0,1>,<1,0>,<1,2>}
5
Complete Graph (Clique)
A complete graph is a graph that has the maximum number of edges For undirected graph with n vertices, the maximum number of edges is n(n-1)/2 For directed graph with n vertices, the maximum number of edges is n(n-1) Examples
To determine the connection of vertices is easy n 1 The degree of a vertex is adj _ mat[i][ j ]
j 0
For a digraph, the row sum is the out_degree, while the column sum is the in_degree
0 1 3 G1 0 1
2 2
(iv)
8
0
0 1 2
1 3
2 1
0 2 3
2
(i)
(ii) (iii) (a) Some of the subgraph of G1
(iv)
0
0 1
0 1
0 1
2 G3
(i)
(ii) (iii) (b) Some of the subgraph of G3
Path, Cycle, and Connected Component
A path from vertex vp to vertex vq in a graph, G, is a sequence of vertices, vp, vi1, vi2, …, vin, vq,such that (vp, vi1), (vi1, vi2), …, (vin, vq) are edges in an undirected graph. The length of a path is the number of edges on it. A simple path is a path in which all vertices, except possibly the first and the last, are distinct. A cycle is a simple path in which the first and the last vertices are the same. In an undirected graph G, two vertices, v0, v1, are connected if there is a path in G from v0 to v1. A connected component, or simply a component, of an undirected graph is a maximal connected subgraph.
ind (vi ) A[ j , i ]
j 0
n 1
outd (vi ) A[i , j ]
j 0
12
n 1
Drawback of adjacency matrix
For all node-pairs, i and j, the path from node i to node j and the path from node j to node i must be the same
10
Degree
The degree of a vertex is the number of edges incident to that vertex For directed graph,
2
Euler’s Solution
Euler defined the degree of a vertex as the number of edges incident on it. He then showed that there is a walk starting at any vertex, going through each edge exactly once, and terminating at the starting vertex iff the degree of each vertex is even.
Strongly Connected Component (SCC)
For all node-pairs, i and j, there is a path from node i to node j and there is a path from node j to node i
Rescursively Strongly Connected Component (RSCC)
0 2
If <v0, v1> is an edge in a directed graph
Restrictions on graphs:
1
3
1
2
7
Subgraph
A subgraph of G is a graph G’ such that V(G’)V(G) and E(G’) E(G).
E.g. <v0, v1> represents an edge in which v0 is the tail and v1 is the head.
4
Sample Graphs
0 0 0
1
3 G1
2
3
1 4 G2
5
2
6
incomplete graph
1
complete graph V(G1)={0,1,2,3} V(G2)={0,1,2,3,4,5,6} V(G3)={0,1,2}
Graphs may be the most widely used of all mathematical structures.
