# Graph Theory Introduction

``````

In :

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 :

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'))

``````
``````

``````