FINAL EXAM Flashcards
vertex
anything
edge
undirected pair of vertices
adjacent
two vertices connected by an edge
incident
edge touches vertices
directed edge
ordered pair of vertices
directed graph
a graph with directed edges
digraph
short for directed graph
degree
of edges to a vertex
in-degree
of edges coming in
out-degree
of edges going out
path
sequence of vertices such that every consecutive pair is adjacent
simple path
no repeated vertices or edges
cycle
a path that begins and ends at the same vertex
simple cycle
no repeated vertices except 1st and last
minimum number of vertices for a simple cycle
3
connected
a path between every vertex
euler path/circuit
traverse all of the edges only once
hamilton path/circuit
traverse all of the vertices only once
tree
an acyclic connected graph
an undirected graph is a tree IFF
there is a unique simple path between any two of its vertices
Variance
How close The elements in the sample space are to the expected value
