Posts Tagged ‘graph-theory’

Ways To Specify Things Precisely And Clearly

February 23, 2014

I am interested in hearing your thoughts on this:

Need Precision And Clearness

In work and in daily life it is important to be precise and clear. Mathematics is one way to achieve precision and clearness, if the problem is numerical in nature. However, there are many problems that require precision and clearness and are not numerical in nature. I think our educational system devotes too much time to mathematics as a way to express precision and clearness, and not enough time to the other means to express precision and clearness.

Allow me to explain please…

My Kitchen Has 10 Pieces Of Fruit

In my kitchen I always keep 10 pieces of fruit on hand. Of the 10 pieces of fruit I always have two varieties: bananas and oranges, pears and kiwis, etc. If I wanted to rigorously specify this, I could create a mathematical equation:

x + y = 10

where x represents one kind of fruit and y the other.

Equations are great for precisely and clearly specifying things that are numerical, such as the count of pieces of fruit in my kitchen.

Being able to specify things precisely and clearly is important. Mathematical equations are great for this: they are succinct, they are abstract (free of irrelevant details such as the fruit’s color, shape, and texture), and they avoid the clumsiness of the English language (“I have 10 pieces of fruit and of them I have two varieties” is clumsy compared to “x + y = 10“).

Non-Numerical Problems Need Precision And Clearness

Not everything that we want to specify precisely and clearly is numerical. For instance, it would be useful to precisely and clearly specify the format of a Web page (i.e., HTML): an HTML document must have html at the beginning (the root element) and it must contain a head element followed by a body element; the head must contain zero or more meta elements and a title element, and so forth. Some very smart people have developed a succinct, precise way of specifying the HTML format, using something called a “BNF grammar.”  A BNF grammar contains “rules” and each rule specifies the content of each element, e.g.,

<html> ::= <head> <body>
<head> ::= <meta>* <title>
<body> ::= …

That notation might look strange. That illustrates my point. Here we have something that is non-numerical and needs a precise and clear specification. The BNF grammar notation is something that our educational system should expose to students early in their education.

Students need to see that (1) things need to be specified precisely and clearly, (2) not everything is numerical, and (3) non-numerical things can be expressed as precisely and clearly as numerical things.

There are many other non-numerical things that would benefit from a precise and clear specification. For example, think about the shipping requirements of Fedex and UPS. In order to ship a package from point A to point B it may have to go through point C. But if point C is unavailable (heavy snow storm there) then the package needs to be re-routed to point D and then E. You get the idea. A precise and clear specification of the routing problem is needed. It is not a numerical problem and so mathematical equations are of limited use. Some very smart people have developed a succinct and precise formalism for this type of thing, called graphs. I won’t go into an explanation of them. The point to be made here is that this is another example of a non-numerical problem for which we need precision and clearness, and students should learn at an early age these formalisms.

Summary

Mathematical equations are great for expressing numerical problems precisely and clearly. Our educational system exposes students early to this way of specifying problems. But there are other problems that are not numerical, require precision and clearness, and for which ways have been created for  specifying them. I think that our educational system should expose students early to these other ways. I think that by the time a student is 10 years old he/she should have been exposed to BNF grammars, graph theory, Turing machines, finite automata, and probably several other things.

Tags:, , , , , , , , , , , , ,
Posted in Uncategorized | Leave a Comment »

Learning for the sheer love of it … determining the number of edges in a complete graph

September 7, 2013

As I noted in an earlier blog, even little discoveries makes one feel wonderful. Today I solved a small problem (i.e., made a little discovery) and I feel wonderful.

I am reading a wonderful book, Introduction to Graph Theory. I am at the part where it describes complete graphs. A complete graph is one where each vertex is connected to every other vertex. The author asks, How many edges are in a complete graph with N vertices? I took this as a challenge to use my reasoning skills to figure it out.

Here are three examples of complete graphs and the number of edges in each graph:

Three examples of complete graphs and the number of edges in each graph

Let’s arbitrarily choose one vertex. It must connect to the other (n-1) vertices. For example, in the complete graph with 4 vertices, the vertex will connect to the other 3 vertices:

A vertex connects to n-1 other vertices

The remaining vertices must form a complete graph amongst themselves. Ah Ha! Now we have a simpler problem: find the number of edges in a complete graph of n-1 vertices.

I now switch on my programmer hat. I smell recursion (which I love):

numEdges (N) {
    if (N == 2) then return 1
    else return (N-1) + numEdges (N-1)

Let’s check that program:

if N = 2, then num edges = 2
if N = 3, then num edges = 2 + 1 = 3
if N = 4, then num edges = 3 + 3 = 6
if N = 5, then num edges = 4 + 6 = 10
if N = 6, then num edges = 5 + 10 = 15
if N = 7, then num edges = 6 + 15 = 21
if N = 8, then num edges = 7 + 21 = 28

Wow! That is cool.

One problem, however. What are the number of edges when, say, N = 1000?

I could implement the above program and set it to solve N=1000. But I know the mathematicians would tell me: Find a formula.

Okay, let’s see … to find the number of edges in a complete graph with N vertices, I must add these numbers:

(N-1) + (N-2) + (N-3) + … + 1

or equivalently:

1 + 2 + … + (N-1)

I remember from school days a formula for the sum of the first N integers:

n(n+1)/2

Of course, I want the sum of the first N-1 integers, so I substitute “n” with N-1:

(N-1)((N-1)+1)/2
= (N-1)(N-1+1)/2
= (N-1)(N)/2
= N(N-1)/2

Let’s check:

if N = 2, then 2(1)/2 = 1
if N = 3, then num edges = 3(2)/2 = 6
if N = 4, then num edges = 4(3)/2 = 6
if N = 5, then num edges = 5(4)/2 = 10
if N = 6, then num edges = 6(5)/2 = 15
if N = 7, then num edges = 7(6)/2 = 21
if N = 8, then num edges = 8(7)/2 = 28

Yea!

I am pretty proud of myself. I solved it, not because it was a homework problem or a work problem. I solved it purely for the love of learning. I figured it out by simple reasoning.

I feel wonderful.

Tags:, , , , , , , ,
Posted in Uncategorized | Leave a Comment »