GRAPH ALGORITHMS Essay

Submitted By pratyushas
Words: 794
Pages: 4

Pratyusha Sampathirao
11/19/2014

Agenda








Graph
Graph Theory
Categories
Applications
Graph Properties and Measurements
References

Graph


 A graph is a representation of a set of objects where some pairs of objects are connected by links.
 The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges.
 Set of dots : Vertices(Nodes or points)
 Joining lines or curves : Edges(Arcs or lines)
 A graph is a set of objects called points or vertices connected by links called lines or edges

Definition: Graph

 G is an ordered triple G:=(V, E, f)
 V is a set of nodes, points, or vertices.
 E is a set, whose elements are known as edges or lines.
 f is a function
 maps each element of E
 to an unordered pair of vertices in V.

Definitions

 Vertex
 Basic Element
 Drawn as a node or a dot.
 Vertex set of G is usually denoted by V(G), or V
 Edge
 A set of two elements
 Drawn as a line connecting two vertices, called end vertices, or endpoints.
 The edge set of G is usually denoted by E(G), or E.

Example


 V:={1,2,3,4,5,6}
 E:={{1,2},{1,5},{2,3},{2,5},{3,4},{4,5},{4,6}}

Loop, Multiple edges 
 Loop : An edge whose endpoints are equal
 Multiple edges : Edges have the same pair of endpoints
Multiple
edges

loop

7



Adjacent, neighbors 
Two vertices are adjacent and are neighbors if they are the endpoints of an edge  Example:
 A and B are adjacent
 A and D are not adjacent

8

Properties

 Undirected
 Simple
 Graph represents a road network, the weights could represent the length of each road

Categories

 Directed Graph:
 The edges have a direction associated with them

 Undirected Graph:
 The edges have a direction associated with them

Categories

Mixed Graph:
Some edges may be directed and some may be undirected
Simple Graph:
An undirected graph without loop or multiple edges

Special Types of
Graphs



 Empty Graph / Edgeless graph
 No edge

 Null graph
 No nodes
 Obviously no edge

Weighted graphs


 It is a graph for which each edge has an associated weight, usually given by a weight function w: E  R.

Connectivity



A graph is connected if
 you can get from any node to any other by following a sequence of edges OR
 any two nodes are connected by a path.

 A directed graph is strongly connected if there is a directed path from any node to any other node.

Topological
Distance

A shortest path is the minimum path connecting two nodes.
The number of edges in the shortest path connecting p and q is the topological distance between these two nodes, dp,q

Graph-based
Representations



Representing a problem as a graph can provide a different point of view
Representing a problem as a graph can make a problem much simpler
 More accurately, it can provide the appropriate tools for solving the problem Graph-like problems 






There are two components to a graph
 Nodes and edges
In graph-like problems, these components have natural correspondences to problem elements
 Entities are nodes and interactions between entities are edges
Most complex systems are graph-like

Graph Theory

 Study of Graphs
 Concerns the relationship among lines and points
 Deals with






Connection problems
Scheduling problems
Transportation problems
Network analysis
Games and Puzzles

Transportation problems 

Tree and Spanning
Tree

 Tree:
 A…