АСП1/К3 2018

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

Задаци

1. задатак

Поставка

Дискутовати имплементацију алгоритма за тополошко сортирање графа у инверзном поретку, уколико се за меморијску репрезентацију графа усвоје листе суседности. Да ли је за ову операцију погодније користити инверзне листе суседности? Образложити одговор уз прецизно навођење разлика у имплементацији.

Решење

2. задатак

Поставка

Дата је матрица путева дужине тачно 1 (један) неког нетежинског усмереног графа. Одредити матрицу путева дужине д≤3. Поступак приказати по корацима, уз образложење.

- А Б C D Е
А 0 1 1 0 0
Б 0 0 0 0 0
C 1 1 0 0 0
D 1 0 0 0 0
Е 0 0 0 1 0

Решење

Датотека:АСП1 К3 2018 задатак 2 граф.пнг
Граф који се добија из матрице суседности.

Наша табела већ садржи информације о свим путевима дужине 1, а то су:

  • АБ
  • АЦ
  • ЦА
  • ЦБ
  • ДА
  • ЕД

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

  • АБ → не може даље
  • АЦ → АЦА, АЦБ
  • ЦА → ЦАЦ, ЦАБ
  • ЦБ → не може даље
  • ДА → ДАБ, ДАЦ
  • ЕД → ЕДА

I тај процес поновимо још једном како бисмо добили путеве дужине 3.

  • АЦА → АЦАБ, АЦАЦ
  • АЦБ → не може даље
  • ЦАЦ → ЦАЦБ, ЦАЦА
  • ЦАБ → не може даље
  • ДАБ → не може даље
  • ДАЦ → ДАЦА, ДАЦБ
  • ЕДА → ЕДАБ, ЕДАЦ

На основу добијених путева ажурирамо матрицу повезаности тако што за сваки пут узмемо чвор са почетка пута и чвор са краја пута, поставимо поље за грану између та два чвора на 1 и за све остале чворове поставимо на 0. Тако се добија коначна таблица испод.

- А Б C D Е
А 1 1 1 0 0
Б 0 0 0 0 0
C 1 1 1 0 0
D 1 1 1 0 0
Е 1 1 1 1 0

3. задатак

Поставка

Дат је усмерени тежински ацикличан граф. Имплементирати функцију ФИНД_ПАТХС_НУМ која треба да пронађе укупан број путања од изворног чвора (срц) до дестинационог чвора (дст) које су краће од вредности прослеђеног параметра к.

Решење

Пошто се не каже да мора итеративно решење, овде нам је најлакше рекурзивно решење. 

FIND PATHS NUM(G, src, dst, k)
if k = 1 then
    return 0
end_if
if src = dst then
    return 1
end_if
paths = 0
for {j : (src, j) ∈ E} do
    paths = paths + FIND_PATHS_NUM(G, j, dst, k - 1)
end_for
return paths

4. задатак

Поставка

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

Решење

TELECOM(G, n, k)
S = {1}
curr = 0
for i = 1 to n-1 do
    find min {w(u, v) : (u ∈ S) and (v ∈ (V - S))}
    curr = curr + w(u, v)
    if curr > k then
        return false
    end_if
    S = S + {v}
end_for
return true

5. задатак

Поставка

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

Решење

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

CONN COMP MAT(G)
curr_comp = 0
for i = 1 to n do
    comp[i] = 0
end_for
stack = t = nil
for i = 1 to n do
    if comp[i] = 0 then
        curr_comp = curr_comp + 1
        comp[i] = curr_comp
        stack = GETNODE
        value(stack) = i
        while stack ≠ nil do
            for j = 1 to n do
                if (e[value(stack), j] = 1) and (comp[j] = 0) then
                    comp[j] = curr_comp
                    t = next(stack)
                    next(stack) = GETNODE
                    value(next(stack)) = j
                    next(next(stack)) = t
                end_if
            end_for
            t = stack
            stack = next(stack)
            FREENODE(t)
        end_while
    end_if
end_for
ALLOCATE(res[curr_comp])
for i = 1 to curr_comp do
    res[i] = nil
end_for
for i = 1 to n do
    if res[comp[i]] = nil then
        res[comp[i]] = v[i]
    end_if
end_for
return res

6. задатак

Поставка

Нека се посматра усмерен граф са слике. Под претпоставком да се за обилазак графа користи БФС алгоритам и почетни чвор А, дефинисати и обележити гране стабла обиласка, гране унапред, повратне гране и попречне гране. Сматрати да се суседи обилазе у алфабетском поретку њихових ознака.

Решење

Редослед обиласка је АБЦДФФГЕ.

  • АСП1 К3 2018 задатак 6 граф.пнг

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

  • АСП1 К3 2018 задатак 6 решење.пнг

    Решење задатка.

7. задатак

Поставка

Датотека:АСП1 К3 2018 задатак 7 граф.пнг
Поједностављен граф из поставке задатка.

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

Решење

Алгоритам завршава свој рад када више не постоји чвор графа и ∉ С коме д[и] ≠ ∞.

С Т D
А Б D Е Ф Г Х
C - ∞ ∞ 3 ∞ ∞ 4 ∞
C, D D ∞ ∞ 3 7 9 4 ∞
C, D, Г Г ∞ ∞ 3 7 6 4 ∞
C, D, Г, Ф Ф ∞ ∞ 3 7 6 4 9
C, D, Г, Ф, Е Е ∞ ∞ 3 7 6 4 9
C, D, Г, Ф, Е, Х Х ∞ ∞ 3 7 6 4 9

8. задатак

Поставка

Максимизација протока графа Г(V, Е)

  1. На формалан (нетекстуални) и прецизан начин дефинисати резидуални граф Гф за проточни граф Г. Колико максимално грана може да има резидуални граф?
  2. Написати функцију која на основу проточног графа Г формира резидуални граф Гф. Граф Г је задат листом суседности, где чвор листе садржи тренутни проток гране ф и њен капацитет ц.

Решење

Резидуални граф Гф је усмерени тежински граф чије гране означавају на који начин се проток у грани која спаја иста два чвора у проточном графу Г може променити. Ако грана између два чвора у резидуалном графу има исти смер као грана између та два иста чвора у проточном графу, то означава да се проток кроз грану у проточном графу може максимално повећати за тежну гране у резидуалном графу. Аналогно, ако гране имају супротне смерове то означава да се проток кроз грану у проточном графу може максимално смањити за тежину гране у резидуалном графу. Могуће је да постоје две гране између два чвора у резидуалном графу, и ако се проток кроз једну грану у проточном графу не може мењати на одређен начин онда одговарајућа грана у резидуалном графу (која би у супротном била тежине 0) не постоји.

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

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

GtoGf(G)
ALLOCATE(E', n)
for i = 1 to n do
    e'[i] = nil
end_for
p = nil
for i = 1 to n do
    p = e[i]
    while p ≠ nil do
        BRANCH_INSERT(E', i, value(p), c(p) - f(p))
        BRANCH_INSERT(E', value(p), i, f(p))
        p = next(p)
    end_while
end_for
return (V, E')

BRANCH INSERT(E', from, to, w)
if w = 0 then
    return
end_if
t = e'[from]
e'[from] = GETNODE
value(e'[from]) = to
next(e'[from]) = t
w(e'[from]) = w
Преузето из „https://siwiki.rs/w/index.php?title=АСП1/К3_2018&oldid=203”