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