Graph Basics
Shown as a dot on a graph
What is a vertex?
A graph where every vertex is connected to every other vertex, directly or indirectly
What is a connected graph?
v + f = e + 2
What is Euler's Formula?
A sequence of edges linking successive vertices
What is a walk?
A graph in which the weights are physical quantities (ie. distance, time, cost)
What is a Network?
Line that joins two dots
What is a edge?
An edge in a graph that if removed leaves the graph disconnected
What is a bridge?
A trail that follows every edge of a graph with no repeated edges
What is an Eulerian Trail?
A walk with no repeated edges
What is a trail?
A connected graph that contains no cycles, multiple edges or loops
What is a Tree?
What is a loop?
What are isomorphic graphs?
An Eulerian Trail that starts and finishes at the same vertex
What is an Eulerian Circuit?
A walk with no repeat edges and no repeated vertices
What is a path?
A way of determining the shortest path between two points in network
What is Dikstra's algorithm?
The number of edges attached to the vertex
What is the degree of a vertex?
A square matrix that recodes the number of edges connecting edge pair of vertices
What is an adjacency matrix?
A path that visits every vertex of a graph with no repeated vertices
What is a Hamiltonian Path?
A walk that starts and ends at the same vertex and has no repeated edges
What is a circuit?
A way of assigning jobs to people so the jobs are completed in the shortest amount of time
What is a Hungarian algorithm?
The number of vertices is equal to twice the number of edges
What is the sum of degrees?
A graph where no edges intersect or overlap
What is a Planar Graph?
A series of rules for determining a minimum spanning tree for a graph
A walk that starts and ends at the same vertex and has no repeated vertices or edges
What is a cycle?
Connecting all vertices in a network in the shortest way
What is a minimum spanning tree?