How to Create a Graph Derived from the 3-CNF Formula

The Clique Problem

The clique problem is an optimization problem where we ask if a clique (complete subgraphs) of a given size k 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 G = (V, E) is a subset V of vertices
  • Each pair of vertices is connected by an edge in E.
  • A clique is a complete sub-graph of G
  • The size of the clique is the number of vertices it contains

Example

Lets compute the graph from the formula \phi in polynomial time.

  • \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} )

Steps

First draw a graph G derived from the formula \phi where:

  • c_{1} = (x_{1} \vee \neg x_{2} \vee \neg x_{3} )
  • c_{2} = (\neg x_{1} \vee x_{2} \vee x_{3} )
  • c_{3} = (x_{1} \vee x_{2} \vee x_{3} )
  1. Connect c_{1}(x_{1}) to c_{2}(x_{2}, x_{3}) and c_{3}(x_{1},x_{2}, x_{3})
  2. Connect c_{1}(\neg x_{2}) to c_{2}(\neg x_{1}, x_{3}) and c_{3}(x_{1}, x_{3})
  3. Connect c_{1}(\neg x_{3}) to c_{2}(\neg x_{1}, x_{2}) and c_{3}(x_{1}, x_{2})
  4. Connect c_{2}(\neg x_{1}) to c_{1}(x_{2}, x_{3})
  5. Connect c_{2}(x_{2}) to c_{3}(x_{1}, x_{2}, x_{3})
  6. Connect c_{2}(x_{3}) to c_{3}(x_{1}, x_{2}, x_{3})
  7. Done

GNF Draw Steps3CNF Draw Complete

 

 

 

 

 

 

 

 

 

© 2015, Alejandro G. Carlstein Ramos Mejia. All rights reserved.

Share

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.

*

Click to Insert Smiley

SmileBig SmileGrinLaughFrownBig FrownCryNeutralWinkKissRazzChicCoolAngryReally AngryConfusedQuestionThinkingPainShockYesNoLOLSillyBeautyLashesCuteShyBlushKissedIn LoveDroolGiggleSnickerHeh!SmirkWiltWeepIDKStruggleSide FrownDazedHypnotizedSweatEek!Roll EyesSarcasmDisdainSmugMoney MouthFoot in MouthShut MouthQuietShameBeat UpMeanEvil GrinGrit TeethShoutPissed OffReally PissedMad RazzDrunken RazzSickYawnSleepyDanceClapJumpHandshakeHigh FiveHug LeftHug RightKiss BlowKissingByeGo AwayCall MeOn the PhoneSecretMeetingWavingStopTime OutTalk to the HandLoserLyingDOH!Fingers CrossedWaitingSuspenseTremblePrayWorshipStarvingEatVictoryCurseAlienAngelClownCowboyCyclopsDevilDoctorFemale FighterMale FighterMohawkMusicNerdPartyPirateSkywalkerSnowmanSoldierVampireZombie KillerGhostSkeletonBunnyCatCat 2ChickChickenChicken 2CowCow 2DogDog 2DuckGoatHippoKoalaLionMonkeyMonkey 2MousePandaPigPig 2SheepSheep 2ReindeerSnailTigerTurtleBeerDrinkLiquorCoffeeCakePizzaWatermelonBowlPlateCanFemaleMaleHeartBroken HeartRoseDead RosePeaceYin YangUS FlagMoonStarSunCloudyRainThunderUmbrellaRainbowMusic NoteAirplaneCarIslandAnnouncebrbMailCellPhoneCameraFilmTVClockLampSearchCoinsComputerConsolePresentSoccerCloverPumpkinBombHammerKnifeHandcuffsPillPoopCigarette