Decision Maths Chapter 2 Definitions Flashcards
Graph
A group of points (called vertices or nodes) that are connected by lines (Edges or Arcs).
Weighted Graph
A graph that has a number associated with each edge.
Subgraph
A graph each of whose vertices belongs to G and each of whose edges belongs to G. It is simply a part of the original graph.
Degree/Valency/Order of a vertex
The number of edges incident to it.
Walk
A route through a graph along edges from one vertex to the next.
Path
A walk, in which no vertex is visited more than once.
Trail
A walk in which no edges are visited more than once.
Cycle
A walk, in which the end vertex is the same as the start vertex and no other vertex is visited more than once.
Hamiltonian Cycle
A cycle that includes every vertex.
Connected Graph
A graph where all vertices are connected.
Loop
An edge that starts and finishes at the same vertex.
Simple Graph
A graph in which there are no loops and there is at most one edge connecting any pair of vertices.
Directed Graph
If the edges of a graph have an associated direction.
Euler’s Handshake Lemma
The sum of the degrees of the vertices is equal to 2 x the number of edges.
Tree
A graph with no cycles
