### Graph

 The net is vast and infiniteBasicA Graph (G) is made up of a set V of vertices and a set E of edges.Another names for the vertices are nodes and another name for the edges is links.The order of the graph (|V|) is the number of vertices.The size of the graph (|E|) is the number of edges.A vertex is listed as letter on this page. Ex a graph contain the vertices a, b and c.A edge is listed as as the two vertices it connect. Ex (a,b) and (b,c).In a undirected graph the edge (a,b) = (b,a).A directed graph have edges that go in one direction from a source node to a destination node.WalksA walk is a sequence of vertices. A walk is closed if the first vertex and the last are the same, and open if they are different.A open walk with no repeat vertices is known as a path.A closed walk with no repeat vertices is known as a cycle.A acyclic graph contains no cycles. The length of a walk is the number of edges.TreeA acyclic graph is called a tree.A spanning tree of a graph is another graph that contains all the vertices and is a tree. If each edge has a length then the tree with the minimal sum of all the weights is called the minimum spanning tree.AdjacencyThe degree of a vertex is the number of edges it has. Loops are counted twice.A vertex of degree 0 is a isolated vertex and one with degree 1 is a leaf.The total degree of a graph is the sum of degrees of all it's vertices.Two vertices a and b are called adjacent if they are connected by a edge.OtherA graph is said to be a weighted graph if it's edges contains a value. A complete graph is a graph where there is a edge between every pair of vertices.Both the nodes and the edges can contain information.A graph can be said to be between sparse or dense. Sparse graph have few connections per node and dense graphs have many.Adjacency matrixIf V contain n vertices then the Adjacency matrix of the graph is a n*n matrix where A[i,j] contain 1 if there is a edge (i,j). If no edge it contain 0. In a weighted graph it can contain the weight of the edge.The diagonal entries are zero if there is no loops.In a undirected graph the matrix is symmetric (A[i,j] = A[j,i]). In a undirected graph each matrix element can use one bit per entry.Adjacency matrix storage is O(V^2). Search Algorithms : http://en.wikipedia.org/wiki/Book:Graph_Algorithms
Subpages (3):