CHP 2: Graphs and Networks - Key Terminology Flashcards
Definition of GRAPH
A graph consists of points (called vertices or nodes) which are connected by lines (edges or arcs).
Definition of WEIGHTED GRAPH
When a graph has a number associated with each edge (usually called its weight).
Also called weighted network.
Definition of SUBGRAPH
A graph, each of whose vertices belongs to the original graph and each of whose edges belongs to the original graph. (Part of the original graph)
What is a list of vertices often called?
Vertex Set
What is a list of edges often called?
Edge Set
Definition of DEGREE
Number of edges incident to a vertex. If even it is called an even degree and vice versa for odd.
Definition of VALENCY
Number of edges incident to a vertex. If even it is called an even degree and vice versa for odd.
Definition of ORDER OF A VERTEX
Number of edges incident to a vertex. If even it is called an even degree and vice versa for odd.
Definition of WALK
A walk is a route through a graph along edges from one vertex to the next.
Definition of PATH
A path is a walk in which no vertex is visited more than once.
Definition of CYCLE
A walk in which the end vertex is the same as the start vertex and no other vertex is visited more than once.
Definition of HAMILTONIAN CYCLE
A cycle that includes every vertex.
Definition of CONNECTED GRAPH
When all vertices are connected by paths.
Definition of LOOP
A loop is an edge that starts and finishes at the same vertex.
Definition of SIMPLE GRAPH
A graph in which there are no loops and there is at most one edge connecting any pair of vertices.