Graph Theory Introduction


In [1]:
import networkx as nx
import matplotlib.pyplot as plt
from scipy import sparse
from IPython.display import Image, display
%matplotlib inline

G = nx.house_graph()
pos = nx.spring_layout(G)
nx.draw(G, pos=pos)


Definition

  • Mathematical definition:

    A graph is is an ordered pair $G = (V,E)$ of a set $V$ of vertices or nodes and a set $E \subseteq [V]^2$ of edges or lines. The elements of $E$ are therefore 2-element subsets of $V$, representing a relation between the two elemnts of $V$.

  • Terminology:
    • graph = network = web
    • vertex = node = point = site = junction: $i = v_i$
    • edge = line = link = arc = tie: $(i,j) = e$
  • Examples:

    graph nodes edges
    internet computers network connections
    power grid power plants, consumers power cables
    transportation network locations routes
    social network individuals relationship
    citation network scientific paper citation
    neural network neuron synapses
    food web functional groups feeding relationships

In [2]:
display(Image(filename='pictures/air_net_light.jpg'))
display(Image(filename='pictures/europ_grid.jpg'))
display(Image(filename='pictures/ice_net.jpg'))
display(Image(filename='pictures/leaf_net.jpg'))
display(Image(filename='pictures/mold_net.png'))
display(Image(filename='pictures/mouse_brain.jpg'))