University of Illinois at Urbana Champaign Spring

Description

University of Illinois at Urbana-Champaign Spring 2007 Math 181 Group F1 Midterm 1 : Correction. Friday, Feb. 23. 1. (a) Draw a graph with vertices A, B, C and D in which the valence of vertices A and D is 3 and the valence of vertices B and C is 2. A B C D (b) Is it possible to draw a graph on the same vertices in which A, B and C have valence 2 and D has valence 3 ? (explain). Answer. It is impossible, because the number of odd-valent vertices is always even. 2. For each of the graphs below, determine the minimal number of edges that need to be removed to disconnect it. Removing three edges is needed in order to disconnect this graph. One must remove 2 edges to disconnect this graph

• fit decreasing


• algorithm


• since there


• task time


• time needed


• when scheduling


• sorted-edges algorithm


• brute force


• euler circuit

Sujets

• Algorithm
• Brute Force
• Eulerian path

Informations

• Publié par: profil-urra-2012
• Nombre de lectures: 6
• Langue: English

Extrait

A B C D A D 3
B C 2
A
CB
D
A B C 2 D
3
One must remove 2 edges Removing three edges is needed
to disconnect this graph in order to disconnect this graph.
b.23.1.(a)ossible,devDraalwwneedaIllinoigraphofwitheacvumerticesedes,er.Fn,t,en.andgraphsymineinedgeswhicrhoftheavvalence(explain).ofisvecauseerticesbridadd-vanderticesFysisFCorrection.ofandelotheevminimalalenceerofhvbertmoicedisconnectse:alenceandand1hasisalenceMidterm?.AnswF1ItGroupimp181bMaththe(b)umIseritopalenossiblevtoisdraaweva2.gorrhathephbonw,thetsamer2007theSpringnibnofwhicthataignto,eUrbana-Champeandvttohait.vvUniversityertices2 211 4 4
2 3
3
1 3
8 78 7
4 595 9
56 14
6 139 137 10 610
12
12
8 1111
This graph doesn’t have any Euler circuit; on the left you see an Eulerization This graph admits an Euler
with three added vertices (which is optimal since there are six odd−valentcircuit, as verified by the
vertices in the graph) and an Euler circuit in the Eulerized graph; one that is represented
on the right you see a circuit that covers all edges while reusing a minimalabove.
number of them, obtained by "squeezing" the Euler circuit from the
Eulerized graph.
B
1060
3020
A C
65
90 35
8030
40E D
A
60+10+30+40+80 = 220
10+35+80+90+20 = 235
5
(5−1)!/2 = 4!/2 = 12
oferbuminthetonormw,uSinceminimofaer.reusesanthathamiltonianuitfocecirgraphareplacingobtainthetoetwhiciiteHosoneuto4.methoandvgraphertheaofertices)EulerizationFtnearest-neighecienbanalgorithm.ndtimeesn't,AEBCDdooitisifmi;ygraph.a)manFworvtheingraphtheabcoherevaree,tndumthamiltonianhge(thehabmigraphsltonianeaccircuitquestion,obtainedthebbyalgorithmapplyingythesorted-edgestheAnswonThisedges.ontheobtainsorcircuitalgorithm,A,startingcostatfcircuith.EulerWhattsiadswhetherthesacosteloofc)twhyatcircuitscircuitould?haAnsweer.considerOneorderobtainsapplythebrutecircuitrABCEDeA,dthe?costthereof5whicertices,hhisnEulerbanofwcircuitsdrathises,rdophitcompleteIfwithnot.voriscircuitthe.hb)orSamenearest3.neighb.26×26×26×10×10
1/2
(9−1!)/2 = 8!/2
(1/2)×(8!/2) 10080
7 1 4
2
4 65
6 15
8 6 4
6 71 8
2 4 3
35 23
13 5 3
Thereer.Answ?er.applyinggraphdierenletterstplatespuseossibilities.toursb)requiresYthisou6.oumerals.wnstaumcbhaSinceiofnuteofenineoraalgorithmppartmenytfcomplexess(includ?itotalnergtthewoneusingyhouhalf-minlivtionebin),algorithmandeyouldouminplanmintoKruskvisitteaelocwhandofmixtureylicenseourtpropInerties.AnswIfTheitntakbesofumeralsisnyoedminfolloutethreeto.computeeacthetourtotalalengthuteocomputa-ftime,athetour,rwforceareinwillsituationlongtakwillconstructeditbtakceossible(inutes,mipnutes.utes)Applytoal'sapplytothehbew.brutemanforceHoanllettersgooriathmplatesto,ndetheaoptimalsometourho5.a)wT T1 4
10 13
T7
7
T T2 56 15
T TTT 96 83 12 5 38
T T T T T T1 4 7 3 5 7
30
79
2 79/2 = 39.5
40
79/3 = 26.333...
30
T1
3
T
7TT 52 T T T T T T5 5 3 8 33 5 86
T T T T T T T T T T T8T 12 1 4 6 7 2 4 5T 763 9 6 4
155 8 9 10 14 16 1819 5 8 9 10 1819
T Schedule obtained with the Schedule obtained with the 4 2
decreasing−time list method .critical−path scheduling
method.
T T T T T T T T3 2 5 1 4 6 8 7
T T T T T T T T3 6 2 5 8 1 7 4
toftimeer(are)isisGivequalsctobtheintotalbtasknetime,listwhiceheisouWithtminoutesarehere.from(iii)yTheredared.tewcessors,owproAnswcessorstheAnswsituationser.toTofotal:taskpriorittimeanalysisdivided?bw.yiser.obtainedistheAnswdulingcessor.theprohedulingonetheisgivTheretimate(ii)bminofutes,nsoon'ttheIfminimalproamounumtknoof(i)timefolloneededtheistimeatminimalleastanpath)..minpathsutes.er.(iv)listTherethearewcriticalermouncriticalaWhatthe,theycessor,decreasing-timeminimalproproTheseoststheohedcessors)ebrepresenapplyingabcritical-pathvhethemethoofandhdecreasing-timetsc(lengmethoutesjobminthatleasteatcanrequirew;ssinceestthistheiproserloumwtheerknothandthewlengther.ofcessors.aofcriticalbpath,nwwedon'taYgain:canwingonlythesajobynishinneededthisofcaseamounthatthetheestimatejobewill(b)requireqndathereleastcriticalwillAnswminTheutes.y8.obtainedFyorcritical-pathtishetorder-requiremenTheretAnswdpath(s)ithegisr(a)aelophwhilebprioritelolistw,thendlistthebscdigraphhtedulesorder-requiremen(onthetConsiderwthree7.processors..Flioryieldthreescproulcessors,swtedeogete.3 4
1 1
1 3475
65 22
7,6,5,5,4,4,3,3,2,2,1,1,1
12 3 4 4 1
1
257 6 5
3
1 3 4 4 11
2
257 6 5
3
nbareloywoalgorithmynext-tWhentheandUseistic(a)path4lbs.the3lbs,starting2lb,ery6lbs,algo3lbs,completiono,b(a)lnot(b)TRSameyquestidgesosalesmann,endenusingFthisctimegraph.theusingrst-tthedecreasingmaalgorithm;Answ:er.ourTheilistheuofdowpeighoptimalts(b)inducednonincreasingsorder-iswhen:v1m1lb,e5lbs,on4lbs,y1lb,2lbs,tree7lbs,m5lbs,tain:of9lbsALSEthanhedulingmorelist-pronoithm,holdrequiredcanhthatincreasebinsTRtotsolutiobtain;inttsyrepresen10.hruegfalsetseeighwTwingoro?follAther.algorithmApplyingesthenecessarilyrsrt-tducealgorithmresults.toUEitThegivproebsthetheofollotedwingepacalgorithmkingsolving:trawelingkproblemacapbthedepktpacthe(c)citspann.nALSEustAmiougtoofYgraphxtustoonpageev(e)edgewaalgorithmFer(d)morescotasksttheancessingrst-trFdecreasinger.timeWbeeacusetasktheylisthettime.fromUEquestionsee(b),e9.b(c)okAgain87.theThesameorst-tquestion,nevusingusesthebwxesorst-thdecreasingthealgorithm.algorithm.AnswALSE