Graph coloring problem

gcprabha 9,185 views 14 slides Oct 21, 2019
Slide 1
Slide 1 of 14
Slide 1
1
Slide 2
2
Slide 3
3
Slide 4
4
Slide 5
5
Slide 6
6
Slide 7
7
Slide 8
8
Slide 9
9
Slide 10
10
Slide 11
11
Slide 12
12
Slide 13
13
Slide 14
14

About This Presentation

Planar graph coloring problem using Backtracking algorithm


Slide Content

Mrs.G.Chandraprabha,M.Sc.,M.Phil.,
Assistant Professor
Department of IT
V.V.Vanniaperumal College for Women
Virudhunagar
Graph Coloring problem
Using Backtracking

GraphColoringisanassignmentofcolors(orany
distinctmarks)totheverticesofagraph.Strictly
speaking,acoloringisapropercoloringifnotwo
adjacentverticeshavethesamecolor.SGVf )(:

Definition:Agraphisplanarifitcanbedrawninaplane
withoutedge-crossings.
Thefourcolortheorem:Foreveryplanargraph,the
chromaticnumberis≤4.

Thefourcolortheoremstatesthatanyplanarmapcan
becoloredwithatmostfourcolors.
Ingraphterminology,thismeansthatusingatmost
fourcolors,anyplanargraphcanhaveitsnodescolored
suchthatnotwoadjacentnodeshavethesamecolor.
Four-colorconjecture–FrancisGuthrie,1852(F.G.)
Manyincompleteproofs(Kempe).
5-colortheoremprovedin1890(Heawood)
4-colortheoremfinallyprovedin1977(Appel,Haken)
◦Firstmajorcomputer-basedproof

Avertexcoloringisanassignmentoflabelsorcolors
toeachvertexofagraphsuchthatnoedgeconnects
twoidenticallycoloredvertices

Similartovertexcoloring,exceptedgesarecolor.
Adjacentedgeshavedifferentcolors.

Everyedge-coloringproblemcanbetransformedintoa
vertex-coloringproblem
ColoringtheedgesofgraphGisthesameascoloring
theverticesinL(G)
Noteveryvertex-coloringproblemcanbetransformed
toanedge-coloringproblem
Everygraphhasalinegraph,butnoteverygraphisa
linegraphofsomeothergraph

K-Coloring
◦Ak-coloringofagraphGisamappingofV(G)onto
theintegers1..ksuchthatadjacentverticesmapinto
differentintegers.
◦Ak-coloringpartitionsV(G)intokdisjointsubsets
suchthatverticesfromdifferentsubsetshave
differentcolors.

K-colorable
◦AgraphGisk-colorableifithasak-coloring.
ChromaticNumber
◦ThesmallestintegerkforwhichGisk-colorableis
calledthechromaticnumberofG,isdenotedbythe
χ(G).

Theideaistoassigncolorsonebyonetodifferent
vertices,startingfromthevertex0.Beforeassigninga
color,wecheckforsafetybyconsideringalready
assignedcolorstotheadjacentvertices.
Ifwefindacolorassignmentwhichissafe,wemark
thecolorassignmentaspartofsolution.
Ifwedonotafindcolorduetoclashesthenwe
backtrackandreturnfalse.
Backtracking Algorithm

NP:theclassofdecisionproblemsthataresolvablein
polynomialtimeonanondeterministicmachine(orwitha
nondeterministicalgorithm)
(Adeterministiccomputeriswhatweknow)
Anondeterministiccomputerisonethatcan“guess”theright
answerorsolutionthinkofanondeterministiccomputerasa
parallelmachinethatcanfreelyspawnaninfinitenumberof
processes
ThusNPcanalsobethoughtofastheclassofproblems
whosesolutionscanbeverifiedinpolynomialtime
NotethatNPstandsfor“NondeterministicPolynomial-time”

FractionalKnapsack
Sorting
Others?
◦GraphColoring
◦Satisfiability(SAT)
theproblemofdecidingwhetheragiven
Booleanformulaissatisfiable.

Manyproblemscanbeformulatedasagraphcoloring
problemincludingTimeTabling,Scheduling,Register
Allocation,ChannelAssignment.
Alotofresearchhasbeendoneinthisareasomuchis
alreadyknownabouttheproblemspace.

Thank You