Unit 4 Quiz Flashcards
Graph
set of vertices and set of edges that relate to the vertices
Path
how to get from one point to another
Weighted Graph
Graph with “cost” associated with the travel from one vertex to another
Directed Graph
Also called Digraph; a graph where each vertex has a one-way relationship represented with arrows
Cyclic Graph
a graph that contains at least one cycle in it, meaning you can travel back to a vertex.
“All roads lead home”
Acyclic Graph
no cycles allowed
Biconnected Graph
Graph with no articulation points ( vertices whose removal disconnects the graph )
Topological Sort
Printing of vertices ( nodes ) from graph so that if there is a path from Vi to Vj, then Vj appears after Vi. In other words, no prerequisites are violated.
Topological sort has __________ and does not need to be _________
multiple answers ; truly sorted
Trees are always ________
Acyclic
All trees are _______
graphs
Multilist
linked list of linked lists
adjacency list
1d array of pointers to whoever we connect to
Min spanning tree
Tree with minimum number of paths to connect
When does dijkstras fail?
when there is a negative weight
Dijkstras is a ______
connected graph
dijkstras runtime
O ( E log V ) B, A, W
E = # edges
V = # vertices
Topological Sort runtime
O ( E + V )
E = # edges
V = # vertices
Depth and breadth first search runtime
O ( E + V )
E = # edges
V = # vertices
Breadth first search
setup identical to DFS, but use a queue
Prints row by row left to right
Depth first search
basically a preorder traversal in disguise
1) push start vertex onto stack
2) pop stack, output top vertex, mark it, push all adj non marked vertices.
Euler circuit
Identical to Hamiltonian circuit, except we want to visit every edge once
- if every vertex has an even degree => euler circuit
Circuit
special type of cycle on a connected, undirected graph
Hamiltonian Circuit
circuit with a path that visits every vertex exactly once and returns to the starting point
Upper bound
the best weve been able to do so far
Lower bound
The best we can hope to do that is theoretically possible
Is there a solution to the Euler bridge problem? why?
No because you have to get off the island.
example of NP complete problem
travelling salesman problem , four color problem
tractable problems
upper and lower bounds are polynomials
NP complete problems
upper bound suggests intractable, but lower bound suggests tractable
Intractable problems
upper and lower bounds are non-polynomial
Undecidable problems
“impossible” to solve
What is the halting problem?
trying to figure out if the program is going to run forever or not
