{ "cells": [ { "cell_type": "markdown", "metadata": {}, "source": [ "# Graphs and Networks in Linear Algebra\n", "\n", "This notebook is based on section 10.1 of Strang's *Linear Algebra* textbook.\n", "\n", "One interesting source of large matrices in linear algebra is a [graph](https://en.wikipedia.org/wiki/Graph_(discrete_mathematics), a collection of *nodes* (vertices) and *edges* (arrows from one vertex to another). Graphs are used in many applications to represent *relationships* and *connectivity*, such as:\n", "\n", "* For computer networks, nodes could represent web pages, and edges could represent links.\n", "* For circuits, edges could represent wires (or resistors) and nodes junctions.\n", "* For transportation, nodes could represent cities and edges roads.\n", "* In bioinformatics, graphs can represent gene regulatory networks.\n", "* In sociology, nodes could represent people and edges relationships.\n", "* ... and many, many other applications ...\n", "\n", "In this notebook, we explain how a graph can be represented by a *matrix*, and how linear algebra can tell us properties of the graph and can help us do computations on graph-based problems. There is a particularly beautiful connection to Kirchhoff's laws of circuit theory." ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "## Packages for this notebook\n", "\n", "To run the code in this notebook, you'll need to install a few Julia packages used below. To do so, uncomment the following line and run it:" ] }, { "cell_type": "code", "execution_count": 1, "metadata": {}, "outputs": [], "source": [ "# Pkg.add.([\"LightGraphs\", \"MetaGraphs\", \"GraphPlot\", \"NamedColors\", \"RowEchelon\", Interact\", \"SymPy\"])" ] }, { "cell_type": "markdown", "metadata": {}, "source": [ "...and then run this cell to import the packages:" ] }, { "cell_type": "code", "execution_count": 2, "metadata": {}, "outputs": [ { "data": { "text/html": [ " \n", "