A Summer 2015 Mathematics A To Z: vertex (graph theory)


I mentioned graph theory several weeks back, when this Mathematics A To Z project was barely begun. It’s a fun field. It’s a great one for doodlers, and it’s one that has surprising links to other problems.

Graph theory divides the conceptual universe into “things that could be connected” and “ways they are connected”. The “things that could be connected” we call vertices. The “ways they are connected” are the edges. Vertices might have an obvious physical interpretation. They might, represent the corners of a cube or a pyramid or some other common shape. That, I imagine, is why these things were ever called vertices. A diagram of a graph can look a lot like a drawing of a solid object. It doesn’t have to, though. Many graphs will have vertices and edges connected in ways that no solid object could have. They will usually be ones that you could build in wireframe. Use gumdrops for the vertices and strands of wire or plastic or pencils for the edges.

Vertices might stand in for the houses that need to be connected to sources of water and electricity and Internet. They might be the way we represent devices connected on the Internet. They might represent all the area within a state’s boundaries. The Köningsburg bridge problem, held up as the ancestor of graph theory, has its vertices represent the islands and river banks one gets to by bridges. Vertices are, as I say, the things that might be connected.

“Things that might be connected” is a broader category than you might imagine. For example, an important practical use of mathematics is making error-detecting and error-correcting codes. This is how you might send a message that gets garbled — in sending, in transmitting, or in reception — and still understand what was meant. You can model error-detecting or correcting codes as a graph. In this case every possible message is a vertex. Edges connect together the messages that could plausibly be misinterpreted as one another. How many edges you draw — how much misunderstanding you allow for — depends on how many errors you want to be able to detect, or to correct.

When we draw this on paper or a chalkboard or the like we usually draw it as a + or an x or maybe a *. How much we draw depends on how afraid we are of losing sight of it as we keep working. In publication it’s often drawn as a simple dot. This is because printers are able to draw dots that don’t get muddied up by edges being drawn in or eraser marks removing edges.

Reading the Comics, January 11, 2015: Standard Genres And Bloom County Edition

I’m still getting back to normal after the Christmas and New Year’s disruption of, well, everything, which is why I’m taking it easy and just doing another comics review. I have to suppose Comic Strip Master Command was also taking it easy over the holidays since most of the subjects are routine genres — word answer problems, mathematics-connected puns, and the like — with the Bloom County reruns the cartoons that give me most to write about. It’s all part of the wondrous cycle of nature; I’m sure there’ll be a really meaty collection of topics along soon.

Gordon Bess’s Redeye (January 8, originally run August 21, 1968) is an example of the student giving a mischievous answer to a word problem. I feel like I should have a catchy name for this genre, given how much it turns up, but I haven’t got anything good that comes to mind. (I don’t tend to talk about the drawing much in these strips — most of the time it isn’t that important, and comic strips have been growing surprisingly indifferent to drawing — but I did notice while uploading this that Pokey’s stance and expression in the first panel is really quite good. You should be able to open the image in a new tab and see it at its fullest-available 1440-by-431 pixel size and that shows off well the crafting that went into the figure.)

'If you had six apples and I came along and took five of them, what would that leave you with?' 'A Paleface peace treaty?'
Gordon Bess’s Redeye for the 8th of January, 2015; originally run the 21st of August, 1968.

Continue reading “Reading the Comics, January 11, 2015: Standard Genres And Bloom County Edition”