Discrete Test 3

0.0(0)
Studied by 0 people
call kaiCall Kai
learnLearn
examPractice Test
spaced repetitionSpaced Repetition
heart puzzleMatch
flashcardsFlashcards
GameKnowt Play
Card Sorting

1/101

encourage image

There's no tags or description

Looks like no tags are added yet.

102 Terms

1
New cards
What makes f: X → Y a function?
Every x ∈ X maps to exactly one y ∈ Y
2
New cards
What is the target of f: X → Y?
The set Y (also called the codomain)
3
New cards
What is the range of f: X → Y?
{y ∈ Y : f(x) = y for some x ∈ X}, a subset of the target
4
New cards
When is a function not well defined?
When it maps an element of the domain to zero elements or more than one element of the target
5
New cards
When are two functions equal?
Same domain, same target, and f(x) = g(x) for every x in the domain
6
New cards
What is ⌊x⌋?
The largest integer y with y ≤ x (round down, so ⌊−3.7⌋ = −4)
7
New cards
What is ⌈x⌉?
The smallest integer y with y ≥ x (round up, so ⌈−3.7⌉ = −3)
8
New cards
When is f one to one (injective)?
x₁ ≠ x₂ implies f(x₁) ≠ f(x₂)
9
New cards
When is f onto (surjective)?
Range = target: every y ∈ Y has an x with f(x) = y
10
New cards
What is a bijection?
A function that is both one to one and onto (a one to one correspondence)
11
New cards
When does a function have an inverse?
If and only if it is a bijection
12
New cards
What is f⁻¹(y)?
f⁻¹(y) = x if and only if f(x) = y
13
New cards
What is the definition of log_b x?
log_b x = y ⇔ bʸ = x (b > 0, b ≠ 1)
14
New cards
How many steps does it take to replace n with ⌊n/b⌋ until n < b?
⌊log_b n⌋ steps
15
New cards
How many steps does it take to replace n with ⌈n/b⌉ until n = 1?
⌈log_b n⌉ steps
16
New cards
When do sets A and B have the same cardinality?
When there is a bijection from A to B
17
New cards
When is a set countably infinite?
When there is a bijection from ℤ⁺ to it
18
New cards
What does countable mean?
Finite or countably infinite
19
New cards
What is an uncountable set?
A set that is not countable, e.g. (0,1) or ℝ
20
New cards
What proof technique shows (0,1) is uncountable?
Cantor diagonalization: assume a complete list exists, then build a number whose ith digit differs from the ith digit of the ith number
21
New cards
If A ⊆ B and B is countable, what do you know about A?
A is countable
22
New cards
If A ⊆ B and A is uncountable, what do you know about B?
B is uncountable
23
New cards
What is a binary relation from A to B?
A subset of A × B; (a,b) ∈ R is written aRb
24
New cards
In the matrix of a relation, what does a 1 in row i, column j mean?
aᵢ R bⱼ
25
New cards
When is a relation R reflexive?
xRx for every x
26
New cards
When is a relation R antireflexive?
xRx for no x
27
New cards
When is a relation R symmetric?
xRy implies yRx
28
New cards
When is a relation R antisymmetric?
xRy and yRx together imply x = y
29
New cards
When is a relation R transitive?
xRy and yRz imply xRz
30
New cards
Can a relation be neither reflexive nor antireflexive?
Yes, if some elements are related to themselves and some are not
31
New cards
What are the in degree and out degree of a vertex in a digraph?
In degree: the number of edges pointing into it. Out degree: the number of edges pointing out of it
32
New cards
What is a self loop?
An edge from a vertex to itself
33
New cards
What is a partial order?
A relation that is reflexive, antisymmetric, and transitive
34
New cards
What is a poset?
A set with a partial order on it, written (A, ⪯)
35
New cards
When are two elements of a poset comparable?
When x ⪯ y or y ⪯ x
36
New cards
What is a total order?
A partial order in which every two elements are comparable
37
New cards
What is a minimal element of a poset?
An element x such that there is no y ≠ x with y ⪯ x
38
New cards
What is a maximal element of a poset?
An element x such that there is no y ≠ x with x ⪯ y
39
New cards
What is left out of an upward (Hasse) diagram?
Self loops, edges implied by transitivity, and arrowheads (smaller elements are drawn lower)
40
New cards
What is an equivalence relation?
A relation that is reflexive, symmetric, and transitive
41
New cards
What is the equivalence class [a]?
The set of all x with a ~ x
42
New cards
What do the distinct equivalence classes of a set form?
A partition: nonempty, pairwise disjoint subsets whose union is the whole set
43
New cards
What is an n ary relation?
A subset of A₁ × A₂ × … × Aₙ (a set of n tuples)
44
New cards
What is a key in a database?
An attribute or set of attributes that uniquely identifies each n tuple
45
New cards
What does the selection operation do?
Keeps the n tuples (rows) that satisfy given conditions
46
New cards
What does the projection operation do?
Keeps only the listed attributes (columns), then removes duplicate tuples
47
New cards
What is a simple graph?
A graph with no parallel edges and no self loops
48
New cards
What is the degree of a vertex?
The number of neighbors it has (the number of edges incident to it)
49
New cards
What does the Handshake Theorem say?
Σ deg(v) = 2|E|, so every graph has an even number of odd degree vertices
50
New cards
What is a d regular graph?
A graph in which every vertex has degree d
51
New cards
How many edges does Kₙ have?
n(n − 1)/2, since every pair of vertices is adjacent
52
New cards
What is Qₙ, and how many vertices and edges does it have?
Vertices are n bit strings, adjacent if they differ in exactly one bit; 2ⁿ vertices and n·2ⁿ⁻¹ edges
53
New cards
What is K_m,n?
Two sets of m and n vertices, with an edge between every vertex in one set and every vertex in the other, and no edges within a set
54
New cards
When are two graphs isomorphic?
There is a bijection f: V → V′ with {x,y} ∈ E if and only if {f(x),f(y)} ∈ E′
55
New cards
What properties are preserved under isomorphism?
Number of vertices, number of edges, degree sequence, cycles of each length, connectedness
56
New cards
What is a degree sequence?
The list of all vertex degrees in nonincreasing order
57
New cards
What is a walk?
A sequence of vertices in which each consecutive pair is joined by an edge; its length is the number of edges
58
New cards
What is the difference between an open walk and a closed walk?
Open: the first and last vertices differ. Closed: the first and last vertices are the same
59
New cards
What is a trail?
A walk with no repeated edge
60
New cards
What is a path?
A walk with no repeated vertex
61
New cards
What is a circuit?
A closed trail (a closed walk with no repeated edge)
62
New cards
What is a cycle in an undirected graph?
A circuit of length at least 3 with no repeated vertex except first = last
63
New cards
What is a cycle in a directed graph?
A circuit of length at least 1 with no repeated vertex except first = last (a self loop counts)
64
New cards
When is a graph connected?
When every pair of vertices is joined by a path
65
New cards
What is a connected component?
A maximal set of connected vertices and all the edges between them
66
New cards
What is the vertex connectivity κ(G)?
The minimum number of vertices whose removal disconnects G (the largest k for which G is k vertex connected)
67
New cards
What is the edge connectivity λ(G)?
The minimum number of edges whose removal disconnects G (the largest k for which G is k edge connected)
68
New cards
What is the upper bound on κ(G) and λ(G)?
κ(G) ≤ δ(G) and λ(G) ≤ δ(G), where δ(G) is the minimum degree
69
New cards
What is an Euler circuit?
A circuit that uses every edge exactly once
70
New cards
What is an Euler trail?
An open trail that uses every edge exactly once
71
New cards
When does a graph have an Euler circuit?
If and only if it is connected and every vertex has even degree
72
New cards
When does a graph have an Euler trail?
If and only if it is connected and has exactly two vertices of odd degree (the trail starts at one and ends at the other)
73
New cards
What is a Hamiltonian cycle?
A cycle that includes every vertex exactly once
74
New cards
What is a Hamiltonian path?
A path that includes every vertex exactly once
75
New cards
How do you show a graph has no Hamiltonian cycle?
There is no degree test; use structure, e.g. a degree 1 vertex, or a vertex whose removal disconnects the graph
76
New cards
What is a planar graph?
A graph that has an embedding in the plane with no edges crossing
77
New cards
What is the degree of a region?
The length of the walk around its boundary (an edge sticking into the region counts twice)
78
New cards
What is Euler's Identity for planar graphs?
n − m + r = 2 for a connected planar graph (vertices − edges + regions)
79
New cards
What edge bound holds for a connected planar graph with n ≥ 3?
m ≤ 3n − 6, so m > 3n − 6 means the graph is not planar
80
New cards
What does Kuratowski's Theorem say?
G is planar if and only if it has no subgraph that is a subdivision of K₅ or K₃,₃
81
New cards
What is a graph minor?
A graph obtained by deleting vertices and edges and contracting edges
82
New cards
What is a valid coloring?
A coloring in which adjacent vertices always have different colors
83
New cards
What is the chromatic number χ(G)?
The smallest k such that G has a valid k coloring
84
New cards
What is the clique number ω(G)?
The largest k such that Kₖ is a subgraph of G
85
New cards
What bounds hold on χ(G)?
ω(G) ≤ χ(G) ≤ Δ(G) + 1, where Δ(G) is the maximum degree
86
New cards
How does greedy coloring work?
Go through the vertices in order and give each one the lowest numbered color not used by its already colored neighbors
87
New cards
What is a tree?
A connected graph with no cycles
88
New cards
How many edges does a tree with n vertices have?
n − 1
89
New cards
How many paths are there between two vertices of a tree?
Exactly one
90
New cards
What is the level of a vertex in a rooted tree?
Its distance from the root (the root is level 0)
91
New cards
What is the height of a rooted tree?
The highest level of any vertex
92
New cards
What is a leaf in a rooted tree?
A vertex with no children
93
New cards
What is the subtree rooted at v?
v together with all of v's descendants
94
New cards
What is a preorder traversal?
Each vertex is visited before its descendants (the root is first)
95
New cards
What is a postorder traversal?
Each vertex is visited after its descendants (the root is last)
96
New cards
What is a spanning tree?
A subgraph of a connected graph G that contains every vertex of G and is a tree
97
New cards
How does depth first search (DFS) build a spanning tree?
It goes as deep as possible and backtracks only when stuck, checking neighbors in alphabetical order
98
New cards
How does breadth first search (BFS) build a spanning tree?
It explores by distance from the start vertex: first its neighbors, then neighbors of neighbors
99
New cards
What is a weighted graph?
A graph with a function w: E → ℝ that assigns a weight to each edge
100
New cards
What is a minimum spanning tree (MST)?
A spanning tree whose weight is no larger than that of any other spanning tree