Scribd
Upload
12 views1 page

Adobe Scan Oct 18, 2023

The document discusses the problem of finding a clique of size k in an undirected graph. It outlines the use of exhaustive search methods and suggests writing a logical expression to identify a clique. Additionally, it highlights the importance of understanding the vertices and edges of the graph for implementing the solution.

Uploaded by

katiahenrriquez14
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
12 views1 page

Adobe Scan Oct 18, 2023

The document discusses the problem of finding a clique of size k in an undirected graph. It outlines the use of exhaustive search methods and suggests writing a logical expression to identify a clique. Additionally, it highlights the importance of understanding the vertices and edges of the graph for implementing the solution.

Uploaded by

katiahenrriquez14
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 1

k Cl ·,que Problem 1_,.:.

,
•Jv ' · '
(
_ .
~•,._ ,·/Ji.\•
~1
- 1,,:1i1 , . :\::,::•::
In . '·If~~' .' . 'there is an undirected graph}nd a'nbnrieg~tive number k'
and the
",.·
to
. . , :,:,,.•:::t-t•r-
find a clique of size k.

: 3\ ~~~m11; ~~i,s r.?f'.~he three main types of exhaustive search is appropriate


J'-. .~J9r. lh1s robl_e~n;~l '.'
} ~ ln,ipJS P.':CAli?fj:f_o,r;t~e next step, write an expression that is true if and only if a
·· ~~r~I9--,~S~~} clkiLie in the graph G = (V. £). (Hint: Your expression will
~51:ieea(to tisc'exjctly.two bounded quantifiers.)
_Tt,·::iijJl ~- 'j~:~~ ',':.:t~)~/.; I

\. 1
II ~f\d ~ -<,0-n>fl;,1.-i,' - Sui"? jv'>\- \ cow.lo, .. ~h lM &- WM.I.kn h i;'\d cL,.11-'td S.lvll•"'

• .. lo c. i:o..- P"•ltf\1 1 I\.U.1 t1> (!\flO ""- \ poS\ o'I.IC. (.~~1<~ .~ v-trli<.cl "14,0-,.,~ <1. c.l,'\.,"''
of- \ i ?;l 1:.

i. IA_,v E}(. ·. (1A1v)-,l1.11 v)e£


n>v 0.\1 f?11- 1'S of a(\t."'Ct Vitv-11<.t\ \.\, O.'\.) V ;VI ~L t Y. 1 i~ V. •~ not ( I .,_ "1 fw-, l'\.\.t t.1,e ( "- 1V)

IM I.I. \ I I,<. f..-lHVli i... "' f"' E


4

• "f - ·· ,.,, . ,r.,-;~ ...'l"'t-"~·-

;On ' _ i~l_-,L~ _.t\t~;at q~!r.act on paper


·t th kc1· P bl v .,.. '~f.;,:.,m;,,71/•v•
_• _· or .· e - 1que ro em. OU~S? t\f\/O"<,j;i/
·~
:precondition/postcondition pairs _J.~,-~t
.,6u\vill
" ~._~:r,...
need to refer . l.•~' _ ,

· to the vertices and edges of a g~a · · ~r,ition for doing ,


;, f so described in the frrst chapter'<~,, ~\'("; ( . . ·,i!
'(j} From your contract, identify the l 9r(~n . ,.rjJ
,f
II . • .

exhaustive-search solution to the k~Cl,q , >Mr,11111",i!r,..r· . .,,,. _ 9~r;th,at the j


-/: worst-case running time for an exhaustive sT,arc epe]"(ldip,n, th~ si~e of the 'j
1

search space. so it is more efficient to use a srn~!l, . se9rfb~ a(e: : M.,::


·--°'~?-"F,l.<--.~i,:.- -<..,,&!;t.;"': ,
,;,

~o
('r'- tot\ ~i\ioV1 : k ~li'.to ¥\ ~i'\1()1'\ ', K._ O
('rHot\~i\ioV1 : V"t [>'- Vvfy :
1 \)(\ : A. X P{v)
(c.( 1v)E.£ po '.:,-\-e,o 'V\.d\ t,\) It\ : (, = L-
7'IY'>tC.o>'\di\iOW1 : C V
rost c.o"~;i,;011 , lc.l-=
('O\t tollldil'lll~ : °i II\ 1II£ C. ( V. 1- \J) ~ ( IA , V) E, t.
"V. E. C. VV (C... LIA .:t ") .-:} (IA.I" ) E- E

You might also like