false

Class Notes
(838,239)

Canada
(510,787)

University of Toronto Scarborough
(31,563)

Computer Science
(312)

CSCA67H3
(56)

Richard Pancer
(3)

Lecture

Unlock Document

Computer Science

CSCA67H3

Richard Pancer

Fall

Description

Cliques in Graphs
Deﬁnition. A clique in a graph is a set S of vertices such that ev-
ery pair of vertices in S are adjacent. If the clique has n vertices,
it is denoted by Kn.
K5
Finding maximal sized cliques in large graphs is a challenging
problem in data mining, i.e., analyzing data clustering.
Maximal clique detection arises in bioinformatics, analysis of so-
cial networking patterns, web page clustering etc.
Cliques and 3-SAT
Recall 3-SAT:
Given a set of clauses C = fC ;C1;::2;C g eakh of size
3, over a set of variables X = fx 1x 2:::;x gn does there
exist a truth assignment that satisﬁes C?
1 3-SAT and Cliques
Suppose we have a 3-SAT formula:
F : (a OR b OR d) AND (b OR !c OR d) AND (!a OR c OR !d) AND (a OR !b OR !c)
Consider the following algorithm to construct a graph from F:
1. Create a vertex for each literal in the formula. Use the literal
to label the vertex.
2. Group the vertices corresponding to a clause together.
3. Connect two vertices in the graph if they are:
▯ In different clauses
▯ and are not a negation of each other.
Example
a b d
b a
!c !b
d !c
!a c !d
2 3-SAT and Cliques
Q. If there is a clique in our graph equal to the number of clauses
in F (so 4), what does this tell us about F?
A.
a b d
b a
!c !b
d !c
!a c !d
F : (a OR b OR d) AND (b OR !c OR d) AND (!a OR c OR !d) AND (a OR !b OR !c)
Q. Notice that there are several possib4e K s in G. What does
this mean?
A.
Q. If there does not exist a clique of size equal to the number of
clauses then what does this tell about F?
A.
3 Clique
Q. Why?
A.
Deﬁnition. The problem known as Clique is the following:
Given a graph G and a natural number k, does there exist a
clique of size k in G?
Q. What have we shown about Clique and 3-SAT?
A.
Q. Why?
A.
This technique of showing that one problem is as hard as another
is called a reduction.
4 Proof By Induction
Proof by Induction is a very powerful tool when used correctly.
Visual: The Domino Argument
Think of a row of dominos.
If set up properly, when the i th
st
domino falls, so too will the i + 1
domino for all values of i.
Therefore, when the ﬁrst domino
is knocked over so too are all the
dominos.
We use it to prove a statement S(n) is true for all natural
numbers n larger than b where b is a natural number.
Note: The natural numbers, denoted N, are the “counting num-
bers” *:
0;1;2;3;:::;i;i + 1;i + 2;:::
*In computer science we usually include 0 in N.
5 Inductive Proof Structure
There are three steps to an inductive proof that:
for aln ▯ b wheren 2 N; S(n ) is true.
1. Base Case: Prove that S(▯) holds for a set B of “smallest”
consecutive values.
2. Inductive Hypothesis: Assume that S(k) holds for all values
of k 2 N such that d < k < n where d is the largest value
in B.
3. Inductive Step: Derive that S(n) is true from the fact that
all values smaller than n make S() true.
Conclusion. For all natural numbers n > b, S(n) holds.
Q. How does each step relate to our domino analogy?
A.
▯
▯
6 Mmmmm....CHOCOLATE!
Suppose we have a chocolate bar
consisting of a number of squares
arranged in a rectangular pattern.
The task is to split the bar into
small squares with a minimum
number of breaks.
Q: How many breaks will it take (assume we only break along
the lines)?
Make an educated guess, and prove it by induction.
Dimensions Breaks
1x1 0
1x2 1
2x2 3
3x2 5
4x3 11
Formula:
l ▯ w chocolate bar needs
7 Proof By Induction
Prove that an l ▯ w chocolate bar needs
Deﬁne S(n): If n ▯ 1 then a chocolate bar with n squares
requires n ▯ 1 breaks.
Prove that 8n 2 N where n ▯ 1;S(n) is true. The symbol 8
means “for all”.
Stay tuned....we will come back to this.
8 Another Example
Prove that 8n 2 N;n(n + 5) is divisible by 6.
Deﬁne P(n):
Let P(n) be
2
9m 2 N;n(n + 5) = 6m
Prove 8n 2 N;P(n) by simple induction.
Base Case. X n = 0. Let m = 0, then 0 = 0 ▯ 6.
Inductive Hypothesis. Let k 2 N. Suppose P(k).
Inductive Step. Prove that if P(k) is true then P(k+1) is true.
2
(k + 1)((k + 1) + 5)
= (k + 1)(k + 2k + 1 + 5)
= (k + 2k + 6) + k(k + 2k + 1 + 5)
2 2 2
= (k + 2k + 6 + 2k + k) + k(k + 5)
= (3k + 3k + 6) + k(k + 5) 2
= 3k(k + 1) + 6 + k(k + 5)2
Notice that the ﬁrst term is divisble by 6 since it is a multiple
of 3 and further either k or (k + 1) is even, or divisible by
2. The second term is divisible by 6 and by the induction
hypothesis, so is the third term.
9 Stamp Example – Simple Induction
Given an unlimited supply of 4-cent and
7-cent stamps, prove that there exists
a combination of stamps to make any
amount of postage that is 18-cents or
more.
Deﬁne P(n), what we are proving:
In English: If n ▯ 18, then postage of exactly n cents can

More
Less
Related notes for CSCA67H3

Join OneClass

Access over 10 million pages of study

documents for 1.3 million courses.

Sign up

Join to view

Continue

Continue
OR

By registering, I agree to the
Terms
and
Privacy Policies

Already have an account?
Log in

Just a few more details

So we can recommend you notes for your school.

Reset Password

Please enter below the email address you registered with and we will send you a link to reset your password.