Back to notes

Graph theory

Keywords: math, graphs, graph theory, data structures, discrete mathematics
  • Graph theory is the study of graphs
  • a graph is a mathematical data structure used to model 1-to-1 relationships between components of the graph
  • graphs are made up of vertices and edges:
    • vertices:
      • AKA "nodes" or "points"
      • connected by "edges"
    • edges:
      • AKA "links" or "lines"
      • connect "vertices" to each other
  • there are multiple types of graphs:
    • undirected:
      • edges connect vertices "symmetrically":
        • any vertex can connect to any other vertex equally
      • groups of connected vertices within an undirected graph are called "connected components" or "components"
    • directed:
      • edges connect vertices "asymmetrically":
        • relationships between vertices can only be established depending on which vertex is establishing the relationship -- relationships in graphs aren't necessarily reciprocal