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
What is a spanning tree?
A subgraph which includes all the vertices of G and is also a tree
What is a complete graph?
Every vertex is directly connected to every other one
What is an isomorphic graph?
Graphs showing the same information but are drawn differently
What is the handshaking lemma?
In an undirected graph, the sum of the degrees of the vertices is equal to double the number of edges. This means the number of odd vertices must be even
Eularian cycle
All nodes are even
Semi-Eularian cycle
2 odd nodes
