Term
|
Definition
| 5 vertecies total, including the center. Looks like a square. |
|
|
Term
|
Definition
| Path between two vertices that goes through each vertex once. |
|
|
Term
|
Definition
| Path that starts and ends at the same vertex and goes through each vertex once. |
|
|
Term
|
Definition
| Closed loop where vertices may repeat. Edges cannot repeat |
|
|
Term
|
Definition
| Open (meaning not same endpt) line where vertices cannot repeat. Edges cannot repeat (Open) |
|
|
Term
|
Definition
| Vertices cannot repeat. Edges cannot repeat (Closed loop) |
|
|
Term
|
Definition
| Visits every edge exactly once (can repeat vertices and be open) |
|
|
Term
|
Definition
| Graph that starts and ends at the same point and every edge is visited once only |
|
|
Term
|
Definition
| A subset of a graph where each vertex is adjacent to each other (basically a complete graph inside a graph) |
|
|
Term
|
Definition
| anticlique (a set of vertices in a graph, no two of which are adjacent) |
|
|
Term
|
Definition
Every vertex is adjacent to something in the dominating set (*usually find min dom set)
ex:
A - B - C
B would be min dom set |
|
|
Term
|
Definition
| assignment of colors to vertices so no edge connects two of the same color |
|
|
Term
|
Definition
Set of edges that don't share endpoints (usually found as maximum matching.
[image] |
|
|
Term
|
Definition
vertecies are all joined by edges: ex:
*-*-* is a path graph connecte
*-* * is disconnected |
|
|
Term
|
Definition
Two vertices are called adjacent if they are connected by an edge.
Two edges are called incident, if they share a vertex. |
|
|
Term
|
Definition
| total degree of all the vertices is twice the number of edges |
|
|
Term
|
Definition
|
|
Term
|
Definition
| number of vertices in a maximum clique |
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
f is O(g)
if ∃C > 0 and k ≥ 0 such that |f(n)| ≤ C|g(n)| for all n > k. |
|
|
Term
| big o with limits definition |
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
| Problem with yes or no values |
|
|
Term
|
Definition
| Given a graph G, there is a ____ of size ___. Returns the best possible #. |
|
|
Term
|
Definition
Conjunctive Normal Form
conjunctions of clauses with clauses of disjunctions. In other words, a statement is a series of ORs connected by ANDs. |
|
|
Term
|
Definition
| descision problem where the input is a boolean formula and the output is a YES or NO statement |
|
|
Term
|
Definition
Suppose you have two decision problems, π and π.
Suppose π' ∈ P, and that A is a polynomial time algorithm to solve π'.
F maps Pi to Pi'
YES-instances of π map to YES-instances of π'
NO-instances of π map to NO-instances of π'
The function F takes polynomial time to compute |
|
|
Term
|
Definition
| All clauses have at most X literals |
|
|
Term
|
Definition
| Is the input X-CNF formula satisfiable? |
|
|
Term
| Permutation vs combination |
|
Definition
| Order matters (permutation) vs doesnt (combination) |
|
|
Term
|
Definition
|
|
Term
|
Definition
Non-deterministic Polynomial Time
NP is the set of decision problems for which you can prove YES-instances are YES-instances in polynomial time. |
|
|
Term
|
Definition
|
|
Term
|
Definition
| P is the set of decision problems that can be solved in polynomial time. |
|
|
Term
|
Definition
Does NP contain problems that CANNOT be solved in
polynomial time?
YES -> P != NP
NO -> P = NP
P is a subset of NP regardless |
|
|
Term
| P, NP, NP Complete, NP Hard graph |
|
Definition
|
|
Term
|
Definition
| Given a graph G, here are the vertecies from the set of ______ |
|
|
Term
|
Definition
| statement that is true or false, but not both |
|
|
Term
|
Definition
True if only ONE is true, false if both are T/F
[image] |
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
|
Definition
| compound statement that is always true |
|
|
Term
|
Definition
| statement that is always false |
|
|
Term
|
Definition
| statement that is neither a tautology or contradiction (can be either true or false) |
|
|
Term
|
Definition
(p ∧ q) ≡ ¬p ∨ ¬q
¬(p ∨ q) ≡ ¬p ∧ ¬q |
|
|
Term
| p ∨ (q ∧ r) ≡ (distribute) |
|
Definition
|
|
Term
| satisfiable/unsatisfiable |
|
Definition
satisfiable - can make the compound preposition true (same as tautology)
unsatisfiable - cant make it true. |
|
|
Term
universal quantifier
existential quantifier |
|
Definition
universal quantifier - ∀
existential quantifier - ∃ |
|
|
Term
|
Definition
|
|
Term
|
Definition
| intersection, objects that belong to set A and set B |
|
|
Term
|
Definition
| Union - objects that belong to set A or set B |
|
|
Term
|
Definition
| subset-A is a subset of B. set A is included in set B. |
|
|
Term
|
Definition
|
|
Term
|
Definition
| Same thing as A-B - Objects in A but not in B |
|
|
Term
|
Definition
| Complement - all the objects that do not belong to set A |
|
|
Term
|
Definition
| The sum of degrees of the vertices of a graph is twice the number of edges |
|
|
Term
|
Definition
One-to-One Function
A function for which every element of the range of the function corresponds to exactly one element of the domain.
Ex: passes both vertical line test and horizontal line test |
|
|
Term
|
Definition
Onto function
Every element of b is mapped to an element of a (if f(2) = 3 then there has to be a f(x) = 2) |
|
|
Term
| The notation f : X → Y means |
|
Definition
f is a function from X to Y
You can think of f as an algorithm with input coming from X and output in Y |
|
|
Term
| Prove a closed form by contradiction |
|
Definition
| Find the smallest k, s.t., P(k) is false while P(k-1) is true. Then prove P(k-1)->P(k) |
|
|
Term
|
Definition
| reflexive, anti-symmetric, and transitive |
|
|
Term
|
Definition
| set is a subset of that is not equal to |
|
|
Term
|
Definition
| Every element is related to itself |
|
|
Term
|
Definition
| if a->b (related) then b->a (related) |
|
|
Term
|
Definition
|
|
Term
|
Definition
| symmetric, reflexive, transitive |
|
|
Term
|
Definition
| subset of the functions codomain, which is the output (basically just output) |
|
|
Term
|
Definition
| set of outputs a function can have (range) |
|
|
Term
|
Definition
|
|
Term
|
Definition
|
|
Term
| The empty set is a subset of the reals/naturals (T/F) |
|
Definition
|
|
Term
| Induction - Picking arbitrary N |
|
Definition
| Pick the largest base case. For weak induction, pick N >= 1 |
|
|
Term
| A set is countable if ____ |
|
Definition
| finite or countable infinite. |
|
|
Term
|
Definition
A special case of CNF is where each clause has at most
two literals! That is, expression that are written in the form (A1 ∨ B1) ∧ (A2 ∨
B2) ∧ . . .(Ak ∨ Bk) |
|
|
