-
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 in-degree and out-degree
- In-degree: Number of edges pointing to a node
- Out-degree: Number of edges pointing from a node
Basic Terminology of Graphs
Graph - Non-Linear Data Structures, Power Booster, Smart Tools For Best Engineer, Developer Must Know Things, Basic terminology of graphs
642
2/7/2017 6:15:55 AM
Reference :
- http://www.radford.edu/~nokie/classes/360/graphs-terms.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/basic-terminology-of-graphs