Računalništvo 1

Večkrat, kot se bo nek znak ali skupina znakov ponovila, bolj bomo lahko stisnili datoteke. Primer, na katerem smo lahko to lepo videli, je primer DNK zapisa bakterije, ko so se ponavljale samo 4-je znaki.

Mislim, da bi bil problem v dekodiranju, saj brez drevesa ne moremo enolično določiti zapis.

Tako je, tudi v najini kodi sma funkcijo za dekodiranje implementirala na tak način. 

Časovna zahtevnost samega huffmanovega algoritma je odvisna od števila različnih znakov v nizu. Zato bi bil algoritem najhitrejši, če je niz sestavljen iz samih enakih znakov. V nasprotnem primeru bi bil najslabši primer, ko niz vsebuje vse možne znake. 

Če pa upoštevamo tudi del, pri katerem polnimo slovar, je časovna zahtevnost odvisna od dolžine začetnega niza. Tako da se lahko velikosti problema v teh dveh primerih močno razlikujeta.

Obstajajo številni algoritmi za stiskanje podatkov. Smiselno bi bilo omeniti Shannon-Fano algoritem. Če se spomnite je bilo na začetku predstavitve povedano, da je Robert Fano  bil Huffmanov profesor in je svojim študentom ponudil izbiro med opravljanjem zaključnega izpita ali pisanjem seminarske naloge. Tema seminarske je bila iskanje najbolj optimalnega algoritma za zapis niza. Študenti niso vedeli da gre za odprt matematični problem s katerim se ukvarja njihov profesor Robert Fano.

 No, problem obstoječega Shannon-Fano algoritma, , ki sta ga razvila Claude Shannon in profesor Robert Fano, leta 1949, pred Huffmanovim algoritmom, je ta da včasih ne vrača najbolj optimalnih rešitev, medtem ko Huffmanovo kodiranje daje vedno optimalne rezultate. V Fanovem algoritmu se gradnja drevesa začne v korenu, torej od zgoraj navzdol, kar je v nasprotju z Huffmanovim algoritmom. Huffmanovo kodiranje je sčasoma zaradi svoje optimalnosti večinoma izpodrinilo uporabo Shannon-Fanojeve metode.

Zelo verjetno, da. Vendar, če uporabimo Huffmanovo kodiranje, kjer moramo prešteti ponovitve znakov nam ta predpostavka ne bo preveč pomagala.

Huffmanova drevesa načeloma niso uravnotežena. Na nek način je njihova naloga zagotoviti kode različnih dolžin in ni narobe če dobimo neuravnotežena drevesa, s katerimi bomo zagotovili dejstvo, da so znaki, ki so najbolj pogosti najbližje korenu drevesa, pri tem so to tudi listi. Znaki ki so redkejši in imajo daljšo kodo so tudi bolj ''oddaljeni'' od korena drevesa.  Za primer lahko pogledamo niz: ''ABCDDDDDDDD''.

Drevo bi zgledalo tako:

Opazimo, da je število pojavitev črke D je večje od skupnega števila pojavitev vseh drugih črk v nizu. Pomeni da bodo vsa vozlišča, razen vozlišča z znakom D v levem poddrevesu. Samo vozlišče z znakom D bo v desnem poddrevesu in na tak način dobimo primer neuravnoteženega drevesa.

Seveda obstaja. Značilno je, da Huffmanovo kodiranje lahko uporabimo kot del večjih in nadgrajenih algoritmov in da se njegova osnovna ideja prepleta v številnih sodobnih algoritmih.

Na primer pri stiskanju slik, videa in zvoka, kjer si lahko privoščimo, da izgubimo delček izvorne informacije in zaradi tega lahko dosežemo boljšo stopnjo stiskanja, pri tem pa človek ponavadi ne opazi bistvene razlike med stisnjeno datoteko in originalom, lahko za najbolj optimalno rešitev vzamemo algoritem z izgubo (angl. lossy).  Torej, algoritmov za kompresijo oziroma stiskanje podatkov z izgubo ali brez, danes ne manjka, vendar moramo biti natančni ko iščemo najboljši algoritem za svoj projekt.

Naša rešitev zagotavlja najbolj optimalen zapis znakov in deluje pravilno.

