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) ≤ Cg(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'
YESinstances of π map to YESinstances of π'
NOinstances of π map to NOinstances of π'
The function F takes polynomial time to compute 


Term

Definition
All clauses have at most X literals 


Term

Definition
Is the input XCNF formula satisfiable? 


Term
Permutation vs combination 

Definition
Order matters (permutation) vs doesnt (combination) 


Term

Definition


Term

Definition
Nondeterministic Polynomial Time
NP is the set of decision problems for which you can prove YESinstances are YESinstances 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
subsetA is a subset of B. set A is included in set B. 


Term

Definition


Term

Definition
Same thing as AB  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
OnetoOne 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(k1) is true. Then prove P(k1)>P(k) 


Term

Definition
reflexive, antisymmetric, 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) 

