math 1060 unit 1 test - UGA fall 2024 FULLY solved & updated

connected For every pair of vertices there is a path from one vertex to another complete For every pair of vertices there is an edge that gets you from one vertex to another Connected graph that is not complete there is a path to every vertex (connected) but vertex Q is not adjacent to vertex R (not complete) Non-connected graph not connected bc there is no path that will allow you to start at C and end at K; bc it's not connected it's also not complete complete graph with N vertices formulas - all vertices will have valence N - 1 - the graph will have 0.5 x N x (N - 1) edges - the graph will have 0.5 x (N - 1)! Unique Hamiltonian circuits graph collection of vertices and edges circuit directed sequence that starts at one vertex, visits some (or all) vertices via edges, then goes back to starting vertex Euler circuit a circuit that uses all the edges of the graph exactly ONCE, starting and stopping at the same vertex; graph "contains" a Euler circuit Euler path a path that uses all edges of the graph exactly once; can start and end at different vertices Euler circuit vs path all Euler circuits are Euler paths, but not all Euler paths are Euler circuits graph has a Euler circuit if - the graph is connected - every vertex has an even valence graph has a Euler path if - the graph is connected - either zero or two vertices with odd valence (which serve as start and end) Euler circuit algorithm DOES NOT EXIST! Euler Circuit Theorem fails... create a eulerized circuit: a circuit that uses every edge AT LEAST once, reuse as few as possible Euler circuits vs eulerized circuits - Euler circuits use all edges exactly once - eulerized circuits use all edges at least once - all connected graphs will have a Euler circuit or eulerized circuit Hamiltonian Circuit a circuit that visits each vertex exactly once; no theory to determine HC; all complete graphs are guaranteed a HC 3 algorithms to find Hamiltonian circuits: - Brute force algorithm - nearest neighbor algorithm - sorted edges algorithm Brute Force Algorithm Time-consuming; only method that guarantees the optimal hamiltonian circuit Nearest Neighbor Algorithm Most time efficient; must have a starting point; does not guarantee the optimal Hamiltonian Circuit Sorted Edges Algorithm Compromise in time; does not guarantee optimal Hamiltonian circuit Hamiltonian circuits vs Euler circuits - a graph can have either, both or neither an ec or Hc - if a graph is not connected, it cannot contain either - all complete graphs will have a Hamiltonian Circuit - only complete graphs with an odd # of vertices will have a HC and an EC