V naši kodi nisva uporabila algoritma z najmanjšo časovno zahtevnostjo, zato ker se nama je zdela naša implementacija za samo predstavitev bolj razumljiva. Je pa edina razlika v primerjavi z algoritmom, z najmanjšo časovno zahtevnostjo, da se naša tabela na vsakem koraku uredi, kar v osnovi ne bi bilo potrebno. Saj je na začetku tabela urejena in nam ostane le, da novo vsoto vstavimo na pravo mesto. 

Pri Huffmanovem drevesu je dobra lastnost ravno ta, da gre za kompresiranje brez izgube podatkov (lossless), je pa res, da zaradi tega rezultat včasih ni najboljši. Namreč, kot je omenjeno v enem od prejšnjih odgovorov, lahko z algoritmom z izgubo (lossy) prihranimo veliko več prostora, pri tem pa je izguba kvalitete oz. podatkov praktično neopazna.

V sam način delovanja drugih oziroma posodobljenih algoritmov za stiskanje se nisva spuščala. Seveda danes uporabljamo dosti bolj kompleksne in nadgrajene algoritme.  

Vendar sva po spletnih podatkih zasledila, da se tehnika Huffmanovega kodiranja še danes uporablja v metodah stiskanja podatkov, vključno z JPEG, MP3 in ZIP. Ti nadgrajeni algoritmi uporabljajo osnovno idejo Huffmanovega kodiranja, torej vzamemo nabor simbolov, ki so lahko znaki v besedilu in zagotovimo optimalne vzorce bitov, s katerimi predstavimo te simbole. Danes se Huffmanovo kodiranje uporablja v kombinaciji z kodiranjem Ziv-Lempel in tako deluje še veliko bolje.

Horowitz-Sahni algoritem ima eksponentno prostorsko zahtevnost, natančneje: O(2^(n/2)). To pa zato, ker moramo ustvariti vse možne podmnožice, da lahko potem pregledamo če se vsoti dveh podmnožic seštejeta v iskano vrednost.

Algoritem z dinamičnim programiranjem ima prostorsko zahtevnost O(n * s), kjer je n velikost množice, s pa želena vsota (vsi podatki so shranjeni v tabeli velikosti n * s). Prostorsko zahtevnost lahko zmanjšamo, če podatke shranjujemo v dveh seznamih (vedno nas zanima samo prejšnja vrstica).

Algoritem se sploh nebi spremenil.

Ja, saj v takem primeru lahko takoj ustavimo algoritem.

Odvisno od primera, če imamo opravka z množico katere elementi so vsi manjši od želene vsote se hitrost algoritma ne spremeni. Če pa je želena vsota manjša od največjega elementa množice, bi pa lahko algoritem ustavili, ko bi prišli do prvega večjega elementa.

S tem bi dobili 4 množice podmnožic. Problem je nato iskanje ustrezne kombinacije podmnožic. Tak algoritem obstaja, več si lahko prebereš na https://en.wikipedia.org/wiki/Subset_sum_problem razdelek: exponential time algorithms, Schroeppel and Shamir algoritem.

Takšni in podobni algoritmi se uporabljajo veliko kje in niso kaj posebnega. Horowitz-Sahni algoritem zgolj razbije problem na dva dela in potem združi rešitve. Algoritem z dinamičnim programiranjem je zgolj en od dveh najpogostejših pristopov reševanja.

Primer uporabe problema v praksi je pa preverjanje gesel. Računalnik mora preveriti uporabnikovo identiteto. Ker ne želimo da so gesla zapisana nekje v neki bazi, si shranimo zgolj neko vrednost. Geslo je podmnožica neke ogromne množice (neka zunanja funkcija vnesenemu geslu priredi neko podmnožico števil). Računalnik lahko nato preveri ali je vsota podmnožice pravilna.

Pri najinem algoritmu sva uporabila način odstranjevanja korena in ne katerega koli elementa. Če bi to funkcijo napisala, bi kot parameter sprejela index. Za index lahko seveda na hitro preverimo ali je večji od dolžine tabele. Če pa bi hoteli izbrisati točno vrednost v tabeli pa bi enostavno šli skozi tabelo in pogledali ali je element notri. Ta drugi način ima seveda problem, če bi imeli 2 elementa (ali več) s to vrednostjo, saj ne bi vedel katerega izbrisati. Tega problema prvi način s podanim indexom nima.

Glede tega, v kopici ni nobenih omejitev. Kopica je lahko narejena tudi iz samih enakih vrednosti. Recimo tabela [23, 23, 23, 23, 23, 23, 23, 23, 23] je maksimalna(in tudi minimalna) kopica. Če sprašuješ po samem algoritmu, se nič ne spremeni. Vsako posebej spremenimo in ga pošiljamo gor/dol(če je premik potreben seveda) po kopici, glede na to ali smo vrednost zmanjšali ali zvečali.

