Decision maths Flashcards
Graphs
Consists of vertices/nodes which are connected by lines/edges
Subgraph
A graph whose vertices belongs to a greater graph and whose edges also belong to that same graph
Weighted Graph or network
A number/weight associated with each weight
Degree/valency
The number of edges incident to it
What must be tue if a vertex is odd?
It must have an odd degree
Path
A walk in which no vertex is visited no more than once
What must be true if a graph is connected?
If all of its vertices are connected
Digraph
If the edges of a graph have a direction associated with them
A tree
A connected graph with no cycles
Spanning tree
A subgraph which includes all the vertices of the original graph and is also a tree
Minimum Spanning Tree
A MST is a spanning tree such that the total length of its arcs is as small as possible
Complete graph
A graph in which each of the n vertices is connected to every other vertex
Hamiltonian cycle
A cycle which includes every vertex
Walk
A route through a graph along edges from one vertex to the next
Trail
A walk in which no edge is visited more than once
