You are here

Binary Relations as Graphs

16 June, 2015 - 14:31
Available under Creative Commons-ShareAlike 4.0 International License. Download for free at http://cnx.org/contents/383d4b87-2d7b-454e-99fe-2eaa43eae8ff@20.20

In fact, binary relations are common enough that sometimes people use some entirely new vocabulary: A domain with a binary relation can be called vertices with edges between them. Together this is known as a graph. We won't stress these terms right now, as we're not studying graph theory.

Binary relations (graphs) can be depicted visually, by drawing the domain elements (vertices) as dots, and drawing arrows (edges) between related elements.

A binary relation with a whole website devoted to it is "has starred in a movie with". We'll call this relation hasStarredWith over the domain of actors. Some sample points in this relation:

  1. hasStarredWith (Ewan McGregor, Cameron Diaz), as witnessed by the movie A Life Less Ordinary, 1997.
  2. hasStarredWith (Cameron Diaz, John Cusack), as witnessed by the movie Being John Malkovich, 1999.

You can think of each actor being a "location", and two actors being "adjacent" to each other if they have ever starred in a movie together; two of these locations, even if not adjacent might have a multi-step path between them. (There is also a shorter path; can you think of it? The (in)famous Kevin Bacon game asks to find a shortest path from one location to the location Kevin Bacon. Make a guess, as to the longest shortest path leading from (some obscure) location to Kevin Bacon.)

Some other graphs:

  • Vertices can be tasks, with edges meaning dependencies of what must be done first.
  • In parallel processing, Vertices can be lines of code; there is an edge between two lines if they involve common variables. Finding subsets of vertices with no lines between them represent sets of instructions that can be executed in parallel (and thus assigned to different processors.)
  • "Word ladders" seek to transform one word to another by changing one letter at a time, while always remaining a word. For example, a ladder leading from WHITE to SPINE in three steps is: ·
    • WHITE ·
    • WHINE ·
    • SHINE ·
    • SPINE

If a solution to such a puzzle corresponds to a path, what do vertices represent? What are edges? Do you think there is a path from any 5-letter word to another?