*The following notes are from “A First Course in Network Theory”, by Estrada and Knight”.*

#Preface

– Originated from lecture notes

– Difficult to balance theory and application, catering to a highly diverse student cluster (in lectures_

– Avoid heavy math bias *(dammit)*

– No prerequisite graph theory *(yay)*

– Assuming simple networks unless otherwise stated (bidirectional, unweighted, connecting unique adjacent nodes.)

#Chapter 1: Introduction to Network Theory

##1.1: Overview of Networks

– A vital science, w a plethora of examples

– Original mathematical contributions seemed frivolous in nature; and was for the pure and recreational mathematician

**Why are networks so ubiquitous?**

– ‘being networked’ is a fundamental characteristic of complex systems.

– Aside from extreme scales (cosmological, quantum), all other forms are the study of complexity sciences

*(aside: even quantum foam and the cosmos itself aren’t imprevious to complexity science, more on that in a blog later)*

Some disciplinary examples include

– Chemistry

– Condensed Matter Physics

– Material Science

– Engineering

– Biology

– Psychology

– Economics

– Social sciences

**Interactions and relations are captured by ‘edges’ of a network (straight lines between nodes) **

###Edges can represent…

– Physical links (road, veins)

– Physical interactions (actions between proteins, biological interactions)

– ‘ethereal’ connections (information transfer)

– Geographic proximity (landscapes, cells & tissues)

– Mass energy exchange (metabolic, reactions, trade)

– Social (friendship, familial, business)

– Conceptual (definitions, citations)

– Functional (gene activation, brain functionality)

##1.2 History of Graphs

Network theory began from graph theory, which started with Euler and the ‘Koenigsberg bridge problem’.

>Is it possible to travel through the city, and cross each bridge only once?

There were four areas of the city with bridges between them, so Euler abstracted the problem into areas $A$, $B$, $C$, and $D$, connected by edges representing bridges.

###Example: Knight’s Tour

Can a knight visit every square on a chessboard visiting each once and only once, returning to its original position?

This is an example of a **circuit**. Alexandre Vandermonde formalized the question by letting each square be given by $(m,n)$, for $1 \leq m,n \leq 8$, and gave the following definition:

A Knight’s Tour is an ordered list in which if $(m_1,n_1)$ follows $(m_0,n_0)$, then $|m_1-m_0| = 2$ and $|n_1-n_0| = 1$, OR $|m_1-m_0| = 1$ and $|n_1-n_0| =2$.

A circuit visiting each ‘vertex’ (eg. square on chessboard) once and only once is a *Hamiltonian Circuit**.

## Leave a Reply