Today I Learned

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

Category Archives: graphs

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.