Prednosti so načeloma to, da je vizualizacija boljša z drevesom, ker takoj vidimo, kdo je oče, kdo je sin in podobno. Sama implementacija bi zahtevala podobno strukturo kot razred “drevo” z dodanimi kazalci na vozlišča. Verjetno bi bilo še lažje ustvariti razred “vozlisce” ki bi kot parameter sprejemal “vrednost”, “Lsin” in “Dsin”(lahko tudi “oce”, ker bi s tem bilo lažje algoritme pisati). Potem pa je odvisno od posameznika, ali mu je lažje razmišljati o indeksih v tabeli, ali pa pisati funkcije za strukturo.

Če si s tem vprašanjem mislil/a na algoritem “heapsort”, je odgovor DA. Spisan algoritem v najinem primeru uniči kopico. To bi seveda lahko enostavno popravili oz. spremenili če bi želeli.

Ne, ker desno poravnano drevo bi zahtevalo drugačno implementacijo tabele. Prvi element bi šel na prvo mesto(tabela[0]), ampak drugi element pa bi moral na tretje mesto(tabela[2]), tretji pa bi nato šel na drugo(tabela[1]). Pri četrtem bi morali iti kar na osmo mesto(tabela[7]) itd… Pri takem načinu bi bila nekatera mesta v tabeli prazna in bi zato morali spremeniti funkcijo odstrani_koren. Na sliki je primer, kjer bi vstavljali elemente 34, 28, 32 in 17 po vrsti. Vidimo, da so v tabeli prazna polja, dokler ni tabela zapolnjena. Zapolnjena bo, ko bo drevo polno.

Kopica je zelo uporabna, ko hočemo dostopati do največjega/najmanjšega elementa iz nekega skupka podatkov. Kopico recimo uporabljajo pri statistiki, ko vedno potrebujejo največji element iz zbirke podatkov.

Kopica ni zelo prostorsko zahtevna, saj je implementirana zgolj kot tabela in ne ustvarja nobenih pomožnih tabel. Torej grajenje same kopice je O(n). Zanimivo pa je, da ima heapsort lahko prostorsko zahtevnost enako O(1), če bi bila funkcija “heapify”(tista funkcija, ki pošilja vozlišče navzdol po kopici) napisana iterativno.

Lahko bi, vendar se pojavi par problemov. Recimo, da pride koren do lista, ampak če to ni zadnji list(element tabele), bi se na tem mestu zbrisal in tako drevo ne bi bilo več levo poravnano, saj bi v njem bila luknja. Zato bi morali še vedno zadnji element postaviti v to luknjo. S tem torej nismo kaj pripomogli k postopku. Recimo pa, da naredimo to na tak način; zadnji list, s katerim smo zapolnili luknjo je sedaj lahko večji od svojega očeta in bi ga morali pošiljati gor po drevesu dokler ni bi prišel na pravo mesto. S tem smo še bolj povečali max število potrebnih menjav.

Seveda je najbolj “enostaven način”, da najprej drevo levo poravnamo in nato iz njega ustvarimo kopico. Tega koraka ne moremo preskočiti, saj je en od pogojev, da je drevo kopica, to da je drevo levo poravnano. Mogoče obstaja kakšna optimizacija, kjer drevo sproti urejamo in poravnavamo, vendar je midva ne najdeva.

Recimo, da imamo podane neke podatke, ki jih hočemo urediti v kopico. Način 1 bi bil, da bi vsak podatek posamezno vstavljali v kopico, kot sva prikazala pri predstavitvi. Način 2 pa bi bil, da bi na naše podatke gledali kot že levo poravnano dvojiško drevo (oz najlažje kot tabelo) in bi to drevo(tabelo) uredili po načinu, ki sva ga opisala (Floydov algoritem). Algoritem pravi, da je najhitrejši način ta, da vse liste(desno polovico tabela) preskočimo, potem pa od konca pošiljamo eno po eno vozlišče navzdol po drevesu (desno v tabeli).

