SUMMARY POINTs
� Terminologies of graphs : Simple graph : A graph that has no loops and no multiple edges connecting the same pair of vertices Multiple graph : A graph that has multiple edges connecting at least one pair of vertices Cycle : A path that the starting vertex is the end vertex Tree : A connected graph with no cycles Spanning tree : A tree that connects all vertices in the graph
� Directed graphs : 1 . Directed graph : A graph that all edges are assigned with directions 2 . In-degree of a vertex : Number of edges connecting and pointing towards the vertex 3 . Out-degree of a vertex : Number of edges connecting and pointing away from the vertex
� Adjacency matrix M of a graph with n vertices : 1 . n� n: Order of M 2 . The entry mij
� 1 if there is an edge connecting the vertex i and the
3 . 4 . vertex j , and mij
� 0 if otherwise p
M shows the number of walks of length p in the graph p r
�M shows the number of walks of length less than or equal to p r�1 in the graph 5 . The column sum of a transition matrix of a directed graph must be equal to 1
9
� Algorithms of finding minimum spanning trees : 1 . Kruskal ’ s algorithm 2 . Prim ’ s algorithm www . seprodstore . com
123