АСП1/К3 2017

Извор: SI Wiki
Пређи на навигацију Пређи на претрагу

Задаци

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) - сви чворови су нам већ у стаблу
  • Граф из поставке задатка.

    Граф из поставке задатка.

  • Минимално обухватно стабло за граф из поставке задатка.

    Минимално обухватно стабло за граф из поставке задатка.

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

Поставка

Граф из поставке задатка.

За граф са слике наћи критични пут и дозвољена кашњења за појединачне чворове. Критични пут означити и на самом графу.

Решење

Критичан пут: АЦГСРТ

Чвор ЕСТ ЛСТ 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. задатак

Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.

Поставка

Нека се посматра нетежински усмерени граф Г са н чворова. За посматрани граф су коришћењем ДФС алгоритма одређена почетна и завршна времена свих чворова и смештена у низовима Ф и 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. задатак

Овај задатак није решен. Помозите СИ Wики тако што ћете га решити.

Поставка

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

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

Решење

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