Discrete Structures

Graph and Trees

Last Update: 12 January 2010

Note: NEW or UPDATED material is highlighted

  1. Graphs

    1. 7 Bridges of Königsberg (from Rosen)

    2. A Set-Theoretical Definition of Graphs

    3. Tymoczko, Thomas (1979), "The Four-Color Problem and Its Philosophical Significance", Journal of Philosophy 76(2) (February): 57-83.

        Also see:
      • 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. Hayes, Brian (2008), "Accidental Algorithms", American Scientist 96(1) (January-February): 9-13.

      • This article should be available to the general public. If it is not, please let me know, and I will make a copy available.

      • 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:

    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. 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.

    11. NEW
      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."

  2. Trees

    1. Tree examples (Fig. 10.1.2 from text)

    2. The Tree of Porphyry

    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).


    Copyright © 2008–2010 by William J. Rapaport (rapaport@buffalo.edu)
    http://www.cse.buffalo.edu/~rapaport/191/F09/graphs.html-20100112