# _w4.pdf

Unlock Document

University of Toronto Scarborough

Computer Science

CSCA67H3

Anna

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.
▯▯
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 = {C ,C1,..2,C k} each of size
3, over a set of variables X = {x 1x ,2..,x n }, 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
▯ ▯ ▯
▯ ▯
▯▯ ▯▯
▯ ▯▯
▯▯ ▯ ▯▯
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.
▯ ▯ ▯
▯ ▯
▯▯ ▯▯
▯ ▯▯
▯▯ ▯ ▯▯
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 ∈ 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 ∈ N such that db , 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 ∀n ∈ N where n ≥ 1,S (n) is true. The symbol ∀
means “for all”.
Stay tuned....we will come back to this.
8 Another Example
Prove that ∀n ∈ N,n(n + 5) is divisible by 6.
Deﬁne P(n):
Let P(n) be
∃m ∈ N,n(n + 5) = 6m
Prove ∀n ∈ N,P (n) by simple induction.
Base Case. ▯ n =0 . Let m =0 , then 0=0 · 6.
Inductive Hypothesis. Let k ∈ N. Suppose P(k).
Inductive Step. Prove that if P(k) is true then P(k+1) is true.
(k + 1)((k + 1) + 5)
=( k + 1)(k +2 k + 1 + 5)
2 2
=( k +2 k + 6) + k(k +2 k + 1 + 5)
=( k +2 k +6+2 k + k)+ k(k + 5) 2
=3( k +3 k + 6) + k(k + 5)
2
=3 k(k + 1) + 6 + k(k + 5)
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 be
made using

More
Less
Related notes for CSCA67H3