Paths in network, degree of vertices


  1. Definitions of paths in graph
    • walk, chain and path
    • closed walk, cycle, closed chain, loop
    • length and value of path
    • the shortest path, diameter
    • k-neighbor
    • depth of vertex in acyclic graph
  2. Degree of vertex
    • input degree
    • output degree
    • all degree
  3. Paths and degrees in Pajek

Examples

  1. Find degrees, shortest paths, paths with the lowest value and distances from selected vertex.
  2. Find depths in acyclic networks.

Assignment

  1. Find diameter, draw the longest shortest path. Find out if there exist any loops in the network. Is the network acyclic (in this case find depths of vertices)?
    Determine input, output and all degrees of vertices. Present results in one table - you can use Tools / Excel / Send to Excel / All Partitions.
    Find distances from the vertex with the highest output degree. Find the shortest path between two vertices with the lowest all degrees (if the shortest path exists).

  2. Interpretation of all results.


    Slides (PDF)