Poti v omrežju, stopnje točk


  1. Definicije poti v grafu
    • sprehod, veriga in pot v grafu
    • cikel, zanka
    • dolžina in vrednost poti
    • najkrajša pot
    • k-sosed
    • definicija globine točke v acikličnem grafu
  2. Definicija stopnje točke v grafu
    • vhodna stopnja
    • izhodna stopnja
    • skupna stopnja
  3. Poti in stopnje točk v programu Pajek

Vaje

  1. V danih omrežjih poiščite stopnje točk, najkrajše poti, poti z najmanjšimi vrednostmi, ter oddaljenosti vseh točk od izbrane točke.
  2. V danih acikičnih omrežjih poiščite globine točk.

Naloga

    V primeru, da je vaše omrežje preredko (okvirno manj kot 50 povezav) in sestavljeno iz večih nepovezanih kosov, prosim, da za nadaljnje naloge namesto omrežja, ki ste ga sami vnesli, uporabljate omrežje, ki vam je dodeljeno na spisku: Spisek dodatnih nalog (PDF), Dodatne naloge (ZIP)
    (legenda: u: univerzitetni DI, v: visokošolski DI; k: komunikologi).

  1. Vsak študent v svojem omrežju poišče premer, ter najdaljšo najkrajšo pot nariše. Poleg tega ugotovi ali obstajajo zanke. Ugotovi tudi ali je omrežje aciklično, ter v tem primeru poišče globine vseh točk.
    V eni tabeli je potrebno izpisati vhodne, izhodne in skupne stopnje za vse točke (pomagate si lahko z ukazom Tools / Excel / Send to Excel / All Partitions).
    Za točko z najvišjo izhodno stopnjo izpiše oddaljenosti vseh drugih točk. Za točki z najmanjšima skupnima stopnjama poišče najkrajšo pot med njima (če obstaja).

  2. Interpretacija rezultatov v nekaj stavkih.


Predavanja (PDF)