
Define a Graph:
 G = (V, E) by defining a pair of sets:
 V = a set of vertices
 E = a set of edges
 G = (V, E) by defining a pair of sets:

Edges:
 Each edge is defined by a pair of vertices
 An edge connects the vertices that define it
 In some cases, the vertices can be the same

Vertices:
 Vertices also called nodes
 Denote vertices with labels

Representation:
 Represent vertices with circles, perhaps containing a label
 Represent edges with lines between circles

Example:
 V = {A,B,C,D}
 E = {(A,B),(A,C),(A,D),(B,D),(C,D)}

Path:
 sequence of vertices in which each pair of successive vertices is connected by an edge

Cycle:
 a path that starts and ends on the same vertex

Simple path:
 a path that does not cross itself
 That is, no vertex is repeated (except first and last)
 Simple paths cannot contain cycles
 a path that does not cross itself

The length of a path:
 Number of edges in the path
 Sometimes the sum of the weights of the edges
 Number of edges in the path

The degree of a Node:
 The degree of a node is the number of edges the node is used to define
 In the example above:
 Degree 2: B and C
 Degree 3: A and D
 A and D have odd degree, and B and C have even degree
 Can also define indegree and outdegree
 Indegree: Number of edges pointing to a node
 Outdegree: Number of edges pointing from a node
Basic Terminology of Graphs
Graph  NonLinear Data Structures, Power Booster, Smart Tools For Best Engineer, Developer Must Know Things, Basic terminology of graphs
477
2/7/2017 6:15:55 AM
Reference :
 http://www.radford.edu/~nokie/classes/360/graphsterms.html
 http://www.csl.mtu.edu/cs2321/www/newLectures/24_Graph_Terminology.html
 https://courses.cs.washington.edu/courses/cse373/06sp/handouts/lecture20.pdf
http://thingswelearned.com/article/show/basicterminologyofgraphs