Math 405: Review For Exam 1
- Be familiar with terminology:
- vertex, edge, multiple edge, loop, degree of a vertex, circuit, path, bridge,
Hamilton circuit, Euler circuit, Eulerization, semi-Eulerization, traveling salesman problem,
routing problem, complete graph, weighted graph, minimum network problem, spanning
subgraph, tree, minimum spanning tree, Steiner point, project digraph, indegree and outdegree,
priority list, critical times and paths, independence of tasks
- Be able to explain why certain graph facts are true:
- A graph with an odd degree vertex has no Euler circuit.
- A graph with more than two vertices of odd degree vertex has no Euler path.
- A graph that is not connected has no Hamiltonian circuit and no Euler path.
- The sum of the degrees in a graph equals twice the number of edges.
- The number of vertices of odd degree is always even.
- Be able to use important theorems:
- Euler's theorem characterizing which graphs have Euler circuits or paths
- The theorems characetrizing which graphs are trees.
- Know the names of the various algorithms, and what they do, and
comparative advantages or disadvantages
they offer when there is more than one for the same problem:
- Brute Force
- Cheapest link
- Nearest neighbor
- Repetitive nearest neighbor
- backflow algorithm
- decreasing time algorithm
- critical path algorithm
- Be able to:
- Produce an appropriate graph model, given a routing problem.
- Tell when Euler circuits or paths exist, and find them if they do.
- Produce an Eulerization or semi-Eulerization and discuss optimality.
- Find a shortest network for the three vertices of a triangle.
- Determine an upper bound on
how many Steiner points might be needed to produce a shortest network.
- Produce a project digraph, priority list and project schedule, and discuss
- Do problems like those assigned on the homework.