Re: Graph Theory

Thread:
JA:http://web.archive.org/web/20140301040001/http://permalink.gmane.org/gmane.science.philosophy.peirce/12012
JA:http://web.archive.org/web/20140306031229/http://permalink.gmane.org/gmane.science.philosophy.peirce/12016

Peircers,

Graph theory is a beautiful subject — and a handy tool to boot.  If you call it “pure” in theory and 
“impure” in practice, graph theory does not mind — purity is in the eye of the beholder, after all.

Peirce remarks somewhere on the character of mathematical practice that one is constantly having to 
return from diverse and sundry distractions to the first principles of definitions and axioms, and 
to start again from those points of relative, never absolute settlement.  Or something like that.

The best way to proceed from here is to go back to the definition of a graph, to make sure we 
understand a reasonable portion of what it implies, and then to go from there.

<quote>

A ‘graph’ G consists of a finite nonempty set V = V(G) of p ‘points’ together with a prescribed set 
X of q unordered pairs of distinct points of V.  Each pair x = {u, v} of points in X is a ‘line’ of
G, and x is said to ‘join’ u and v.  We write x = uv and say that u and v are ‘adjacent points’ 
(sometimes denoted ‘u adj v’);  point u and line x are ‘incident’ with each other, as are v and x. 
If two distinct lines x and y are incident with a common point, then they are ‘adjacent lines’.
A graph with p points and q lines is called a ‘(p, q) graph’.  The (1, 0) graph is ‘trivial’.

</quote> Harary, ‘Graph Theory’, p. 9.

As I pointed out, the part that defines a graph is really just the first sentence:

“A ‘graph’ G consists of a finite nonempty set V = V(G) of p ‘points’ together with a prescribed set 
X of q unordered pairs of distinct points of V.”

Concrete examples do yeoman service in abstract subjects, and so I constructed one to fit the 
definition:

Let us take a finite nonempty set of points

V = {a, b, c, d, e}

together with a set

X = {x1, x2, x3, x4, x5, x6, x7}

of unordered pairs of distinct points of V,
say as prescribed below:

x1 = {a, b} = ab
x2 = {b, c} = bc
x3 = {c, d) = cd
x4 = {d, e} = de
x5 = {e, a} = ea
x6 = {a, d} = ad
x7 = {c, e} = ce

Then that is an example of a graph.

We can draw a picture of that graph as follows:

  ```````````````````````````
  `````````````b`````````````
  `````````````o`````````````
  ````````````/`\````````````
  ```````````/```\```````````
  ````````a`o`````o`c````````
  ``````````|\```/|``````````
  ``````````|`\`/`|``````````
  ``````````|``\``|``````````
  ``````````|`/`\`|``````````
  ``````````|/```\|``````````
  ````````e`o-----o`d````````
  ```````````````````````````

My school of graph theorists call that a “diagram” of the graph,
and it is possible to draw many such diagrams for the same graph.

To be continued ...

Jon

-- 

academia: http://independent.academia.edu/JonAwbrey
my word press blog: http://inquiryintoinquiry.com/
inquiry list: http://stderr.org/pipermail/inquiry/
isw: http://intersci.ss.uci.edu/wiki/index.php/JLA
oeiswiki: http://www.oeis.org/wiki/User:Jon_Awbrey
facebook page: https://www.facebook.com/JonnyCache
_______________________________________________
Inquiry mailing list
[email protected]
http://stderr.org/cgi-bin/mailman/listinfo/inquiry