*The following notes are from “A First Course in Network Theory”, by Estrada and Knight”.*
– 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
– Condensed Matter Physics
– Material Science
– 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