Skip to content

Latest commit

 

History

History
161 lines (150 loc) · 9.61 KB

graph-theory.md

File metadata and controls

161 lines (150 loc) · 9.61 KB
Raw

Graph Theory

  • A graph is a network of connected nodes (i.e. vertices)..
  • A connection with a direction is an arc.
  • A connection without a direction is an edge.
  • A connection can have a weight or cost.
  • A graph with directions is called a directed graph, or digraph.
  • A graph with weights is called a weighted graph.
  • You may want to visit every node: the travelling salesman problem.
  • You may want to find the shortest or cheapest path.

Representations

You can represent a graph as a list of edges or arcs:

  • 1 -> 2
  • 2 -> 3
  • 2 -> 4
  • 3 -> 4
  • 3 -> 5
  • 3 -> 6
  • 4 -> 1
  • 4 -> 5
  • 5 -> 2

You can also represent a graph as a dictionary of lists, where each key is a node, and each value is a list of connected nodes.

graph = {1: [2],
         2: [3, 4],
         3: [4, 5, 6],
         4: [1, 5],
         5: [2]}

Definitions

Mathematical Theories

Graph Features

Types of Graph

Graph operations

Problems

Algorithms