CseWay

A Way For Learning

Graphs

No comments

Graphs

A graph is a non-linear data structure consisting of vertices (also known as nodes) and edges (links between vertices). Usually this is denoted as G = <V, E>, where V is a set of vertices, and E is a set of edges. Each edge is a pair (x,y), where x and y belongs to V. If the edge pair is ordered, the edge is called directed and thus the graph is directed graph. Otherwise, the graph is called undirected. Sometimes, an edge has a component called edge cost (or weight).
Graphs have applications in many areas: a city map, airports, computer networks, electrical circuits, and so on.
Here is the directed weighted graph
The graph has 5 vertices
V = {v1,v2,v3,v4,v5}
and 6 edges
E ={(v1,v2), (v2,v5), (v5,v3), (v4,v5), (v4,v3), (v4,v1)}
A graph is simple if there is no more than one edge between any two vertices. Otherwise, a graph is called multigraph. We also assume that a graph has no loops - an edge connecting the same vertex. I this course we will consider only simple graphs, without self-loops or multiple edges.
In a directed graph, an edge leaves its origin and ends in the destination. The out-degree of a vertex is the number of edges leaving the vertex. The in-degree of a vertex is the number of edges entering the vertex.  The degree of a vertex is the number of edges entering and leaving the vertex. In the above example, the vertex v5 has the in-degree = 2, and the out-degree = 1, thus the degree is 3. The sink is a node, which has out-degree 0. A path is a sequence of distinctive vertices connected by edges. The path length is the number of edges on the path. In the weighted graph, the length is the sum of the costs along the path. A cycle in a directed graph is a path that begins and ends at the same vertex. A forest is a graph without cycles. A graph is connected, if there is a path between any two vertices. A tree is a connected graph without cycles. An alternative definition, a tree is a connected forest.
Proposition 1.
In a directed graph, the sum of in-degrees (or out-degrees) is equal the number of edges.
Reasoning: In a directed graph, any edge (x, y) contributes one unit to all in-degrees and one unit to all out-degrees.
Proposition 2.
In a connected graph with m edges the sum of degrees of all vertices is 2*m.
Reasoning: The proposition follows from the previous one.
Exercise.  Suppose a simple graph has 15 edges, 3 vertices of degree 4, and all others of degree 3. How many vertices does the graph have? 3*4 + (x-3)*3 = 30
Exercise.  Given a graph with 7 vertices; 3 of them of degree two and 4 of degree one. Is this graph is connected? No, 3*2 + 4*1=10 must have 10/2 = 5 edges

Proposition 3.
In an undirected graph with n vertices, there are at most n*(n-1)/2 edges.
In a directed graph with n vertices, there are at most n*(n-1) edges.
Reasoning: Consider an undirected graph with n vertices and choose any vertex. The possible number of edges leaving this vertex is n-1. Take another vertex. The possible number of edges leaving this vertex is n-2 (don't count the edge between these vertices twice!), and so on. We have
(n-1) + (n-2) + ... + 1 = n(n-1)/2
For all graphs, the number of edges and vertices satisfies the following inequality |E|<|V|^2, meaning that the number of edges is always less than the number of vertices squared. If the number of edges is close to |V|^2, we say that this is a dense graph, it has a large number of edges. Otherwise, this is a sparse graph. In most cases, the graph is relatively sparse.
Proposition 4.
Let G be an undirected graph.
  • If G is connected, then |E| >= |V|-1
  • If G is a tree, then |E| = |V|-1
  • If G is a forest, then |E| <= |V|-1
A complete graph is a graph in which every vertex is adjacent (i.e., connected) to every other vertex.
o  o---o   o     o-o
          / \    |x|
         o---o   o-o
A subgraph of a graph G is a graph whose vertices and edges are subsets of the vertices and edges of G. If a graph is not connected, its maximal connected subgraphs are called connected components.
 
     v2      v3          v2       v3
      o       o           o       o
      |\     /|            \     /
      | \   / |             \   /
      |  \ /  |              \ /
      |   ov1 |               o v1
      |  / \  |              / \
      | /   \ |             /   \
      |/     \|            /     \
      o       o           o       o
      v5      v4          v5      v4
        graph              subgraph
 
A spanning tree of a graph is a subgraph, which is a tree and contains all vertices of the graph. An example,
    2
 A------B               A------B
 |    / |                     /
9|   /  |6                   /
 | 3/   |                   /
 | /    |                  /
 D------C                D-----C
    5                spanning tree
Representation:
In a directed graph, vertex x is adjacent to vertex y if and only if there is an edge (x, y) between them.
There are two standard ways to represent a graph:
·  as a collection of adjacency lists
·  or as an adjacency matrix
The adjacency-list representation is used for representation of the sparse graphs. An adjacency-matrix representation may be preferred when the graph is dense.
The adjacency-list representation of a graph G consists of an array of linked lists, one for each vertices. Each such list contains all vertices adjacent to a chosen one. Here is an adjacency-list representation:
Vertices in an adjacency list are stored in an arbitrary order. A potential disadvantage of the adjacency-list representation is that there is no quicker way to determine if there is an edge between two given vertices. This disadvantage is eliminated by an adjacency-matrix representation.
For the adjacency-matrix representation we assume that the vertices are numbered 0, 1, 2, ..., N-1. The adjacency-matrix representation of a directed graph G = <V, E>  then consists of a |V| x |V|matrix, such that
matrix[i][j] = cost (or binary 1), if there is an edge between i and j
matrix[i][j] = INFINITY  (or binary 0), otherwise
 
Here is the adjacency-matrix for the graph on the first page:





v1
v2
v3
v4
v5
v1
inf
5
inf
inf
inf
v2
inf
inf
inf
inf
6
v3
inf
inf
inf
inf
inf
v4
25
inf
11
inf
19
v5
inf
inf
33
inf
inf

The adjacency-matrix implementation:
It consists of two classes. The matrix class
 
public class Matrix
{
   private Double [][] M;
   protected final static Double INFINITY = Double.MAX_VALUE;
 
   public Matrix(int n)
   {
      M = new Double[n][n];
      for (int i = 0; i < n; i++)
        for (int j = 0; j < n ; j++)
           M[i][j] = INFINITY;
   }
 
   //methods: get, set, toString
}
and the Graph class
 
public class Graph extends Matrix
{
   private int numEdges;
   private int numVertices;
 
   public Graph(int n)
   {
      super(n);
      numEdges = 0;
      numVertices = n;
   }
 
   //methods: addEdge, removeEdge, ...
}
 
Exercise 1.
Implement the method inDegree, which computes the in-degree of a given vertex.
Exercise 2.
Implement the method removeEdge, which removes an edge from a graph.
Exercise 3.
How many graphs are there which have n vertices? Don't count graphs with vertices connected to themselves.
Comparison of both representations:
                         Adjacency List                     Adjacency Matrix
                        sparse |E| << |V|^2               dense  |E| ~ |V|^2          
  Space              O(|V| + |E|)                                O(|V|^2)          
Edge access           O(|V|)                                       O(1)     


Reference
                                                                          

No comments :

Post a Comment

Subscribe to: Post Comments ( Atom )