АСП1/К3 2017
1. задатак
Поставка
На слици је дат тежински неусмерени граф. Формирати минимално обухватно стабло коришћењем Крускаловог алгоритма. Приказати поступак избора грана и финално стабло.
Решење
- АСП1 К3 2017 задатак 1 граф.пнг
Граф из поставке задатка.
- АСП1 К3 2017 задатак 1 МСТ.пнг
Минимално обухватно стабло за граф из поставке задатка.
2. задатак
Поставка
Написати у псеудокоду итеративну имплементацију функције за тополошко сортирање усмереног нетежинског графа. Уколико у неком тренутку више чворова може бити кандидат за исту позицију у финалном редоследу, бира се чвор са највише непосећених суседа. Граф се представља помоћу листе суседности у чијем се заглављу за сваки чвор, поред показивача на одговорајућу листу суседа, налази и број суседа. Функција треба да врати низ чворова у тополошком поретку.
Решење
TOPSORT(G, n)
3. задатак
Поставка
Перица је водоинсталатер. Завршио је посао за данас и враћа се кући, где га жена чека за ручком. На путу до своје куће пролази поред кућа својих пријатеља и зна да ће га сваки од њих зауставити да поприча са њим (мало место, сви се знају, а и наш Перица је добар водоинсталатер). Перица је гладан и није данас много расположен за причу, па жели да стигне кући и притом поприча са што мањим бројем људи. Пут до куће садржи одређени број раскрсница које спајају улице са одређеним бројем кућа.
- Објаснити на који начин се изложени проблем може моделовати путем графа.
- Написати у псеудокоду функцију која наводи Перицу од посла до куће тако да на путу поприча са што је могуће мањим бројем људи.
Решење
GET PERICA HOME(G, work, home)
4. задатак
Поставка
За граф са слике наћи критични пут и дозвољена кашњења за појединачне чворове. Критични пут означити и на самом графу.
Решење
Критичан пут:
| Чвор | ЕСТ | ЛСТ | L |
|---|---|---|---|
| А | |||
| C | |||
| Е | |||
| Ф | |||
| Г | |||
| Х | |||
| К | |||
| Н | |||
| Р | |||
| С | |||
| Т |
5. задатак
Поставка
Нека се посматра један фудбалски тим са 25 чланова који конкуришу за 11 позиција у тиму. Сваки играч има дефинисан скуп позиција на којима може да игра, а за сваку позицију му се додељује одговарајућа оцена. Дати предлог на који начин се дати проблем може моделовати графом и извршити селекција прве поставе, тако да се изабере постава од 11 играча који имају најбоље оцене. Сматрати да је свака позиција у тиму покривена најмање једним играчем.
Решење
6. задатак
Поставка
Нека се посматра нетежински усмерени граф Г са н чворова. За посматрани граф су коришћењем ДФС алгоритма одређена почетна и завршна времена свих чворова и смештена у низовима Ф и L дужине н. Написати у псеудокоду функцију која проналази највећу јако повезану компоненту по броју чворова. Сматрати да је граф представљен помоћу матрице суседности.
Решење
MAX STRONG CC(G, n)
7. задатак
Поставка
Нека је дато неко стање проточног графа преко матрице тренутних протока Ф као и одговарајуће стање резидуалног графа преко матрице Р.
- Написати функцију која одређује матрицу капацитета и израчунава број грана полазног проточног графа.
- У односу на број грана почетног проточног графа, одредити колико најмање и колико највише грана може имати резидулани граф.
Решење
FLOW CAP(F, R)
8. задатак
Поставка
Потребно је утврдити да ли је дати повезани неусмерени граф цикличан на што ефикаснији начин.
- Објаснити поступак и дати временску сложеност.
- На основу предложеног поступка написати псеудокод.
Решење
IS CYCLIC(G)