АСП1/К3 2017

Извор: SI Wiki
< АСП1
Датум измене: 1. јул 2020. у 21:01; аутор: KockaAdmiralac (разговор | доприноси) (Ispravka uslova za prebrojavanje grana u sedmom zadatku)
Пређи на навигацију Пређи на претрагу

Задаци

1. задатак

Поставка

На слици је дат тежински неусмерени граф. Формирати минимално обухватно стабло коришћењем Крускаловог алгоритма. Приказати поступак избора грана и финално стабло.

Решење

Када уредимо гране по тежини добијамо редослед по којем можемо да их бирамо за убацивање у граф.

  1. Б-D (2)
  2. C-Е (5)
  3. А-C (8)
  4. C-Д (10)
  5. А-Б (12) - А и Б су већ повезани преко А-C, C-Д и Б-D
  6. D-Е (13) - D и Е су већ повезани преко C-Д и C-Е
  7. Б-M (15)
  8. А-Е (25) - сви чворови су нам већ у стаблу
  9. 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. задатак

Поставка

Перица је водоинсталатер. Завршио је посао за данас и враћа се кући, где га жена чека за ручком. На путу до своје куће пролази поред кућа својих пријатеља и зна да ће га сваки од њих зауставити да поприча са њим (мало место, сви се знају, а и наш Перица је добар водоинсталатер). Перица је гладан и није данас много расположен за причу, па жели да стигне кући и притом поприча са што мањим бројем људи. Пут до куће садржи одређени број раскрсница које спајају улице са одређеним бројем кућа.

  1. Објаснити на који начин се изложени проблем може моделовати путем графа.
  2. Написати у псеудокоду функцију која наводи Перицу од посла до куће тако да на путу поприча са што је могуће мањим бројем људи.

Решење

Овај систем можемо моделовати неусмереним тежинским графом у којем су посао, кућа и раскрснице чворови, улице између њих су гране а тежина тих грана је број људских бића са којима ће Перица нажалост морати да се сукоби у његовој најнеомиљенијој дисциплини: пријатељском разговору. 

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. задатак

Поставка

Датотека:АСП1 К3 2017 задатак 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. задатак

Поставка

Нека је дато неко стање проточног графа преко матрице тренутних протока Ф као и одговарајуће стање резидуалног графа преко матрице Р.

  1. Написати функцију која одређује матрицу капацитета и израчунава број грана полазног проточног графа.
  2. У односу на број грана почетног проточног графа, одредити колико најмање и колико највише грана може имати резидулани граф.

Решење

Резидуални граф најмање може имати грана у случају да су сви протоци пуни или празни и има тачно онолико грана колико је потребно да би граф био повезан, или грана у случају да ниједан проток није пун или празан и сваки чвор је повезан са сваким. 

FLOW CAP(F, R)
num_total = 0
for x = 1 to n do
    for y = 1 to n do
        if (F[x, y] > 0) or ((F[x, y] = 0) and (F[y, x] = 0) and (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. задатак

Поставка

Потребно је утврдити да ли је дати повезани неусмерени граф цикличан на што ефикаснији начин.

  1. Објаснити поступак и дати временску сложеност.
  2. На основу предложеног поступка написати псеудокод.

Решење

IS CYCLIC(G)
Преузето из „https://siwiki.rs/w/index.php?title=АСП1/К3_2017&oldid=310”