{"id":2925,"date":"2015-04-03T10:13:39","date_gmt":"2015-04-03T14:13:39","guid":{"rendered":"http:\/\/www.acarlstein.com\/?p=2925"},"modified":"2015-04-03T11:03:29","modified_gmt":"2015-04-03T15:03:29","slug":"how-to-create-a-graph-derived-from-the-3-cnf-formula","status":"publish","type":"post","link":"http:\/\/blog.acarlstein.com\/?p=2925","title":{"rendered":"How to Create a Graph Derived from the 3-CNF Formula"},"content":{"rendered":"<p><strong>The Clique Problem<\/strong><\/p>\n<p>The <a href=\"http:\/\/en.wikipedia.org\/wiki\/Clique_problem\" target=\"_blank\">clique problem<\/a> is an optimization problem where we ask if a clique (<a title=\"Complete graph\" href=\"http:\/\/en.wikipedia.org\/wiki\/Complete_graph\" target=\"_blank\">complete<\/a> <a title=\"Glossary of graph theory\" href=\"http:\/\/en.wikipedia.org\/wiki\/Glossary_of_graph_theory#Subgraphs\" target=\"_blank\">subgraphs<\/a>) of a given size\u00a0<img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?k\" alt=\"k\" align=\"absmiddle\" \/> exists in the graph.<br \/>\nThe idea is to find the clique maximum size in a graph.<\/p>\n<p><span style=\"text-decoration: underline;\">List of Facts<\/span><\/p>\n<ul>\n<li>A clique in a undirected graph\u00a0<img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?G&amp;space;=&amp;space;(V,&amp;space;E)\" alt=\"G = (V, E)\" align=\"absmiddle\" \/> is a subset\u00a0<img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?V'&amp;space;\\subseteq&amp;space;V\" alt=\"V' \\subseteq V\" align=\"absmiddle\" \/> of vertices<\/li>\n<li>Each pair of vertices is connected by an edge in\u00a0<img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?E\" alt=\"E\" align=\"absmiddle\" \/>.<\/li>\n<li>A clique is a complete sub-graph of <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?G\" alt=\"G\" align=\"absmiddle\" \/><\/li>\n<li>The size of the clique is the number of vertices it contains<\/li>\n<\/ul>\n<p><span style=\"text-decoration: underline;\">Example<\/span><\/p>\n<p>Lets compute the graph from the formula <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?\\phi\" alt=\"\\phi\" align=\"absmiddle\" \/> in polynomial time.<\/p>\n<ul>\n<li><img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?\\phi&amp;space;=&amp;space;(x_{1}&amp;space;\\vee&amp;space;\\neg&amp;space;x_{2}&amp;space;\\vee&amp;space;\\neg&amp;space;x_{3}&amp;space;)&amp;space;\\wedge&amp;space;(\\neg&amp;space;x_{1}&amp;space;\\vee&amp;space;x_{2}&amp;space;\\vee&amp;space;x_{3}&amp;space;)&amp;space;\\wedge&amp;space;(x_{1}&amp;space;\\vee&amp;space;x_{2}&amp;space;\\vee&amp;space;x_{3}&amp;space;)\" alt=\"\\phi = (x_{1} \\vee \\neg x_{2} \\vee \\neg x_{3} ) \\wedge (\\neg x_{1} \\vee x_{2} \\vee x_{3} ) \\wedge (x_{1} \\vee x_{2} \\vee x_{3} )\" align=\"absmiddle\" \/><\/li>\n<\/ul>\n<p><span style=\"text-decoration: underline;\">Steps<\/span><\/p>\n<p>First draw a graph\u00a0<img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?G\" alt=\"G\" align=\"absmiddle\" \/> derived from the formula <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?\\phi\" alt=\"\\phi\" align=\"absmiddle\" \/> where:<\/p>\n<ul>\n<li><img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?c_{1}&amp;space;=&amp;space;(x_{1}&amp;space;\\vee&amp;space;\\neg&amp;space;x_{2}&amp;space;\\vee&amp;space;\\neg&amp;space;x_{3}&amp;space;)\" alt=\"c_{1} = (x_{1} \\vee \\neg x_{2} \\vee \\neg x_{3} )\" align=\"absmiddle\" \/><\/li>\n<li><img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?c_{2}&amp;space;=&amp;space;(\\neg&amp;space;x_{1}&amp;space;\\vee&amp;space;x_{2}&amp;space;\\vee&amp;space;x_{3}&amp;space;)\" alt=\"c_{2} = (\\neg x_{1} \\vee x_{2} \\vee x_{3} )\" align=\"absmiddle\" \/><\/li>\n<li><img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?c_{3}&amp;space;=&amp;space;(x_{1}&amp;space;\\vee&amp;space;x_{2}&amp;space;\\vee&amp;space;x_{3}&amp;space;)\" alt=\"c_{3} = (x_{1} \\vee x_{2} \\vee x_{3} )\" align=\"absmiddle\" \/><\/li>\n<\/ul>\n<ol style=\"list-style-type: upper-alpha;\">\n<li>Connect <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?c_{1}(x_{1})\" alt=\"c_{1}(x_{1})\" align=\"absmiddle\" \/> to <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?c_{2}(x_{2},&amp;space;x_{3})\" alt=\"c_{2}(x_{2}, x_{3})\" align=\"absmiddle\" \/> and <img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?c_{3}(x_{1},x_{2},&amp;space;x_{3})\" alt=\"c_{3}(x_{1},x_{2}, x_{3})\" align=\"absmiddle\" \/><\/li>\n<li>Connect\u00a0<img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?c_{1}(\\neg&amp;space;x_{2})\" alt=\"c_{1}(\\neg x_{2})\" align=\"absmiddle\" \/> to\u00a0<img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?c_{2}(\\neg&amp;space;x_{1},&amp;space;x_{3})\" alt=\"c_{2}(\\neg x_{1}, x_{3})\" align=\"absmiddle\" \/> and\u00a0<img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?c_{3}(x_{1},&amp;space;x_{3})\" alt=\"c_{3}(x_{1}, x_{3})\" align=\"absmiddle\" \/><\/li>\n<li>Connect\u00a0<img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?c_{1}(\\neg&amp;space;x_{3})\" alt=\"c_{1}(\\neg x_{3})\" align=\"absmiddle\" \/> to\u00a0<img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?c_{2}(\\neg&amp;space;x_{1},&amp;space;x_{2})\" alt=\"c_{2}(\\neg x_{1}, x_{2})\" align=\"absmiddle\" \/> and\u00a0<img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?c_{3}(x_{1},&amp;space;x_{2})\" alt=\"c_{3}(x_{1}, x_{2})\" align=\"absmiddle\" \/><\/li>\n<li>Connect\u00a0<img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?c_{2}(\\neg&amp;space;x_{1})\" alt=\"c_{2}(\\neg x_{1})\" align=\"absmiddle\" \/> to\u00a0<img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?c_{1}(x_{2},&amp;space;x_{3})\" alt=\"c_{1}(x_{2}, x_{3})\" align=\"absmiddle\" \/><\/li>\n<li>Connect\u00a0<img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?c_{2}(x_{2})\" alt=\"c_{2}(x_{2})\" align=\"absmiddle\" \/> to\u00a0<img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?c_{3}(x_{1},&amp;space;x_{2},&amp;space;x_{3})\" alt=\"c_{3}(x_{1}, x_{2}, x_{3})\" align=\"absmiddle\" \/><\/li>\n<li>Connect\u00a0<img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?c_{2}(x_{3})\" alt=\"c_{2}(x_{3})\" align=\"absmiddle\" \/> to\u00a0<img decoding=\"async\" src=\"http:\/\/latex.codecogs.com\/gif.latex?c_{3}(x_{1},&amp;space;x_{2},&amp;space;x_{3})\" alt=\"c_{3}(x_{1}, x_{2}, x_{3})\" align=\"absmiddle\" \/><\/li>\n<li>Done<\/li>\n<\/ol>\n<p><a href=\"http:\/\/www.elblender.com\/wordpress\/wp-content\/uploads\/2015\/04\/GNF-Draw-Steps.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\" size-full wp-image-2930 aligncenter\" src=\"http:\/\/www.elblender.com\/wordpress\/wp-content\/uploads\/2015\/04\/GNF-Draw-Steps.jpg\" alt=\"GNF Draw Steps\" width=\"484\" height=\"689\" srcset=\"http:\/\/blog.acarlstein.com\/wp-content\/uploads\/2015\/04\/GNF-Draw-Steps.jpg 484w, http:\/\/blog.acarlstein.com\/wp-content\/uploads\/2015\/04\/GNF-Draw-Steps-211x300.jpg 211w\" sizes=\"auto, (max-width: 484px) 100vw, 484px\" \/><\/a><a href=\"http:\/\/www.elblender.com\/wordpress\/wp-content\/uploads\/2015\/04\/3CNF-Draw-Complete.jpg\"><img loading=\"lazy\" decoding=\"async\" class=\" size-full wp-image-2929 aligncenter\" src=\"http:\/\/www.elblender.com\/wordpress\/wp-content\/uploads\/2015\/04\/3CNF-Draw-Complete.jpg\" alt=\"3CNF Draw Complete\" width=\"405\" height=\"303\" srcset=\"http:\/\/blog.acarlstein.com\/wp-content\/uploads\/2015\/04\/3CNF-Draw-Complete.jpg 405w, http:\/\/blog.acarlstein.com\/wp-content\/uploads\/2015\/04\/3CNF-Draw-Complete-300x224.jpg 300w\" sizes=\"auto, (max-width: 405px) 100vw, 405px\" \/><\/a><\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n\n<script>\nvar zbPregResult = '0';\n<\/script>\n","protected":false},"excerpt":{"rendered":"<p>The Clique Problem The clique problem is an optimization problem where we ask if a clique (complete subgraphs) of a given size\u00a0 exists in the graph. The idea is to find the clique maximum size in a graph. List of Facts A clique in a undirected graph\u00a0 is a subset\u00a0 of vertices Each pair of [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[19,218],"tags":[1267,1268,1266],"class_list":["post-2925","post","type-post","status-publish","format-standard","hentry","category-programming","category-algorithms-programming","tag-3-cnf","tag-formula","tag-graph"],"_links":{"self":[{"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=\/wp\/v2\/posts\/2925","targetHints":{"allow":["GET"]}}],"collection":[{"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2925"}],"version-history":[{"count":7,"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=\/wp\/v2\/posts\/2925\/revisions"}],"predecessor-version":[{"id":2940,"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=\/wp\/v2\/posts\/2925\/revisions\/2940"}],"wp:attachment":[{"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2925"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2925"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/blog.acarlstein.com\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2925"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}