Graph Theory Definitions Flashcards
Network
a graph with weights along each edge, number may refer to time, distance or money.
Order/Degree of a vertex
number of edges it’s attached to, a loop counts as 2
Odd vertex
a vertex with an odd order/degree
loop
edge with the same vertex at each end
if a graph has n edges, what’s the sum of it’s order?
2n
Complete Graph
every vertex is connected by an edge to all other vertices
Simple Graph
no loops, one edge connects to any pair of vertices
When would a complete graph have n odd vertices?
when it’s Eulerian
Digraph/directed graph
a graph that has at least one edge with a direction
Cycle
a route starting and finishing at the same vertex
Hamiltonian Cycle
a cycle that visits every vertex once (not every edge) and returns to the start vertex
What is the connection between a Hamiltonian cycle and the number of edges?
They are the same, no. of edges = no. vertices
How many different Hamiltonian cycles are associated with a fully connected graph?
(n-1)!/2 where n = number of vertices and (n-1)! is the number of possible cycles
Eulerian Graph
A connected graph with with all even orders
Eulerian Cycle
visits every edge once and all vertices are of an even order
