1 of 11

What is a Network

A configuration of agents (vertices or nodes)
Connections between agents (edges) representing some manner of interaction

Social networks

Nodes = individuals

edges = friendships/acquaintances

2 of 11

Can you take a walk through the town, visiting each part of the town and crossing each bridge only once?

This question was given to a famous mathematician called Leonhard Euler (1707 - 1783).

The Seven Bridges of Königsberg

The old town of Königsberg has seven bridges:

3 of 11

Simplify the map

There are four areas of the town - on the mainland north of the river, on the mainland south of the river, on the island and on the peninsula (the piece of land on the right). Let us label them A, B, C and D

Can you draw each line p, q, r, s, t, u and v only once, without removing your pencil from the paper?

The Seven Bridges of Königsberg

4 of 11

Graphs and Digraphs

5 of 11

A graph is a pair G = (V,E) where V is a set whose elements are nodes and E is a set whose elements are a set of unordered pairs {u,v} of nodes (called edges).
If we specify an orientation for edges, we call the result a directed graph (digraph).
When an edge exists between nodes u,v, these nodes are called adjacent.
The degree of a node is the number of edges connecting it.
A multigraph is a graph that allows multiple edges to exist between the same pair of nodes.
A node without an edge is called an isolated node.
An edge that connects one node to itself is called a loop.
A graph without loops, isolated nodes and multiple edges is called a simple graph.

Graph Definitions

6 of 11

Example Graphs

7 of 11

Example Digraphs

8 of 11

Basic Graphs and Their Adjacency Matrices

9 of 11

Why Graphs?

Graphs are a general language for describing and analyzing entities with relations/interactions