FINAL EXAM Flashcards
(21 cards)
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
