Graph theory
Keywords: | math, graphs, graph theory, data structures, discrete mathematics |
Date: |
- 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
- vertices:
- 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"
- edges connect vertices "symmetrically":
- 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
- edges connect vertices "asymmetrically":
- undirected: