University of Illinois at Urbana Champaign Spring

pages

English

Documents

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

Découvre YouScribe en t'inscrivant gratuitement

Je m'inscris

pages

English

Ebook

Lire un extrait

Obtenez un accès à la bibliothèque pour le consulter en ligne En savoir plus

Publié par

profil-urra-2012

Nombre de lectures

Langue

English

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

ﬁt decreasing

algorithm

since there

task time

time needed

when scheduling

sorted-edges algorithm

brute force

euler circuit

Voir

Publié par

profil-urra-2012

Nombre de lectures

Langue

English

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

Voir

Univers
Ebooks
Livres audio
Presse
Podcasts
BD
Documents

University of Illinois at Urbana Champaign Spring

YouScribe

Le catalogue

Le service

Les conditions