Če imamo tabelo podatkov, ki jih hočemo urediti, kopica načeloma ni enolično določena. Odvisno je kateri algoritem uporabimo. Če uporabimo algoritem, ki sva ga midva, kjer posamezno vstavljamo vsak podatek posebej in gradimo kopico, bi bila kopica drugačna(v večini primerov), kot pa če bi uporabili Floydov algoritem za grajenje kopice. Za točno število možnih kopic si lahko prebereš več na https://www.geeksforgeeks.org/number-ways-form-heap-n-distinct-integers/

Dobro vprašanje, to sva pozabila omeniti. To je seveda možno, je pa vseeno s katerim sinov bi v tem primeru zamenjali. Po menjavi bo en od sinov postal oče od drugega in bo pogoj, da je večji ali enak držal.

Gre zgolj za implementacijo boljšega ali slabšega načina. Če implementiraš boljši način, bo tudi ta vedno uporabljen.

Imenuje se minimalna kopica. To sva omenila na začetku, ampak sva se na predstavitvi fokusirala na maksimalno kopico. Za minimalno kopico veljajo podobna pravila kot za maksimalno: oče mora biti manjši ali enak obema sinovoma in drevo mora biti levo poravnano. Zraven prilagam še primer minimalne kopice.

Odvisno od implementacije. Bolj smiselno se mi sicer zdi pretvarjanje vseh črk v eno od velikosti(male ali velike), saj pri analizi nekega besedila ponavadi ne želimo razlikovati med "lonec" in "Lonec". 

class Trie:

# ...ostale metode...

def trie_delete(self,word):

def trie_del(node,word):

if len(word) == 0:

if node.IsWord: # potrdimo, da smo res nasli besedo

node.IsWord = False

# vozlisca bomo brisali, le ce beseda ni predpona neke druge besede

return len(node.children) == 0 

return False

else:

cont = False # ta vrednost pove, ce moramo se naprej brisati vozlisca

inx = None

# najdemo vozlisce, ki vodi no naslednjega znaka v besedi

for i in range(len(node.children)):

if node.children[i].value == word[0]:

cont = trie_del(node.children[i],word[1:])

inx = i

break

if cont:

node.children.pop(inx) # izbrismo vozlisce

# z brisanjem nadaljujemo, ce trenutno vozlisce ne predstavlja 

# besede in ni predpona drugih besed

if node.IsWord or len(node.children) > 0:

cont = False

return cont

# funkcija sicer vrne neko vrednost(True/False), a je ne posredujemo naprej

trie_del(self.root,word)

Poleg "autocomplete"-a pri urejevalnikih besedil se uporblja tudi kot glavna podatkovna struktura v usmerjevalnikih. Usmerjevalnik shrani IP naslov, ki je zaporedje 32-ih bitov(IPv4), v podatkovno strukturo podobno drevesu predpon, ki je prilagojena shranjevanju nizov bitov konstantne dolžine.  

To bi lahko dosegli tako, da bi v drevo predpon vstavili vse besede nekega jezika(npr. iz slovarja) in preverili, če je naša beseda v drevesu.

