5 Pages
English

# University of Illinois at Urbana Champaign Spring

5 Pages
English

Description

University of Illinois at Urbana-Champaign Spring 2007 Math 181 Group F1 Midterm 1. Friday, Feb. 23. No documents allowed. Mobile phones, mp3 players, etc., are also forbidden. The one and only piece of equip- ment you may use is a basic calculator- and you won't need it. NAME 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. (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). 2. For each of the graphs below, determine the minimal number of edges that need to be removed to disconnect it.

• hold no

• ﬁt decreasing

• algorithm

• no documents allowed

• algorithm when

• does

• ﬁrst-ﬁt algorithm

• when scheduling

Subjects

##### Algorithm

Informations

Exrait

A B C D A D 3
B C 2
A B C 2 D
3
Friday,erticesdisconnectandFerev1.gFb.23.eloNobdoiscumentsertaltoloweond.181MidtermMobilephones,ofmp3eplayers,hetc.,moarandeandalsooffsoprwbidden.aF1sameGroupwhicvTheonevMathandovnly(explain).pieeaccgraphsedeofmineeedgesquip-needmentryouedmaySpringuseaignisUrbana-Champathebalence2007visice.tIsasicacalculator-(b)aitndossibleyoudrawona'trnephethedvit.inNAMEh,and1.ha(a)eDraalencewandahasgraphalencewith?v2.erticesorsh,theIllinoib,w,oftminimalrumtheandnUniversitybinofwhicthatthetovealenceeofvvtoerticesit.B
1060 3020
A C
65
90
35
8030
40E D
A
17 4
2
45
6 15
8 6 4
6 71 8
2 4 3
35 23
13 35