Differences

This shows you the differences between two versions of the page.

--- graph_theory [2019/01/01 19:07]
paul
+++ graph_theory [2020/08/23 17:12] (current)
@@ Line 32: / Line 32: @@
 {{::graph_term_5.png?direct&600|}}
+**def:** the number of edges incident to a node is called the **degree** of a node.
+**def:** A graph is **simple** if it has no loops of multiple edges.
+Graph Coloring Problem
+Given graph $G$ and $k$ colors assign a color to each node so that the adjacent nodes get different colors.
+Def. Minimum value of $k$ for which such a coloring exists is the chromatic value. $χ(G)$
+Basic graph coloring algorithm for $G=(V,E)$
+    - Order the nodes $V_1, V_2 .. V_n$
+    - Order the colors $C_1, C_2 .. C_k$
+    - For $i = 1,2 ... n$ assign lowest legal color for $V1$
+===== Topological Sorting =====
+[[https://www.youtube.com/watch?v=jonc-AGbPQo|Intro video on topoligical sorting.]]
+==== Kahn's Algorithm for Topological Sorting ====
+[[https://www.youtube.com/watch?v=tFpvX8T0-Pw|Video on Kahn's algorithm of topological sorting.]]
+Everyime we visit a vertex, we decrement the number of depencies it has.
+This is a good explanation of the Alien Dictionary problem: [[https://leetcode.com/problems/alien-dictionary/discuss/157298/C%2B%2B-BFS-and-Topoligical-Sort-with-explanation|link]].