Overview
On this page, we discuss some basic results about the theory of graphs (in some contexts also called networks).
Important
The basic and advanced learning objectives listed below are meant to give you an idea of the material you should learn about this section. These are mainly intended to be used in a course which uses an Active Learning approach, where students are required to “read ahead” before each class - but can equally be used in a more traditional course setting.
Unless your teacher gives you specific instructions, it is up to you to decide how much of the listed resources you need to read or watch - you probably do not need to go through all of it. You might also want to look at the General Study Tips & Tricks page for some recommendations on how to effectively study with a math textbook and videos.
Basic learning objectives
These are the tasks you should be able to perform with reasonable fluency when you arrive at your next class meeting. Important new vocabulary words are indicated in italics.
- Identify the vertices and edges in a given (directed or undirected) graph
- Read off the adjacency matrix of a graph.
- Given the adjacency matrix, draw a picture of the graph.
Advanced learning objectives
In addition to mastering the basic objectives, here are the tasks you should be able to perform after class, with practice:
- Use powers of the adjacency matrix to find the number of walks of a specific length between a pair of vertices.
- Identify circuits and cycles (or their absence) in a graph.
To prepare for class
-
Watch this short video explaining how the field of Graph Theory was invented/discovered by Johann Euler in 1736:
-
Watch this short video giving a quick overview of the most important terms used in Graph Theory (or Network theory):
-
Watch this video explaining the adjacency and incidence matrices for a graph, and which also briefly shows how to use the computer algebra system Sage (freely available on CoCalc.com, previously called “Sage Math Cloud” as mentioned in the video) to enter and draw a graph:
-
Watch this video which explains the terms walk, trail, and path:
-
Watch this video which shows how to use powers of the adjacency matrix to find the number of walks of a specific length between a pair of vertices:
Beyond your course
-
Watch this great video (by PBS Infinite Series) about using graph/network theory to analyze friendship/rivalry relationships (with some references [and mild spoilers] for Game of Thrones):
