Discrete Structures

Graphs and Trees

Last Update: 9 April 2012

Note: or material is highlighted

Graphs
1. A Set-Theoretical Definition of Graphs
2. 7 Bridges of Königsberg (from Rosen)
  - Seven Bridges of Königsberg (Wikipedia)
    - Article on the graph-theoretical problem, with the same map, clarified.
  - Jacobs, Frank (2011), "Walk Like an Eulerian: The Bridges of Königsberg", Strange Maps (16 October).
3. Tymoczko, Thomas (1979), "The Four-Color Problem and Its Philosophical Significance", Journal of Philosophy 76(2) (February): 57-83.
  - Gardner, Martin (1966), Martin Gardner's New Mathematical Diversions from Scientific American (New York: Simon & Schuster), Ch. 10: "The Four-Color Map Theorem", pp. 113-123, 250-251.
4. Dipert, Randall R. (1997), "The Mathematical Structure of the World: The World as Graph", Journal of Philosophy 94(7) (July): 329-358.
  
  "[T]he concrete world is a single, large structure
  induced by a single, two-place, symmetric relation,
  and thus best analyzed as a certain sort of graph."
5. Brian Hayes on graphs:
  - Thee articles should be available to the general public.
    If they are not, please let me know, and I will make copies available.
  1. Hayes, Brian (2000), "Graph Theory in Practice", American Scientist
    
    Part I, Vol. 88 (January-February): 9–13.
    Part II, Vol. 88 (March-April): 104–109.
  2. Hayes, Brian (2008), "Accidental Algorithms", American Scientist 96(1) (January-February): 9-13.
    - Discusses Eulerian and Hamiltonian circuits, and cites the work of former UB CS faculty member Jin-Yi Cai.
6. Hendler, James; Shadbolt, Nigel; Hall, Wendy; Berners-Lee, Tim; & Weitzner, Daniel (2008), "Web Science: An Interdisciplinary Approach to Understanding the Web", Communications of the ACM 51(7) (July): 60-69.
  - "One way to understand the Web…is as a graph whose nodes are Web pages (defined as static HTML documents) and whose edges are the hypertext links among these nodes." (p. 64.)
7. Special Issue on AI and Networks, AI Magazine 29(3) (Fall 2008).
  - Contains articles on applications of graph theory to artificial intelligence and the World Wide Web. In particular, the introductory article has a nice summary of elementary graph theory:
    - desJardins, Marie; Gaston, Matthew E.; & Radev, Dragomir (2008), "Introduction to the Special Issue on AI and Networks", AI Magazine 29(3) (Fall): 11-15.
8. Horrocks, Ian (2008), "Ontologies and the Semantic Web", Communications of the ACM 51(12) (December): 58-67.
  - Explains how graphs and relations can make the Web easier to use.
9. Massé, Blondin A.; Chicoisne, G.; Gargouri, Y.; Harnad, S.; Picard, O.; & Marcotte, O. (2008), "How Is Meaning Grounded in Dictionary Definitions?", in TextGraphs-3 Workshop—22nd International Conference on Computational Linguistics
  - Nice introduction to graph theory and its application to computationally representing and reasoning about the inevitable circularity in dictionaries.
10. Traveling Salesman Problem:
  1. Stern, R.J. (2008), Goldman's Theorem (Saga Books), isbn 978-1-897512-22-7.
    - A humorous, yet serious, novel about a mathematician who attempts to prove that the Traveling Salesman problem in graph theory can be solved in polynomial time.
  2. Schuessler, Jennifer (2012), "Willy Loman, Where Are You?", New York Times (15 March): C8.
    - Relates the TSP to Arthur Miller's classic play, Death of a Salesman. For online version, scroll down to "March 14 The Traveling Salesman Problem".
11. Hoffmann, Leah (2009), "The Networker", Communications of the ACM 52(10) (October): 112–111 (!).
  - Interview with Cornell University computer scientist (and Buffalonian) Jon Kleinberg "about algorithms, information flow, and the connections between Web search and social networks."
Trees
1. Tree examples (Fig. 10.1.2 from text)
2. The Tree of Porphyry
  - from John F. Sowa, Knowledge Representation (Pacific Grove, CA: Brooks/Cole).
  - English translation of Peter of Spain's (Pope John XXI's) version, also from Sowa.
3. Zimmer, Carl (2009), "Crunching the Data for the Tree of Life", Science Times, New York Times (10 February): D1,D3.
  - Discusses the role of computers in searching very large trees (such as the tree of all life forms).
Text copyright © 2008–2012 by William J. Rapaport
Cartoon links and screen-captures appear here for your enjoyment and are not meant to infringe on any copyrights held by the creators.
For more information on any cartoon, click on it, or contact me.
(rapaport@buffalo.edu)
http://www.cse.buffalo.edu/~rapaport/191/graphs.html-20120408