MATH 225N WEEK 4 LEARNING WORKBOOK
2026 ALGEBRAIC EXPRESSIONS AND
FUNCTIONS
◉ Euler Path.
Answer: covers each edge exactly once, but may not end at starting
vertex
◉ How to tell if a graph has an euler path?.
Answer: If 2 or fewer vertices have odd valences and the graph is
connected
(odd vertices begin and end path)
◉ Postman Problem.
Answer: add edges until every valence is even
◉ hamiltonian circuit.
Answer: use every vertex exactly once (skip some edges)
returns to where it started
◉ complete graph.
, Answer: A graph in which every vertex is directly connected by an
edge to each of the other vertices.
◉ Nearest Neighbor Algorithm.
Answer: 1. pick any starting vertex
2.move to an adjacent vertex along the best allowable edge (has not
been used; does not block you from completing the hamiltonian
circuit)
3. continue until you have visited each vertex exactly once and have
returned to the starting vertex
◉ sorted edges algorithm.
Answer: 1. Arrange edges of the complete graph in order of
increasing cost
2. Select the lowest cost edge that has not already been selected that
a. Does not cause a vertex to have 3 edges
b. Does not close the circuit unless all vertices have been included
◉ Spanning tree.
Answer: A subgraph of a graph which includes all the vertices of the
graph and is also a tree.
no circuits
touches all vertices
2026 ALGEBRAIC EXPRESSIONS AND
FUNCTIONS
◉ Euler Path.
Answer: covers each edge exactly once, but may not end at starting
vertex
◉ How to tell if a graph has an euler path?.
Answer: If 2 or fewer vertices have odd valences and the graph is
connected
(odd vertices begin and end path)
◉ Postman Problem.
Answer: add edges until every valence is even
◉ hamiltonian circuit.
Answer: use every vertex exactly once (skip some edges)
returns to where it started
◉ complete graph.
, Answer: A graph in which every vertex is directly connected by an
edge to each of the other vertices.
◉ Nearest Neighbor Algorithm.
Answer: 1. pick any starting vertex
2.move to an adjacent vertex along the best allowable edge (has not
been used; does not block you from completing the hamiltonian
circuit)
3. continue until you have visited each vertex exactly once and have
returned to the starting vertex
◉ sorted edges algorithm.
Answer: 1. Arrange edges of the complete graph in order of
increasing cost
2. Select the lowest cost edge that has not already been selected that
a. Does not cause a vertex to have 3 edges
b. Does not close the circuit unless all vertices have been included
◉ Spanning tree.
Answer: A subgraph of a graph which includes all the vertices of the
graph and is also a tree.
no circuits
touches all vertices
