� 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 vertex
3 . 4 . 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 in the r�1
graph 5 . The column sum of a transition matrix of a directed graph must be equal to 1
� Algorithms of finding minimum spanning trees : 1 . Kruskal ’ s algorithm 2 . Prim ’ s algorithm
� Eulerian trails and circuits : |
1 . |
Trail : A sequence of edges that passes through any edge at most once |
2 . |
Circuit : A trail that the starting vertex is the end vertex |
3 . |
Eulerian trail : A trail that passes through all edges of a graph |
4 . |
Eulerian circuit : A circuit that passes through all edges of a graph |
5 . |
An Eulerian trail exists if there exists two and only two vertices of odd |
degree |
6 . |
An Eulerian circuit exists if all vertices are of even degree |
7 . |
Chinese postman problem can be used to find the route of minimum |
weight that covers all edges of a graph |
� Hamiltonian paths and cycles : 1 . Complete graph : A graph that there exists an edge for any pair of two vertices 2 . Hamiltonian path : A path that passes through all vertices of a graph 3 . Hamiltonian cycle : A cycle that passes through all vertices of a graph
� Travelling Salesman problem : 1 . Travelling Salesman problem can be used to find the cycle of minimum weight that passes through all vertices of a graph 2 . Nearest neighbour algorithm can be used to find the upper bound of the solution of a travelling salesman problem 3 . Deleted vertex algorithm can be used to find the lower bound of the solution of a travelling salesman problem
www . seprodstore . com
21