April 24th

Graphs!

Graphs are a super-flexible concept which allows mathematicians and algorists to work with "relationships". If you can model some problem as a graph problem then you will unleash the power of many many powerful geeks!

Graphs are yet another type of binary relation on a set of nodes (sometimes a node is called a vertex) and the relations are the edges. An edge is just a connection between two nodes. If a graph is directed then the edges are arrows. If the edges are weighted then they also have a value associated with them. Don't let the generic-ness fool you into thinking they aren't powerful. You will study them in several future courses and they can be used to solve many interesting problems you wouldn't expect.

Extra Prof.Ninja Resources!

At cs.prof.ninja/slides you can peruse my lecture notes for CISC320 which deals with graphs heavily. The notes which introduce graphs are at class 11.

  1. Here are some major movies and some of their main stars (particularly kevins). Create a graph whose nodes are performers and whose edges are movies that connect two performers (they starred together in the movie).

    For instance a Fish Head is two movies (Apollo 13: Bacon and Paxton) from Kevin Bacon and thus at most 4 movies from any of these Kevins.

  2. In the following word bridge graph how many paths are there from brain to mind?
  3. Find a cycle (path that starts and ends at the same vertex) in the following graph which never visits the same vertex twice (other than the start node).
  4. Create a graph of the contiguous color chunks in the following sock-dye screenshot.
  5. Create a graph from Situation, sir. A neutron star is not neutral! whose nodes are the ten letters in this sentence (the 1 point scrabble tiles btw) and whose edges are arrows from each letter to the next in the sentence. For example there is a directed edge from t to i and none from n to a.
  6. In the previous sentence find a path through all of the letters which never repeats a letter.