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

  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)