# Today I Learned

Some of the things I've learned every day since Oct 10, 2016

## 189: Depth-First, Breadth-First, Uniform Cost, and A* Search Differ Only In Their Fringe

As graph exploration algorithms through search problem state spaces, depth-first, breadth-first, uniform cost, and A* search all have the following general form:

Credit: University of California, Berkeley

They differ only in the type of fringe used. Depth first uses a stack, breadth-first a queue, and both uniform cost and A* use a priority queue. (Uniform cost’s priority is based on the distance from the starting point to a given node, while that of A* is the sum of this distance and the node’s heuristic function.)

## 68: The Tutte Polynomial

In graph theory, the Tutte polynomial $T_G$ of a graph $G$ is a 2-variable polynomial which is well-defined for any undirected graph and contains information about that graph.

Let $G = (V, E)$ be an undirected graph, and let $k(A)$ denote the number of connected components in $G' = (V, A)$, where $A \subseteq E$. Then the Tutte polynomial is defined as

$T_G (x, y) = \sum _{A \subseteq E} (x-1)^{k(A) - k(E)} (y-1)^{k(A) + |A| - |V|}$.

Some properties:

• Isomorphic graphs have the same Tutte polynomial, but the reverse is not the case
• Along $xy = 1$, it specializes to the Jones polynomial of an associated alternating knot
• $T_G (2, 1)$ is the number of forests of $G$
• If $G$ is connected, $T_G (1, 1)$ counts the number of spanning trees.

There are too many to list, but there are many other constraints one can place onto $T_G$ and get various kinds of information about $G$. It enjoys a wide range of applications, from statistical physics to theoretical computer science.