Famous Problems on Graphs:
- Binary Search Trees. Place data in a binary search tree.
(Known solution on a computer. Used for TreeMap and TreeSet class in Java)
- Be able to place numbers inside a binary search tree.
- What is the approximate height of a balanced binary tree.
- Know what a tree is a connected graph with no cycles.
- Rooted tree: know terms - root, leaf, child, ancestor, descendant.
- Know that a tree with n vertices has n-1 edges.
- Minimum Spanning Tree problem - find a subgraph of the graph that
is a tree and has a minimum cost for the edges.
- Know special kinds of graphs: clique, cycle, path, bipartite graphs,
planar graphs, regular graphs
- Find the largest clique, cycle, path - in a graph. (Unknown)
- Know the notation for paths, cycles, cliques = complete graphs,
complete bipartite graphs.
- Eulerian Graphs - There exists a circuit that uses all edges in the
graph exactly once, beginning and ending in the same vertex.
(easy to tell)
- Graph Coloring - color the vertices of a graph with the fewest
number of colors (original problem was coloring a map)
- All planar graphs can be 4-colored. Not all planar graphs
are 3-colorable. Find an efficient algorithm to determine if
a planar graph is 3-colorable (no known efficient algorithm).
- Hamiltonian Cycle - does a graph have a cycle through all the
vertices? (no known efficient algorithm)
- Traveling Salesman - find a minimum weight cycle through all the
vertices in a complete weighted graph. (no known efficient algorithm)
- Find a largest independent set in a graph. (no known
efficient algorithm).
- Graph Isomorphism: Given two graphs, can you rename the vertices
in the second graph such that the two graphs have the same set of
vertices and the same set of edges. (no known efficient algorithm,
but may not be as hard as some of these other ones).
- Drawing a graph with the fewest number of edges crossing.
- Know the relationship between the sum of the degrees in the
graph and the number of edges in the graph.