АСП1/К3 2017
1. задатак
Поставка
На слици је дат тежински неусмерени граф. Формирати минимално обухватно стабло коришћењем Крускаловог алгоритма. Приказати поступак избора грана и финално стабло.
Решење
Када уредимо гране по тежини добијамо редослед по којем можемо да их бирамо за убацивање у граф.
- Б-D (2)
- C-Е (5)
- А-C (8)
- C-Д (10)
А-Б (12)- А и Б су већ повезани преко А-C, C-Д и Б-DD-Е (13)- D и Е су већ повезани преко C-Д и C-Е- Б-M (15)
А-Е (25)- сви чворови су нам већ у стаблуM-Е (30)- сви чворови су нам већ у стаблу
- АСП1 К3 2017 задатак 1 граф.пнг
Граф из поставке задатка.
- АСП1 К3 2017 задатак 1 МСТ.пнг
Минимално обухватно стабло за граф из поставке задатка.
2. задатак
Поставка
Написати у псеудокоду итеративну имплементацију функције за тополошко сортирање усмереног нетежинског графа. Уколико у неком тренутку више чворова може бити кандидат за исту позицију у финалном редоследу, бира се чвор са највише непосећених суседа. Граф се представља помоћу листе суседности у чијем се заглављу за сваки чвор, поред показивача на одговорајућу листу суседа, налази и број суседа. Функција треба да врати низ чворова у тополошком поретку.
Решење
TOPSORT(G, n) p = nil for i = 1 to n do in[i] = 0 end_for for i = 1 to n do p = first(e[i]) while p ≠ nil do in[value(p)] = in[value(p)] + 1 p = next(p) end_while end_for tail = head = nil for i = 1 to n do if in[i] = 0 then if tail = nil then tail = head = GETNODE value(tail) = i else PRIORITY_QUEUE_INSERT(tail, head, E, i) end_if end_if end_for i = 1 while tail ≠ nil do ret[i] = value(tail) p = first(e[i]) while p ≠ nil do in[value(p)] = in[value(p)] - 1 if in[value(p)] = 0 then PRIORITY_QUEUE_INSERT(tail, head, E, value(p)) end_if p = next(p) end_while i = i + 1 p = tail tail = next(tail) FREENODE(p) end_while return ret
PRIORITY QUEUE INSERT(tail, head, E, value) p = tail found = false t = nil if num(e[value]) > num(e[value(p)]) then tail = GETNODE value(tail) = value next(tail) = p else while next(p) ≠ nil do if num(e[value]) > num(e[value(next(p))]) then t = next(p) next(p) = GETNODE value(next(p)) = value next(next(p)) = t found = true break end_if p = next(p) end_while if not found then next(head) = GETNODE value(next(head)) = value head = next(head) end_if end_if
3. задатак
Поставка
Перица је водоинсталатер. Завршио је посао за данас и враћа се кући, где га жена чека за ручком. На путу до своје куће пролази поред кућа својих пријатеља и зна да ће га сваки од њих зауставити да поприча са њим (мало место, сви се знају, а и наш Перица је добар водоинсталатер). Перица је гладан и није данас много расположен за причу, па жели да стигне кући и притом поприча са што мањим бројем људи. Пут до куће садржи одређени број раскрсница које спајају улице са одређеним бројем кућа.
- Објаснити на који начин се изложени проблем може моделовати путем графа.
- Написати у псеудокоду функцију која наводи Перицу од посла до куће тако да на путу поприча са што је могуће мањим бројем људи.
Решење
Овај систем можемо моделовати неусмереним тежинским графом у којем су посао, кућа и раскрснице чворови, улице између њих су гране а тежина тих грана је број људских бића са којима ће Перица нажалост морати да се сукоби у његовој најнеомиљенијој дисциплини: пријатељском разговору.
GET PERICA HOME(G, work, home) S = {home} p = nil curr = 0 for i = 1 to n do d[i] = w(home, i) if d[i] = ∞ then t[i] = 0 else t[i] = home end_if end_for for k = 1 to n-1 do find min {d[i] : i ∈ (V - S)} p = e[i] while p ≠ nil do if d[i] + w(i, value(p)) < d[value(p)] then d[value(p)] = d[i] + w(i, value(p)) t[value(p)] = i end_if p = next(p) end_while S = S + {i} end_for curr = t[work] while curr ≠ home then GO(curr) curr = t[curr] end_while GO(home)
4. задатак
Поставка
За граф са слике наћи критични пут и дозвољена кашњења за појединачне чворове. Критични пут означити и на самом графу.
Решење
Критичан пут: АЦГСРТ
Чвор | ЕСТ | ЛСТ | L |
---|---|---|---|
А | 0 | 0 | 0 |
C | 11 | 11 | 0 |
Е | 13 | 25 | 12 |
Ф | 26 | 31 | 5 |
Г | 18 | 18 | 0 |
Х | 10 | 13 | 3 |
К | 32 | 36 | 4 |
Н | 35 | 39 | 4 |
Р | 40 | 40 | 0 |
С | 38 | 38 | 0 |
Т | 43 | 43 | 0 |
5. задатак
Поставка
Нека се посматра један фудбалски тим са 25 чланова који конкуришу за 11 позиција у тиму. Сваки играч има дефинисан скуп позиција на којима може да игра, а за сваку позицију му се додељује одговарајућа оцена. Дати предлог на који начин се дати проблем може моделовати графом и извршити селекција прве поставе, тако да се изабере постава од 11 играча који имају најбоље оцене. Сматрати да је свака позиција у тиму покривена најмање једним играчем.
Решење
Предлажемо структуру неусмереног тежинског графа у којем чворови представљају позиције и играче а грана између играча позиције означава да тај играч може да игра ту позицију (оцена је тежина гране). На почетку одабира позиције се чувају у опадајућем приоритетном реду по броју суседа, и онда се иде по том реду и свакој позицији додељује играч који је најспособнији за ту позицију, а затим се избацују чвор позиције и играча из графа и ажурира број суседа у приоритетном реду. Тај процес се понавља док има чворова у приоритетном реду.
6. задатак
Поставка
Нека се посматра нетежински усмерени граф Г са н чворова. За посматрани граф су коришћењем ДФС алгоритма одређена почетна и завршна времена свих чворова и смештена у низовима Ф и L дужине н. Написати у псеудокоду функцију која проналази највећу јако повезану компоненту по броју чворова. Сматрати да је граф представљен помоћу матрице суседности.
Решење
MAX STRONG CC(G, n)
7. задатак
Поставка
Нека је дато неко стање проточног графа преко матрице тренутних протока Ф као и одговарајуће стање резидуалног графа преко матрице Р.
- Написати функцију која одређује матрицу капацитета и израчунава број грана полазног проточног графа.
- У односу на број грана почетног проточног графа, одредити колико најмање и колико највише грана може имати резидулани граф.
Решење
Резидуални граф најмање може имати грана у случају да су сви протоци пуни или празни и има тачно онолико грана колико је потребно да би граф био повезан, или грана у случају да ниједан проток није пун или празан и сваки чвор је повезан са сваким.
FLOW CAP(F, R) num_total = 0 for x = 1 to n do for y = 1 to n do if (x > y) and ((F[x, y] > 0) or (R[x, y] > 0)) then num_total = num_total + 1 end_if if F[x, y] = 0 then if R[x, y] ≠ 0 then C[x, y] = R[x, y] end_if else C[x, y] = F[x, y] + R[x, y] end_if end_for end_for return num_total
8. задатак
Поставка
Потребно је утврдити да ли је дати повезани неусмерени граф цикличан на што ефикаснији начин.
- Објаснити поступак и дати временску сложеност.
- На основу предложеног поступка написати псеудокод.
Решење
IS CYCLIC(G)