АСП1/К3 2018

Задаци

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 - w(src, j))
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. задатак

Поставка

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

Решење

Основна детекција повезаних компоненти функционише тако што једна петља пролази кроз сваки чвор и ако није посећен рачуна га као одвојену компоненту и ради ДФС над њим како би се остали чворови у компоненти означили као посећени. Са листом суседности спољашња петља пролази тачно н пута кроз низ а од сваког чвора приликом ДФС-а се морају посетити све гране, па то чини укупну сложеност од $\mathcal{O(e + n)}$. Пошто, нажалост, користимо матрицу суседности уместо листе суседности, при обилажењу сваког чвора ДФС-ом мораћемо да прођемо кроз цео ред матрице како бисмо одредили које су у њој гране, и то ћемо морати да учинимо за сваки чвор (јер ћемо сваки чвор морати да посетимо), што без обзира на спољашњу петљу чини сложеност од $\mathcal{O(n^2)}$.

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. Написати функцију која на основу проточног графа Г формира резидуални граф Г_ф. Граф Г је задат листом суседности, где чвор листе садржи тренутни проток гране ф и њен капацитет ц.

Решење

$G_f = (V, E_f)$

$E_f = \{(i, j) : i, j \in V, c(i, j) - f(i, j) > 0 \}$

Резидуални граф може максимално да има дупло више грана од проточног графа, у случају да се након замене грана не добију гране тежине 0. Проточни граф има максималан број грана $\frac{n(n-1)}{2}$ јер између свака два чвора може да постоји грана, па зато резидуални граф може да има максимално $n(n-1)$ грана.

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