Kurssiviikko 10

Kysymys 1

Mitkä seuraavista väitteistä ovat totta?

Jos on reitti solmusta \(x\) solmuun \(y\), niin on olemassa kaari solmusta \(x\) solmuun \(y\).

Jos suuntaamattomassa graafissa on olemassa reitti solmusta \(x\) solmuun \(y\), niin on olemassa myös reitti solmusta \(y\) solmuun \(x\).

Suuntaamattomalla graafilla voi olla silmukka, mutta suunnatulla graafilla ei.

Jos suunnatussa graafissa on olemassa kaari solmusta \(x\) solmuun \(y\), niin kaaren solmusta \(y\) solmuun \(x\) on oltava olemassa.

Jokainen puu on graafi, mutta kaikki graafit eivät ole puita.

Kysymys 2

Mitkä seuraavista väitteistä yhtenäisestä graafista ovat totta?

Yhtenäisessä graafissa on olemassa kaari jokaisesta solmusta \(x\) jokaiseen muuhun solmuun \(y\).

Yhtenäisessä graafissa jokaiseen solmuun on kytketty vähintään yksi kaari.

Graafissa, joka ei ole yhtenäinen, on olemassa ainakin yksi solmu, johon ei ole kytketty yhtään kaarta.

Jos graafi on yhtenäinen ja ei ole olemassa kaarta solmusta \(x\) solmuun \(y\), niin reitillä solmusta \(x\) solmuun \(y\) on vähintään 2 kaarta.

Kysymys 1

Kun tutkitaan suunnattua graafia, missä seuraavista tilanteista leveys-ensin-haku (BFS) olisi hyödyllinen?

Kun halutaan löytää lyhyin reitti yhdestä tietystä solmusta kaikkiin muihin solmuihin.

Kun halutaan löytää pisin reitti yhdestä tietystä solmusta johonkin toiseen tiettyyn solmuun.

Kun halutaan löytää graafin lyhyin silmukka.

Kun halutaan löytää solmu, jolla on eniten naapurisolmuja.

Kysymys 2

Oletetaan, että suunnatulla graafilla on 4 solmua, \(s\), \(a\), \(b\) ja \(c\). Oletetaan myös, että graafilla on kaikki mahdolliset kaaret paitsi 2, kaari solmusta \(s\) solmuun \(a\) ja kaari solmusta \(a\) solmuun \(b\). Mitkä ovat etäisyydet solmusta \(s\) kaikkiin muihin solmuihin?

etäisyydet solmusta \(s\) solmuun \(a\) 2, solmusta \(s\) solmuun \(b\) 2, solmusta \(s\) solmuun \(c\) 1

etäisyydet solmusta \(s\) solmuun \(a\) 1, solmusta \(s\) solmuun \(b\) 2, solmusta \(s\) solmuun \(c\) 1

etäisyydet solmusta \(s\) solmuun \(a\) 2, solmusta \(s\) solmuun \(b\) 1, solmusta \(s\) solmuun \(c\) 2

etäisyydet solmusta \(s\) solmuun \(a\) 2, solmusta \(s\) solmuun \(b\) 1, solmusta \(s\) solmuun \(c\) 1

Kysymys 3

Oletetaan, että BFS-algoritmi aloittaa solmusta \(s\). Oletetaan, että \(x\) on toinen solmu ja on olemassa reitti solmusta \(s\) solmuun \(x\). Miksi BFS-algoritmi määrittää eri värejä solmulle \(x\)?

Se tekee niin seuratakseen, kuinka monta naapurisolmua solmulla \(x\) on.

Se tekee niin seuratakseen, onko reitti solmusta \(s\) solmuun \(x\) löydetty ja onko \(x\) täysin käsitelty.

Se tekee niin varmistaakseen, että kun BFS on lopettanut, kahdella naapurisolmulla ei ole samaa väriä.