Implementacja podatkovne strukture je zelo odvisna od področja uporabe. Na vsakem področju lahko izkoristimo posebnosti za bolj učinkovito delovanje. Shranjevanje večih znakov v enem vozlišču bi sicer bolje izkoristilo prostor, a bi imeli pri vstavljanju več dela. To je glavna ideja kompaktnega drevesa predpon(https://en.wikipedia.org/wiki/Radix_tree).

Pri brisnju vedno najprej potrdimo, da je beseda res v drevesu predpon. Če je ni, brsanje drevesa ne spremeni.

Da, časovna zahtevnost obeh operacij je enaka, saj se moramo na nižji nivo spustiti n-krat, kjer je n dolžina besede, ki jo vstavljamo/brišemo. Pri brisanju moramo nato še izbristi vozlišča, kar naredimo n linearnem času glede na dolžino niza, ki ga želimo izbristi.

V najinem drevesu predpon bi bila niz 'racionalno' ter niz 'iracionalno' shranjena kot dve različni poddrevesi brez skupnih vozlišč, kljub temu da se razlikujeta zgolj za eno črko. V drevesu predpon je smiselno shranjevati le skupne začetke besed. Res je, da se pri tem primeru zapis ponavlja, vendar taki primeri predstavljajo le majhen delež celotnih besed, zato se mi jih ne zdi smiselno posebej obravnavati.

Torej ali bi najina podatkovna struktura delovala, če bi imeli poljubne nize. Izkaže se, da bi saj če premislimo delamo le primerjavo med nizi po velikosti, torej bo niz vseh števil od 1 do 9 manjši od vseh vrednosti črk. Pri najini implementaciji drevesa, bi se torej, ob predpostavki, da do sedaj še nimamo nizov števil, niz '1abc' pojavil na prvem mestu, ko pa bi ustavili še '1abc2', bi se k vozliščem od niza '1abc' le priklopil vozel z vrednostjo '2'.

To ni označeno v drevesu ampak v posameznem vozlu. Naša struktura drevo deluje na ta način, da ima vsebovano novo strukturo vozel, kateri ima lastnosti vrednost, potomci ter ali je beseda konec ali ne. Struktura drevo pa ima le lastnost koren, ki nam pove kateri vozel je koren našega drevesa.

Ne čisto tako, ampak podobno. Odgovor na vprašanje bi bil: odvisno od kodiranja.

Če ponovimo kako gre to v ASCII:

Ja potomce shranjujemo v seznam, saj jih imamo lahko poljubno mnogo in želeli bi jih imeti urejene. Za razliko od dvojiških dreves imamo pri strukturi drevo predpon opraviti s splošnim drevesom, torej imamo lahko poljubno mnogo potomcev. Za dostop do želenega poddrevesa se moremo torej sprehoditi čez seznam  in nadaljevati na želeni vrednosti vozla.

Ključna ideja B-dreves je ta, da želimo združiti čim več podatkov v eno vozlišče, posledično znižati višino drevesa in s tem zmanjšati število dostopov do diska, saj do vseh podatkov vozlišča dostopamo z enim samim dostopom.

Koliko podatkov največ pa lahko shranimo v posamezno vozlišče, da bi lahko do njih dostopali na ta način, pa je odvisno od tega kolikšna je velikost našega pomnilnika. Če je velikost bloka v disku enaka recimo 512KB, velikost posameznega podatka pa 128KB, bomo lahko znotraj posameznega vozlišča shranili maksimalno 4 podatke, tj. red drevesa bo štiri.

Dodatno razlago si lahko pogledate na videu: https://youtu.be/TOb1tuEZ2X4?t=114

Uporaba B-dreves na majhnem številu podatkov se mi ne zdi smiselna, saj so namenjena predvsem za ogromno količino podatkov, ki jih ne moremo shraniti v glavni pomnilnik, pač pa jih hranimo na zunanjem pomnilniku (disku). Podrobnejši opis je pri odgovoru na vprašanje glede določanja reda drevesa.

.

Mislim, da bi bila najbolj primerna uporaba B+-dreves, ki podatke shranjujejo le v listih drevesa, v notranjih vozliščih pa so le ključi (kot indeksi), ki omogočajo usmerjanje po drevesu. Kljub temu, da bomo morali dodatno hraniti ključe notranjih vozlišč, so njihove velikosti veliko manjše od samih podatkov in jih lahko več shranimo na isti blok diska, kar pa pomeni nižji red samega drevesa in manj dostopov na disk, kar pospeši potek operacij nad njimi.

Za lažjo predstavo si lahko na spodnjem posnetku ogledate delovanje indeksiranja v drevesu in kako si lahko z njihovo pomočjo pomagamo, da do željenega podatka dostopamo hitreje. B+ drevesa delujejo podobno: https://youtu.be/aZjYr87r1b8?t=398

Lastnost vsako vozlišče (razen korena) ima vsaj  (m/2) sinov ter vsaj (m/2)– 1 podatkov nam zagotavlja, da je vsako notranje vozišče vsaj na pol polno. Dve taki vozlišči se lahko enostavno združita v eno oz. se lahko eno polno vozlišče razdeli na dve na pol polni. Ta lastnost je precej učinkovita pri operacijah vstavljanja in brisanja.

B-drevesa uporabljamo za shranjevanje velikih baz podatkov na zunanji polnilnik oz. trdi disk. Ker je doseg do ene strani na trdem disku relativno zelo počasen v primerjavi z obdelavo podatkov na hitrem polnilniku, lahko z B-drevesom visokega reda omogočimo dostop do ogromne količine podatkov z majhnim številom branj strani z diska. Tipično se koren drevesa hrani v hitrem polnilniku, eno vozlišče pa ustreza eni strani na disku. B-drevesa navadno uporabljamo za shranjevanje kode za indeksiranje podatkovnih struktur v mnogih DBMS (sistemi za opravljanje podatkovnih baz) na trdih diskih, medtem ko dvojiška drevesa uporabljamo za shranjevanje v RAMU-u.

Če bi bile vrednosti negativne se ne spremeni popolnoma nič, ker imamo v vsakem primeru opravka z iskalnim drevesom, ki vedno ohranja podatke urejene po velikosti.

Vsako vozlišče B-drevesa reda m (razen koren) ima najmanj m/2 sinov in najmanj m/2-1 podatkov. Za korensko vozlišče B-drevesa vemo, da ima vsaj 2 sinova (kadar je notranje vozlišče) ali pa je brez otrok (kadar je celotno drevo sestavljeno samo iz korena). Recimo, da je višina B-drevesa enaka h. Takrat imamo v B-drevesu na nivoju 1 najmanj 2 vozlišči, na nivoju 2 najmanj 2(m/2) = m vozlišč, na nivoju 3 najmanj 2(m/2)^2 = m^2/2,... Vsi listi B-drevesa so na nivoju h in teh je najmanj 2(m/2)^(h-1). Višina B-drevesa reda m z n podatki je: 

.

Število posegov v disk pri iskanju podatka nad B-drevesom zahteva največ tako število operacij, ki je sorazmerno višini B-drevesa. Zato je časovna zahtevnost iskanja v B-drevesu logaritemska: O(log(n)).

Rotacije lahko izvajamo na vseh dvojiških iskalnih drevesih.

Da, pregled v globino bi pri obeh algoritmih storil enako, ko bi v povezanem delu grafa pregledal vsa vozlišča bi skočil na poljubno vozlišče, ki še ni bilo obiskano, torej do vozlišča ne bi prišel prek povezave ampak bi naredil preskok na nepovezan del grafa.

Tarjanov algoritem ima malenkost boljšo časovno zahtevnost saj krepko povezane komponente poišče z enim pregledom v globino, ki ima časovno zahtevnost O(|V|+|E|).
Kosarajujev algoritem pa najprej opravi en pregled v globino, nato graf transponira ter nato opravi še en pregled v globino. Transponiranje grafa ima prav tako časovno zahtevnost O(|V|+|E|).
Torej kot vidimo je časovna zahtevnost kosarajujevega algoritma 3 * O(|V|+|E|), kar je slabše od tarjanovega.

Število krepko povezanih komponent se lahko poveča zmanjša ali pa ostane enako. Vse je odvisno od tega kako vozlišče povežemo z ostalimi vozlišči.
Če vozlišče dodamo ter nobena povezava ne kaže iz njega, pomeni, da vanj lahko pridemo, vendar poti ne bomo mogli nadaljevati, zato bi se število krepko povezanih komponent povečalo – to novo vozlišče bi bila svoja krepko povezana komponenta.
Število krepkih komponent bi ostalo enako, če bi npr. v vozlišče vodila le ena povezava ter bi prav tako le ena povezava izhajala iz vozlišča ter bi ta kazala v vozlišče, ki kaže v dodano vozlišče, torej, da bi se lahko iz na novo dodanega vozlišča vrnili le v tisto iz katerega smo prišli, v tem primeru bi bilo novo vozlišče del iste krepko povezane komponente kot vozlišče preko katerega lahko vanj pridemo.

Lahko pa se število krepko povezanih komponent tudi zmanjša, če imamo na primer graf z dvema vozliščema A in B ter eno povezavo, ki vodi iz A v B, bi imeli 2 krepko povezani komponenti, saj se iz B ne moremo vrniti v A, če pa dodamo še vozlišče C ter dve povezavi, prvo ki vodi iz B v C ter drugo, ki vodi iz C v A, bi imeli krepko povezan graf oz. eno krepko povezano komponento in število krepkih komponent bi se zmanjšalo.
V primeru, da ne dodamo nobene povezave, se število krepko povezanih komponent le poveča za število dodanih vozlišč.

Ja.

Oba algoritma imata linearno časovno zahtevnost.
Tarjanov algoritem opravi en pregled v globino, ki ima časovno zahtevnost O(|V|+|E|).
Kosarajujev algoritem najprej opravi en pregled v globino, nato graf transponira ter nato opravi še en pregled v globino. Transponiranje grafa ima prav tako časovno zahtevnost O(|V|+|E|).
Kot vidimo je časovna zahtevnost kosarajujevega algoritma 3 * O(|V|+|E|), kar pa je še vedno linearna časovna zahtevnost.

Tako je, vsak neusmerjen povezan graf je krepko povezan.