CS 173: Skills list for Examlet 4
- Graphs
- Identify real-world applications that can be modeled by graphs.
- Define these terms and know their notation: walk, path, distance, closed walk, merge of two walks, cycle, (a)cyclic, DAG, topological sort.
- Identify examples of the above terms given a concrete graph.
- Given a graph G, construct the related graphs G^n, G^+, G^*.
- Relations
- Know that the edges of a graph are a relation.
- Know which relations can become the edges of a graph.
- Define these terms: reflexive, symmetric, transitive, equivalence relation.
- Prove or disprove that a given relation has the above properties, or similar new properties given their definitions.