Decision maths - graphs and networks Flashcards
What is a graph?
Points (vertices or nodes) which are connected by lines (arcs or edges)
What is a weighted graph/network?
When a graph has a number associated with each edge
What is a vertex/node?
A point on a graph
What is an edge/arc?
A line segment joining vertices
What is a subgraph of G?
A graph, each of whose vertices and edges belong to G. It is part of the original graph
What is the degree or valency of a vertex?
The number of edges entering/leaving it
What is a walk?
A route along edges from one vertex to the next
What is a path?
A walk in which no vertices are visited more than once
What is a trail?
A walk in which no edge is visited more than once
What is a cycle?
A walk where the end vertex is the same as the start vertex
What is a Hamiltonian cycle?
A cycle that includes every vertex
When is a graph connected?
When all its vertices are connected
What is a loop?
An edge that starts and finishes at the same vertex
What is a directed graph?
One where the edges of a graph have direction associated to them
What is a tree?
A connected graph with no cycles
