graph_theory [Paul's Wiki]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
====== 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 = <V,E>$

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