Graph
A graph can be defined as group of vertices and edges that are used to connect these
vertices. A graph can be seen as a cyclic tree
Definitions: Graph, Vertices, Edges
• Define a graph G = (V, E) by defining a pair of sets:
1. V = a set of vertices
2. E = a set of edges
• Edges:
1. Each edge is defined by a pair of vertices
2. An edge connects the vertices that define it
3. In some cases, the vertices can be the same
• Vertices:
1. Vertices also called nodes
2. Denote vertices with labels
• Representation:
1. Represent vertices with circles, containing a label
2. Represent edges with lines between circles
• Example:
1. V = {A,B,C,D}
2. E = {(A,B),(A,C),(A,D),(B,D),(C,D)}
, Graph Terminology
1. Digraph or Directed graph
2. Undirected graph
3. Mixed graph
4. Weighted graph
5. Path
6. Loop or selfloop
7. Cycle or cyclic graph
8. Acyclic graph
9. Parallel edge
10. Connectec graph
Path
A path can be defined as the sequence of nodes that are followed in order to reach
some terminal node V from the initial node U.
Cycle
A cycle can be defined as the path which has no repeated edges or vertices except the
first and last vertices.
Connected Graph
A connected graph is the one in which some path exists between every two vertices
(u, v) in V. There are no isolated nodes in connected graph.
Weighted Graph
In a weighted graph, each edge is assigned with some data such as length or weight.
The weight of an edge e can be given as w(e) which must be a positive (+) value
indicating the cost of traversing the edge.
Digraph
A digraph is a directed graph in which each edge of the graph is associated with some
direction and the traversing can be done only in the specified direction.
A graph can be defined as group of vertices and edges that are used to connect these
vertices. A graph can be seen as a cyclic tree
Definitions: Graph, Vertices, Edges
• Define a graph G = (V, E) by defining a pair of sets:
1. V = a set of vertices
2. E = a set of edges
• Edges:
1. Each edge is defined by a pair of vertices
2. An edge connects the vertices that define it
3. In some cases, the vertices can be the same
• Vertices:
1. Vertices also called nodes
2. Denote vertices with labels
• Representation:
1. Represent vertices with circles, containing a label
2. Represent edges with lines between circles
• Example:
1. V = {A,B,C,D}
2. E = {(A,B),(A,C),(A,D),(B,D),(C,D)}
, Graph Terminology
1. Digraph or Directed graph
2. Undirected graph
3. Mixed graph
4. Weighted graph
5. Path
6. Loop or selfloop
7. Cycle or cyclic graph
8. Acyclic graph
9. Parallel edge
10. Connectec graph
Path
A path can be defined as the sequence of nodes that are followed in order to reach
some terminal node V from the initial node U.
Cycle
A cycle can be defined as the path which has no repeated edges or vertices except the
first and last vertices.
Connected Graph
A connected graph is the one in which some path exists between every two vertices
(u, v) in V. There are no isolated nodes in connected graph.
Weighted Graph
In a weighted graph, each edge is assigned with some data such as length or weight.
The weight of an edge e can be given as w(e) which must be a positive (+) value
indicating the cost of traversing the edge.
Digraph
A digraph is a directed graph in which each edge of the graph is associated with some
direction and the traversing can be done only in the specified direction.
