Graph Tutorial

Bipartite Graph

A Graph G is divided into two finite Set U,V such that each vertex of U is connected to each vertex of V in  such a manner where no vertex is adjacent of same, i.e. U set vertex will not connected of any other vertex of U.

In bipartite graph it is necessary that each vertex must be connect with different color otherwise graph is not bipartite

Complete bipartite graph

In regular bipartite graph G(U,V) ,each Vertex U(n) and V(n) connected each other 

A complete bipartite graph is a graph whose vertices can be partitioned into two subsets V1 and V2 such that no edge has both endpoints in the same subset, and every possible edge that could connect vertices in different subsets is part of the graph. That is, it is a bipartite graph (V1, V2, E) such that for every two vertices v1  V1 and v2 V2, v1v2 is an edge in E

Complete Graph

A complete graph is a graph where every vertex is adjacent to every other vertex. A complete graph on n vertices is denoted by Kn (or sometimes by K(n)). So, for example follows is the graph K₅.

Cycles

A cycle is an ordered sequence

a=v0, v1, …, vm=a

of vertices in which each adjacent pair (vj-1,vj) of vertices is linked by an

edge, and v0, v1, …, vm-1 are distinct . The length of the cycle is m

Circuits

A circuit is a path which ends at the vertex it begin (so a loop is a circuit of length one)

Tree

A tree T is a connected graph that has no cycles.

(Simple Tree)

Equivalent definitions of a tree

Let T be a graph with n vertices.

Then the following statements are equivalent.

• T is connected and has no cycles.

• T has n - 1 edges and has no cycles.

• T is connected and has n - 1 edge.

• T is connected and the removal of any edge disconnects T.

• Any two vertices of T are connected by exactly one path.

• T contains no cycles, but the addition of any new edge creates a cycle.

Why are trees a very common data structure in computer science algorithms

And applications?

Which are more commonly used: Trees or Graphs?

Research you answer by finding some key applications of trees and graphs.

Justify any conclusion reached.

Rooted tree

Many applications in Computer Science make use of so-called rooted

Trees, especially binary trees.

Binary Tree Example: Sorting

Create tree via:

First number is the root.

• Put number in tree by traversing to an end vertex

• If number less than or equal vertex number go left branch

• If number greater than vertex number go right branch

• Rooted trees can be used to store data in a computer’s memory in

• many different ways.

• Consider a list of seven numbers 1; 5; 4; 2; 7; 6; 8. The following trees

• show two ways of storing this data, as a binary tree and as a stack.

• Both trees are rooted trees and both representations have their advantages.

• However it is important in both cases to know the starting point of the data,

• i.e. the root.

Trail

A trail is a walk that does not pass over the same edge twice. A trail might visit the same vertex twice, but only if it comes and goes from a different edge each time.

Central Graph

The center of a graph is the set of all vertices of minimum eccentricity that is the set of all vertices A where the greatest distance d(A,B) to the other vertices B is minimal. Equivalently, it is the set of vertices with eccentricity equal to the graph’s radius thus vertices in the center (Central points) minimize the maximal distance from other point.

Eccentricity

Let G be a graph and V be a vertex of G. then eccentricity is maximum length of distance to m from any other vertex.

      E(v) =max{d(v,w),w in v(g)}

Radius 

    Radius is a minimum distance from v to any other vertex of graph G assumes U is a vertex then minimum distance of other vertex which mark in maximum.

Diameter

     Sum of maximum eccentricity

Spanning Tree

A sub graph 􀀀 of a undirected graph   is a spanning tree of _ if it is a tree and   contains every vertex of.

Weighted Graphs:

 A weighted graph is a graph, in which each edge has a weight (some real number).

Weight of a Graph: 

The sum of the weights of all edges.

Minimum Spanning Tree

A Minimum Spanning Tree in an undirected connected weighted graph is a spanning tree of minimum weight (among all spanning trees).

Planar Praphs

A planar graph is a graph which can be drawn in the plane without any

edges crossing. Some pictures of a planar graph might have crossing edges,

but it’s possible to redraw the picture to eliminate the crossings

any planar graph could be colored with only five colors. (Actually, it was an *attempt* to prove that any planar graph could be colored with only four colors, but the proof contained an error; after correcting it, it could only show that you could color a planar graph with no more than 5 colors.) Not only that, but exploiting the properties of a planar graph, you can 5-color a planar graph in *linear* time.

Hamilton Path

A Hamilton path is a directed or undirected graph walk in which each vertex of graph G visited exactly ones.

Eulerian Graph

An Eulerian graph is an eulerian trail in which all vertex are visited with no repeat edges. This path starts and stops on same vertex.

G= (V (G), E (G))

They were first discussed by Leonhard Euler while solving the famous Seven Bridges of Königsberg problem in 1736. Mathematically the problem can be stated like this:

Given the graph in the image, is it possible to construct a path (or a cycle, i.e. a path starting and ending on the same vertex) which visits each edge exactly once?

It is noted in eulerian path that all vertex has even degree.