# Differences

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

 graph_theory [2019/03/31 14:49] graph_theory [2020/08/23 17:12] (current) 2019/01/01 21:59 paul [Graph Terminology] 2019/01/01 21:59 paul [Graph Terminology] 2019/01/01 21:55 paul [Graph Terminology] 2019/01/01 20:11 paul [Graph Terminology] 2019/01/01 20:10 paul [Graph Terminology] 2019/01/01 19:07 paul 2019/01/01 19:05 paul 2019/01/01 16:42 paul 2019/01/01 16:41 paul 2019/01/01 16:38 paul 2019/01/01 16:38 paul 2019/01/01 16:32 paul 2019/01/01 16:23 paul created Line 1: Line 1: + ====== Graph Theory ====== + + Graph Theory was developed by Leonhard Euler to solve the 7 bridges of Konigsberg problem. + + A graph $G$ is a collection of vertices, $V$, and edges, $E$. + + So we say $G =$ + + Here is an example of a graph: + + {{:graph.png?direct&400|}} + + ===== Graph Terminology ===== + + Incident - Edges that touch a vertex. Ex. $x$ is incident to $a$ and $b$. + + Adjacent - Vertices that are connected. Ex. $a$ is adjacent to $b$; $b$ is adjacent to $a,c,e$ + + Isolated - Vertices that are not connected. Ex. $d$ is isolated. + + {{:graph_term_1.png?direct&600|}} + + The are two types of graphs, undirected and directed. In a directed graph, order matters. + + {{:graph_term_2.png?direct&600|}} + + There are two types of "walks". X-Y walks and closed walks. + + {{::graph_term_4.png?direct&600|}} + + {{::graph_term_3.png?direct&600|}} + + {{::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]].