So, tonight's lecture will be about graph theory. First, an elementary definition of a graph. A graph is a symbolic representation of a network. It is an abstraction of the reality so that it can allow its model ization. qwertydawom> in fact i'm on the phone too lol that explains the fact that i'm a bit slow :/ ^^ lol well, im still here.. In geography of travellings, most of the networks have a spatial b asis, but this is not true for all the travelling networks. For example, it is possible to represent a telecommunication syste m as a network although its spatial expression has a limited importance and woul d be difficult to transpose on a territory. The examples of cell phones or the internet show the cases of netw orks with limited spatial structure. Still, most of the travelling networks can be represented thanks t o graph theory. So, first of all, we are going to define the main elements of a gr aph. But, before this, I want you to read what was the first example of graph theory, namely, the seven bridges of Konigsberg problem : http://en.wikipedia.org/wiki/Seven_bridges_of_K%C3%B6nigsberg . so, did you read it? :qwertydawom!qwertydawo@RDR-F1A64CEF.fbx.proxad.net MODE #lecture -m yeah ok So, for the definitions : read it before -Graph : A travelling network, as any network, can be represented as a grap h. A graph G consists in a set of nodes v and of arcs e. Hence, we'll denote, G = (v, e). -Vertice (node) : A vertice v is a point of extremity or an intersection point of a graph. It is an abstraction of a place, such as a city, a crossroads or a structure of exchanges (such as airports etc.). -Arc : An arc e is a link between two vertices. (ahem, sorry, plural = vertices; singular = vertex :/) it's okay :) The arc (i, j) is characterized by an initial vertex i and a termi nal vertex j. An arc is an abstract representation of infrastructures of support of movings between two nodes. Finally, an arc has a direction, often symbolized by an arrow. Now, to see if you got it, can someone draw (quickly, on paint or similar) the representation of the following graph : G = (v, e) v = (1,2,3,4,5) e = (1,2), (1,3), (2,2), (2,5), (4,2), (4,3), (4,5) ? aren't arcs vectors only in directed graphs? *oriented yep btw, directed is OK ;) ah excellent := :) or, to be shorter (lazyness.. :P), you can even say "digraphs" :) long live laziness :D hehe yep :) so, um, did anyone draw this graph? yep looks weird though show me? :) perhaps i didn't place the vertices in the best places anyway aha actually... i'll modify it :) yep looks good now show me? :) <-- me too ;P i hate how big bmps are in fact, if you could imageshack it, I guess it'd be perfect ;) i'll jpeg it png? use open source :D helo heya hi there :) much better :D riftor: ! (it's SysSpider here) :) hey man http://sysspider.vectorstar.net/misc/graph.jpg @riftor, the exercise was the following : sorry i've been quieter lately, back at work, things are busy and I was away in Rome for almost a week with IBM Now, to see if you got it, can someone draw (quickly , on paint or similar) the representation of the following graph : G = (v, e) v = (1,2,3,4,5) e = (1,2), (1,3), (2,2), (2,5), (4,2), (4,3), (4,5) ? oky oh that's cool qwertydawom: checked my drawing? yep, seems good in fact, it could have been even simpler :) undirected? a single line? are we going for (1,2) as being the ordered tuple for a directed graph directed, but yeah, he's forgotten the arrows or being like {1,2} okay no@single_line ok, let me draw this ;) ok i'll think in the meanwhile oh i think i got it let me try an envelope without one of the arcs yes, i think you've got it my drawing : http://img372.imageshack.us/my.php?image=digraph16zz. png http://sysspider.vectorstar.net/misc/graph.jpg <-- different after a ll but (even if i forgot the arrows, it seems ok) bah no nvm no it's not good (4, 5) doesn't exist oh actually it's the 4, 3 yep that i forgot so it'd be the same after all or almost brb yes ok forgive my ignorance, but what exactly makes that better or worse than th e first one? :P other than the fact that one of the lines is missing, of course first one = ? qwertydawom, I mean... why did he rearrange the vertices? aesthetical reasons that's it? and also, vertices are better placed when they're not inside the fig ure no yep yes ah, ok i ain't being a pretty good uncle paul am i? ;P :) ok, so let's go on with the definitions : -Subgraph : A subgraph is a subset of a graph G where p is the number of subgr aphs. As an example, G' = (v', e') can be a distinct subgraph of G. In the previous graph G, p = 1. If the arcs (1, 2) and (4, 3) (apparently, SysSpider already thoug ht of that :P) were to disappear, then p would be equal to p=2. :P Unless we consider the global travelling system as forming an "all ", each travelling network is, in theory, a subgraph of another. -Loop : There is a loop when an arc makes the correspondance with a same v ertex. (2, 2) is a loop. Now, we are going to see the links and attributes of a graph. Actually, I'm just going to mention the words, as they're quite se lf-definable : edge, path, cycle. If you don't get what the meaning of one of these words could be, just ask. isn't edge == arc? nope arc --> direction edge --> no orientation in other words, an arc is a directed edge :) ah ok now, if everything is ok, let's move on we are going to see how to describe a graph Symmetry and asymmetry : A graph is symmetric when each pair of vertices connected in one w ay is also connected in the other way. Connectedness : A graph is said to be connected if for every pair of distinct vert ices there exists a string that connects them. The direction has no importance for a graph to be connected. If p>1 the graph is not connected because it has more than one sub graph. Complete (graph) : A graph is complete if any two vertices are connected in at least one direction. so a triangle represents a complete undirected graph exactly :) now, can you generalize your statement? i'm trying for any convex polygon is that what you mean? although it's not true for e.g. a square indeed well with the triangle, you had 3 vertices in general, how many vertices will a complete graph have? an odd number? 1, 3, 5, 7, ... nope you can define it for all n so if the complete graph has n vertices how many edges will it have? for the triangle it's n, but not for the complete "square" yep try with n=1, 2 0, 1, 3, 8 no@8 i mean, 8 for n = 5 let me check for 4 6? no@8 :) yep, 6 for n=4 and it's not 8 for n = 5? no, it's not 10? but still, don't 1, 3, 6 ring a bell? 1, 3, 6... it does triangular numbers? exactly! :D i knew it was familiar :P yes@10 ;) hehe :) i think i actually read about this in my childhood :) about the properties of triangular numbers i think my head hurts it was presented as a problem concerning handshakes, where everyone cumpliments the others so, actually, the number of edges of a complete graph with n verti ces is n(n-1)/2 ah, yes, I see sorry missed a bit no problem but actually, now that the definitions are all(?) done and clear(? ), I guess we'll stop so that no more heads start to hurt :p and, next time, we'll continue on graphs