# 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) |
||
---|---|---|---|

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 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. | ||

+ | |||

+ | {{: | ||

+ | |||

+ | The are two types of graphs, undirected and directed. In a directed graph, order matters. | ||

+ | |||

+ | {{: | ||

+ | |||

+ | There are two types of " | ||

+ | |||

+ | {{:: | ||

+ | |||

+ | {{:: | ||

+ | |||

+ | {{:: | ||

+ | |||

+ | **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:// | ||

+ | |||

+ | ==== Kahn's Algorithm for Topological Sorting ==== | ||

+ | |||

+ | [[https:// | ||

+ | |||

+ | Everyime we visit a vertex, we decrement the number of depencies it has. | ||

+ | |||

+ | This is a good explanation of the Alien Dictionary problem: [[https:// | ||