Theory of Complex Networks

Tutorial 1

7 problems · 6 solved

  1. 1.Simple and directed graphs and their vertex and edge setssolved 15 Octobersolution

    Which of the three graphs below is simple? Which of them is directed? Give for each of them the vertex set and the edge set .

    The three graphs of Tutorial 1: \(G_{\text{left}}\) is directed, \(G_{\text{middle}}\) and \(G_{\text{right}}\) are not.
    Fig. 1. The three graphs of Tutorial 1: is directed, and are not.
  2. 2.Adjacency matrices of the Tutorial 1 graphssolved 15 Octobersolution

    Calculate the adjacency matrices of the three graphs of exercise 1, after relabelling the nodes of the left graph so that its vertex set becomes .

  3. 3.Graph of a local street neighbourhood and its length-three pathssolution

    Draw a graph corresponding with your local street neighbourhood, and determine its adjacency matrix. How many paths of length three does your graph have? Register an account on Edstem following the link https://edstem.org/us/join/CguTku. Optional: post your result on the forum in the category "Tutorials: Week1".

  4. 4.In- and out-degrees of the Tutorial 1 graphssolved 15 Octobersolution

    Calculate all in-degrees and all out-degrees of the three graphs of exercise 1.

  5. 5.Neighbourhood sets of the directed Tutorial 1 graphsolved 15 Octobersolution

    Determine the neighbourhood sets of the left graph of exercise 1.

  6. 6.In-degree equals out-degree in undirected graphssolved 15 Octobersolution

    Prove that in non-directed graphs , and that .

  7. 7.Sum of in-degrees equals sum of out-degreessolved 15 Octobersolution

    Prove that in directed graphs .

Solutions

  1. 1.Simple and directed graphs and their vertex and edge sets

    None of the graphs has a self-interaction, so all three are simple. Only has arrows, so it is the only directed one.

    An edge is the link , in line with iff . Undirected links are written once as and count as both and .

    • : , with links , , , , , , , , .
    • : , with the eight links for .
    • : , with links , , , , .
  2. 2.Adjacency matrices of the Tutorial 1 graphs

    Convention: iff there is a link , so and .

    Relabel the left graph by sending the nodes that point at the hub to , the hub to , and the nodes the hub points at to , so that the link becomes :

    old 2 10 6 11 3 9 5 7 4
    new 1 6 7 8 9 2 3 4 5

    The middle graph is already labelled : for every , and all other entries are .

    The right graph is already labelled :

  3. 3.Graph of a local street neighbourhood and its length-three paths

    No solution yet.

  4. 4.In- and out-degrees of the Tutorial 1 graphs

    Convention: iff there is a link , so and .

    The left graph is directed, so its in- and out-degrees differ (original labels):

    2 3 4 5 6 7 9 10 11
    0 4 1 1 0 2 1 0 0
    1 4 1 0 1 0 0 1 1

    The other two graphs are not directed, so , the sum of row of .

    • Middle: , and for the other eight nodes.
    • Right: , , .
  5. 5.Neighbourhood sets of the directed Tutorial 1 graph

    The in-neighbourhood holds the nodes with a link into , and the out-neighbourhood the nodes links to:

    2
    3
    4
    5
    6
    7
    9
    10
    11
  6. 6.In-degree equals out-degree in undirected graphs

    With the convention iff there is a link , and .

    In-degree equals out-degree. A non-directed graph has , so

    Degree as a diagonal of . Using and for ,

  7. 7.Sum of in-degrees equals sum of out-degrees

    Both sums count every link exactly once. Relabelling the dummy indices in the second sum,

/ or Ctrl K
search; empty, it shows notes to revise and lately read
m
mark this note to revise, or unmark it
c
cover maths, proofs and solutions to test yourself
n
uncover the next covered item
y
copy this note’s org-roam link
e
copy this note as markdown, LaTeX kept as TeX
p
the next problem to work; there h hints, s shows the solution, x passes it for today
→ ← j k space
turn the page, when reading in pages
l
on the map, trace the greatest distance, then the longest path
double-click
a formula, to copy its TeX
rest on maths
bind a part of a formula and open the wheel of notes it comes from; scroll or ↑ ↓ widens it, 1–6 goes
?
this card