1/19
Looks like no tags are added yet.
tree
connected graph that contains no cycles
graphs with no cycles → acyclic
leaf
vertex of degree 1 in a tree
forest
a collection of one or more trees
binary decision tree
structure to facilitate searches and sorts and to model the logic of algorithms
bipartite graph
type of graph where vertices can be split into two separate, non overlapping groups, such that every edge connects a vertex in one group to a vertex in the other group
theorem: if a tree is of order n then T has ____ edges
n-1
Theorem: if f is a forest of order n containing k connected components, then F contains __ edges
n - k
a graph of order n is a tree iff __
it is connected and contains n-1 edges
or
it is acyclic and contains n-1 edges
connected
you can get from any vertex to any other vertex by following edges
let T be the tree of order n>=2
then T has at least two leaves
In any tree, the center is
either a single vertex or a pair of adjacent vertices
let T be a tree wit K edges. If G is a fraph whose minimum degree satisfies delta (G) >= k,
then G contains T as a subgraph. alternatively g contains every tree of order at most delta(G) + 1 as a subgraph
handshaking lemma
the sum of all vertex degrees = 2|E|
bridge
an edge that if you remove makes the graph become disconnected
cut vertex
a vertex that disconnects the graph when you remove it
spanning tree
of connected graph G is a subgraph that includes every vertex and is a tree so is connected and has no cycles
weight function
a function W that maps the edges of G to the nonnegative real numbers
weighted graph
the graph G together with a weighted function
minimum weight spanning tree
Given a connected, weighted graph G, the sum of the weights of the edges of T is no more than the sum for any other spanning tree of G
kruskal’s algorithm
Given : A connected , weighted graph G.
i . Find an edge of minimum weight and mark it .
ii . Among all of the unmarked edges that do not form a cycle with any of the marked edges , choose an edge of minimum weight and mark it .
iii . If the set of marked edges forms a spanning tree of G , then stop . If not , repeat step ii .