A bit of theory on Graphs

Please forgive me!

What's about to follow may seem a bit... stomach torching?

But mathematics is all about precision and (sometimes) a bit of placing-cards-on-deck-faced-up.

And graphs are too a nice subject to leave them out in the fog. Yes, they devise a tiny, crank description. I try. If you would like to change/add, I'm more than happy!

So, what a "graph" is?

I could answer intuitively, but will not. Rather, will give the full definition (and hope any "true mathematician" will forgive my sloppiness) (there is, as I told, a lot of space to make things better and better).

So. A "graph" is an instance of "mathematical structure". Quite abstract.

There are two species of graphs, "directed" and "undirected".

An "undirected graph" is an ordered couple G = (V,E) of a (usually finite, and surely nonempty) set V of "vertices", and a set E of "edges". Edges themselves are two-element sets of vertices.

Let's see an example (as it's always better). Imagine V = {1,2,3} is made of just three vertices. Now, let's assume E = { {1,2}, {2,3}, {3,1} }. The graph G=(V,E) in this case is a triangle.

But also G=(V,E) with V = {1,2,3} and E = { {1,2}, {1,3} } is a graph: in this case, the vertex "1" acta as a sort of hub connecting "2" and "3".

"Directed graphs" are similar to undirected graphs, but now the "edge set" is not made of two-element sets, but rather by ordered couples (or two-components vectors if you like). This tiny replacement has interesting consequences: first of all, if {1,2} is a set containing the vertices "1" and "2", {2,1} is the same set: what matters in a set is which elements are in, not their order. So, if {1,2} is an edge, {2,1} is the same edge written differently (it is this, to make the graph "undirected").

With ordered couples, it's all different. (1,2) is not the same things than (2,1). Conventionally, the first case is represented through an arrow starting at "1" and reaching "2". The second case is just opposite. A direct graph might be G = (V,A) with V = {1,2,3} and A = {(1,2), (1,3), (2,3), (3,2), (1,1)}.

Have you noticed it? In our last example there is a couple (1,1) joining a vertex with itself: this is perfectly legitimate, and has even a name: "self loop".

Of course, in a undirected graph you would find no self-loops. Why? Just because {1,1} is not a two-element set! In sets, repetitions are not admitted, so writing {1,1} is just a very cumbersome (and little wrong) way of writing {1}: a one-element set! But, being just one-element, this can not be an "edge"!

Directed graphs are very common in engineering, and allow a somewhat more detailed treatment than undirected graphs. They also have their own special terminology (for example, "edges" are commonly named "arcs" in directed graphs).

But if we want to model relationships, we can assume all the ones relevant are reciprocal, and we can limit to undirected graphs.

(Well, human relationships are not as trivial. Concepts like "non-corresponded love" or "hatred for oneself" are not easy to model with an undirected graph... But we know, mathematicians love "simple" models. Beware!)

OK. We now know what a "graph" is. We may deal with important properties.

Maybe, the first important graph property is connectedness. The concept is very intuitive: a connected graph has no isolated vertices, or group of vertices. But, how to express this in a logical way?

The answer is through the concept, also important, of "path".

A path joining two vertices u and v is a sequence of edges e1, e2, ..., en (possibly formed by just one edge, or even none at all if u and v coincide), where

e1 = {u,a1}, e2 = {a1, a2}, ..., en = {am, v}

Now: a graph is connected if any two vertices are joined by (at least) a path.

In our former case, G=(V,E), V={1,2,3} and E={{1,2},{1,3}}, it is easy to see any two vertices are joined by a path. Even 2 and 3, in which case a path is {2,1}, {1,3}.

And what of this? G = (V={1,2,3}, E={{1,2}}).

This is an unconnected graph: the vertex 3 is connected to 1 by no vertex.

Connected graphs may be turned into unconnected by pruning one or more edges. That of pruning some edge at random, and checking whether the graph is still connected, is a test with important practical applications, for example to assess the robustness of an electric distribution network (often modeled as an undirected graph).

The planetary ecosystem is an example of big network, which can be modeled through a (very large) graph. Is it connected, or not?

Basic ecological evidence shows that yes, it "is" connected. But also, it is composed by highly connected sub-graphs linked by relatively few "key" edges. A lot of life, for example, occurs in correspondence of "black smokers" close to oceanic ridges, based on a chemistry entirely different from the photosynthesis-based one we are accustomed to. These communities are not completely separated from others, but connections occurs through occasional predation, or other very rare event. Or not? Maybe, some huge connection exists, but we are still too ignorant to notice!

What could it happen to the ecosystem if we remove at random some edge or, worse, vertex? (This is what happens now! Our species is driving to extinctions many others, at a rate larger or comparable to the one seen during the Cretaceous-Tertiary or the Permian-Triassic mass extinction events)

Will the ecosystem sooner or later disconnect and collapse?

Maybe "not". Life is highly resilient. But nothing guarantees we are not able to disconnect the little part of the ecosystem made by Homo sapiens, corn, rats, cows, ..., from the remaining biosphere. If we are not attentive, we may easily fall prey of the same mass extinction we are fostering.

Paths are non unique, usually. If E = {{1,2}, {2,3}, {1,3}}, then 1 connects to 3 both directly by a single edge {1,3}, and indirectly through the chain {1,2}, {2,3}.

When two vertices are joined by more than one path, then, inevitably, some path among the many will have a minimum length. These minimal paths may also be non-unique. But, they are much less that the total number of paths.

The minimum path length allows to define a sort of "diameter" of a graph, as the largest length of minimal paths connecting any two vertices. Intuitively, as we prune edges from a formerly connected graph, its diameter increases... Until it splits in separate components, loosing the property of connectedness.

The length of the minimal path connecting two vertices is a sort of "distance" ("closeness", if you like). This is where the theory of the six degrees of separation comes from. In human communities, any two people are very close if edges are used to represent acquaintances. Six seems to represent a sort of worse-case, when people are really chosen at random. But if they, say, share the same nationality, their distance is most likely to be two, or less (they both are likely to "know" some shared famous "hub" individual, like a politician, or a common friend).

Undirected graphs are very god models of the "popularity based assembly" common among girls... in which case, the graph in addition of being huge is also very "fluid", with edges forming and vanishing quickly among a set V made by more or less the same individuals.

Is "true friendship" graph more stable than this?

And what of "best friendship" graph? In this case in addition to stability (some best-friendship relations survive decades), any individual is connected by very few others. But, is this graph still connected, as a whole? How "vulnerable" it is to some relationship removal?

There is matter for some other post, to just go on...

But for the moment, allow me to stop here! It's seven o'clock in the morning, and I have not yet prepared myself to go work - let alone my home...

So, see you soon! With some other "sproloquia".

Mauri