:PROPERTIES: :ID: 80095df3-22a2-4a89-9968-c1734c94c219 :mtime: 20231026081959 20231026071151 :ctime: 20231026071145 :END: #+title: graph (discrete mathematics) #+filetags: :public:project: * Definition of a graph ** Undirected Graph In the context of discrete mathematics, a *graph* is a pair $(V,E)$, where $V$ is the set of verticies and $E$ is the set of edges. ** Directed Graph * Different Types of Graphs - undirected graphs - directed graphs - multigraphs. * Examples of graphs - Linkedin connections - Facebook friends - Dependency graphs of programs. * Graph-theoretic Terms - degree - in-degree - out-degree - Simple path - edge-disjoin path - directed acyclic graph - Tree - rooted tree - Walk * Problems and algorithms involving graphs - Shortest path on graph problem - [[id:a69c361e-b8fb-4a93-a456-61b53360d2a7][Find the topological ordering of a graph]] - depth-first seach. - Determine if graph is cyclic. * Representations of graphs in programming ** Agda representation #+BEGIN_SRC agda2 record Graph (Obj : Type) (arr : Obj → Obj → Prop) : Type where field decide : (A B : Obj) -> Dec (arr A B) flip : {A B : Obj} -> arr A B -> arr B A record FiniteGraph (Obj : Type) (arr : Obj → Obj → Prop) : Type where field neighbors : Obj -> Set Obj #+END_SRC ** Adjacency Lists