Se tekee niin varmistaakseen, että BFS:n käyttämässä jonossa ei ole kahta samanväristä solmua.

Kysymys 4

Oletetaan, että suunnattu graafi syötetään BFS-algoritmiin. Oletetaan myös, että BFS-algoritmi aloittaa solmusta \(s\) ja on olemassa reitti solmusta \(s\) jokaiseen muuhun solmuun. Kun BFS-algoritmi on lopettanut, mitkä seuraavista ovat totta? (Huomaa: useampi kuin yksi väite voi olla totta.)

BFS:n käyttämässä jonossa on kaikki solmut.

BFS:n tuloksista voidaan muodostaa reitti solmusta \(s\) mihin tahansa muuhun solmuun.

BFS varmistaa, että kahdella solmulla ei ole samaa väriä, kun BFS on lopettanut.

BFS on laskenut positiivisen etäisyyden kaikille solmuille lukuunottamatta solmua \(s\).

Kysymys 1

Kun tutkitaan suunnattua graafia, missä seuraavista tilanteista syvyys-ensin-haku (DFS) olisi hyödyllinen?

Kun halutaan löytää kaikki reitit tietystä solmusta toiseen tiettyyn solmuun.

Kun halutaan selvittää, onko suunnatussa graafissa silmukoita vai ei.

Kun halutaan löytää pisin reitti tietystä solmusta toiseen tiettyyn solmuun.

Kun halutaan löytää kaikki tietyn pituiset reitit tietystä solmusta toiseen tiettyyn solmuun.

Kysymys 2

DFS-algoritmissa käytetään pinoa. Oletetaan, että \(x\) ja \(y\) ovat kaksi eri solmua suunnatussa graafissa. Minkä säännön mukaan DFS-pino toimii?

Jos \(x\) on pinon päällimmäinen solmu ja halutaan lisätä pinoon solmu \(y\), \(x\) on ensin poistettava pinosta.

Jos on olemassa kaari solmusta \(x\) solmuun \(y\), niin \(x\) ja \(y\) eivät saa olla pinossa samanaikaisesti.

Jos \(x\) ja \(y\) ovat molemmat pinossa samanaikaisesti ja solmu \(x\) on lisätty pinoon ennen solmua \(y\), niin \(x\) poistetaan pinosta ennen solmua \(y\).

Jos \(x\) ja \(y\) ovat molemmat pinossa samanaikaisesti ja solmu \(x\) on lisätty pinoon ennen solmua \(y\), niin \(y\) poistetaan pinosta ennen solmua \(x\).

Kysymys 1

Oletetaan, että graafi tallennetaan C++:ssa. Oletetaan, että solmun tiedot tallennetaan struct:ssa, jossa solmun naapurisolmut tallennetaan joko vector-säiliössä tai unordered_set-säiliössä. Missä tilanneessa on järkevämpi käyttää unordered_set-säiliötä?

Kun jokaisella graafin solmulla on korkeintaan 1 naapurisolmu ja naapurisolmu ei koskaan muutu.

Kun usein lisätään kaareja graafiin tai poistetaan kaareja graafista.

Kun minkä tahansa solmun naapurisolmut aina käsiteltävä tietyssä järjestyksessä.

Kun jokaiselle solmulle annetaan nimi, joka ei koskaan muutu.

Kysymys 2

Kun tallennetaan graafi C++:ssa, mikä seuraavista väitteistä on totta?

On aina käytettävä STL-kirjaston säiliötä nimeltä std::graph-structure.

On aina oltava mahdollista antaa solmulle väri.

On vain yksi oikea tapa tallentaa solmun naapurisolmut.

Kaikkien solmujen naapurisolmut on tallennettava.

Kurssiviikko 10¶

Itseopiskelu¶

Graafit¶

Leveys-ensin-haku (BFS)¶

Syvyys-ensin-haku (DFS)¶

Graafien toteuttaminen¶

Viikkoharjoitusten palautettavat kotitehtävät¶