Graph

The net is vast and infinite

Basic

  • A 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.

Walks

  • A 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.

Tree

  • A 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.

Adjacency

  • The 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.
Other
  • A 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 matrix

  • If 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



Comments