Achieving an Undergraduate Level Understanding of Graph Theory

Date: December 31 2022

Summary: Ultralearning project to learn the equivalent of an undergraduate maths of computer science student understanding of graph theory.

Keywords: #zettel #ultralearning #graph #theory #project #archive #blog

Bibliography

Not Available

Table of Contents

Motivation

I have always found graph theory interesting ever since I was exposed to it back in my undergraduate studies at Georgia Tech. I found out about it through SIR Modeling but personally found the structure of graphs far more fascinating than its application to SIR models. Furthermore, as I intend to be pursuing graduate studies in applied mathematics, why not get started with trying to understand it?

Project Goals

This process is adapted from the Ultralearning framework posited by Scott Young.

What Am I Doing?

Gain an undergraduate level of understanding of graph theory on par with maths and computer science students.

Concepts

• Basic concepts:

  • Definition of a graph and its components:

    • Understand the components of a graph and the differences between directed and undirected graphs.

  • Subgraphs and isomorphism:

    • Understand the definitions of subgraphs and isomorphism and be able to identify and compare them in a given graph.

  • Directed graphs:

    • Understand the definition of a directed graph and be able to represent it using adjacency and incidence matrices.

  • Graphs and their properties:

    • Understand various properties of graphs and be able to apply them to analyze and classify different types of graphs.

• Connectivity:

  • Paths and circuits:

    • Understand the definitions of paths and circuits and be able to identify and construct them in a given graph.

  • Connectedness and components:

    • Understand the concept of connectedness and be able to determine whether a graph is connected or disconnected.

    • Understand the concept of graph components and be able to identify them in a given graph.

  • Distance in graphs:

    • Understand the concept of distance between vertices and be able to compute it using various measures.

• Trees:

  • Trees and their properties:

    • Understand the definition of a tree and be able to identify and distinguish trees from other types of graphs.

  • Rooted trees and binary trees:

    • Understand the concept of rooted trees and be able to construct and manipulate them.

    • Understand the concept of binary trees and be able to construct and manipulate them.

  • Spanning trees

• Matrix representations of graphs:

  • Adjacency matrices:

    • Understand the concept of an adjacency matrix and be able to represent a graph using an adjacency matrix.

  • Incidence matrices:

    • Understand the concept of an incidence matrix and be able to represent a graph using an incidence matrix.

• Graph algorithms:

  • Breadth-first search:

    • Understand the concept of breadth-first search and be able to implement it to traverse a graph.

  • Depth-first search:

    • Understand the concept of depth-first search and be able to implement it to traverse a graph.

• Planar graphs:

  • Planar graphs and their properties:

    • Understand the definition of a planar graph and the properties that distinguish planar graphs from other types of graphs.

  • Euler's formula:

    • Understand Euler's formula and be able to apply it to analyze the structure of planar graphs.

  • Dual graphs:

    • Understand the concept of a dual graph and be able to construct the dual of a given planar graph.

• Coloring graphs:

  • Vertex coloring:

    • Understand the concept of vertex coloring and be able to color the vertices of a given graph according to various coloring schemes.

  • Edge coloring:

    • Understand the concept of edge coloring and be able to color the edges of a given graph according to various coloring schemes.

• Matchings and factors:

  • Matchings:

    • Understand the concept of a matching in a graph and be able to identify and construct matchings in a given graph.

  • Factors:

    • Understand the concept of a factor in a graph and be able to identify and construct factors in a given graph.

• More advanced topics:

  • Hamiltonian cycles:

    • Understand the concept of a Hamiltonian cycle and be able to identify and construct Hamiltonian cycles in a given graph.

  • Network flows:

    • Understand the concept of network flows and be able to model and analyze flow problems in graphs.

  • Graphs and groups:

    • Understand the connection between graphs and group theory, and be able to apply group-theoretic techniques to analyze graphs.

  • Graphs and logic:

    • Understand the connection between graphs and logic, and be able to apply logical techniques to analyze graphs.

  • Graphs and geometry:

    • Understand the connection between graphs and geometry, and be able to apply geometric techniques to analyze graphs.

Facts

• Definition of a graph and its components:

  • Vertices (also called nodes).

  • Edges.

  • Weights.

  • Labels.

• Subgraphs and isomorphism.

• Directed graphs and their representations:

  • Adjacency matrices.

  • Incidence matrices.

• Graph properties:

  • Connected/disconnected.

  • Bipartite/not bipartite.

  • Cyclic/acyclic.

• Paths and circuits.

• Connectedness and components.

• Distance between vertices.

• Trees:

  • Definition.

  • Unique path between vertices.

  • Root vertex.

  • Branches.

• Additional topics:

  • Matrix representations:

    • Adjacency matrices.

    • Incidence matrices.

  • Graph algorithms:

    • Breadth-first search.

    • Depth-first search.

  • Planar graphs and their properties:

    • Definition of a planar graph.

    • Properties that distinguish planar graphs from other types of graphs.

    • Euler's formula.

    • Dual graphs.

  • Tree properties:

    • Rooted trees.

    • Binary trees.

Procedures

1. Representing graphs using different notations (e.g. adjacency lists, adjacency matrices, incidence matrices).

2. Traversing graphs using different algorithms (e.g. breadth-first search, depth-first search).

3. Analyzing the properties of graphs (e.g. connectedness, bipartiteness, acyclicity).

4. Finding paths and circuits in graphs.

5. Identifying and constructing different types of trees (e.g. rooted trees, binary trees).

6. Coloring the vertices or edges of a graph according to various coloring schemes (e.g. vertex coloring, edge coloring).

7. Finding matchings and factors in graphs.

8. Identifying and constructing Hamiltonian cycles in graphs.

9. Modeling and analyzing flow problems in graphs using network flows.

10. Applying group-theoretic and logical techniques to analyze graphs.

11. Applying geometric techniques to analyze graphs.

Roadmap

This is based on the Meta Learning step Young described as well as some additional tweaks of my own:

• Outcomes: The knowledge and abilities you’ll need to acquire for success.

• Rationale: Know exactly why you want to learn a skill or subject.

• Resources: The resources you’ll use when learning.

• Done: If this task has been completed (X) or not yet (cell is empty)

This table describes the very broad topics, resources I'll use, and the expected learning outcomes for each topic. As I progress through this table, I will add an "X" to each row I have studied. Furthermore, the table is ordered by level of difficulty with "Definition of a graph and its components" being the first topic I should learn and "Graphs and geometry" being the more advanced topics I should study. The topics and resources here are based on [1] and [2] with potentially more resources to add in the future.

This table gets more into exact topics and concepts to master. They have an associated difficult level and overall topic. Moreover, this a synthesis of concepts and topics to be covered based on class outlines from:

• COMS W4203: Introduction to Graph Theory (taught by Timothy Sun at Columbia University)

• MATH 6014: Graph Theory (taught at Georgia Institute of Technology)

• MATH 4022: Introduction to Graph Theory (taught at Georgia Institute of Technology)

How To Cite

Zelko, Jacob. Achieving an Undergraduate Level Understanding of Graph Theory. https://jacobzelko.com/01012023000122-graph-theory-learning. December 31 2022.

References:

[1] R. Trudeau, Introduction to Graph Theory, Dover. DOVER PUBLICATIONS, INC., 1994.

[2] N. Hartsfield and Ringel, Pearls in Graph Theory A Comprehensive Introduction. DOVER PUBLICATIONS, INC., 1994.

Discussion: