GRAPH Course

Introduction

A graph $G$, is a set of vertices (=nodes=sommets/nœuds) $V$ linked by edges (=links=arêtes) $E$ giving us the notation $G(V, E)$. Vertices can have a direction or not.

Graph - example

You will use graphs in databases in GraphDatabase, check the NoSQL course if that was what you are looking for. You may also use it to solve scheduling problems using P.E.R.T. in the project management course.


Kinds of graphs

A graph can be simple/multiple and directed or not.

  • simple graph (graphe simple): up to one edge between two vertex (2 if "directed graph") and no loop/self-edges.
  • multiple graph (graphe complexes): graphs that are not simple
  • undirected graph (Graphe non orientés (GNO)): edges do not have a direction, they are written $(a,b)$
  • directed graph (Graphe orientés (GO)): edges, called arcs, have a direction, they are written $[a,b]$
undirected graph directed graph description
edge
arête
arc
arc
The keyword for edges in changing if the graph is directed or not.
chain/walk $P_n$
Chaine
path/trail $P_n$
chemin
Each vertex degree is 2 aside from the extremities (degree=1). If the graph is directed, we must be able to go from one extremity to the other.
cycle/tour $C_n$
cycle
circuit $C_n$
circuit
Each vertex degree is 2. This is also called "closed walk/path/...". If a graph does not have cycles, then the graph is acyclic.
star $S_n$
étoile
star $S_n$
étoile
One vertex degree is $|V|-1$ and the others are of degree $1$. We got a vertex linked to every other vertex.
wheel $W_n$
roue
wheel $W_n$
roue
One vertex degree is $|V|-1$ and the others are of degree $3$. It's a vertex linked to all other vertices and each vertex is linked to two aside from the center of the wheel.
butterfly/hourglass
papillon
butterfly/hourglass
papillon
One vertex degree is $|V|-1=4$ and the others are of degree $2$. The graph is make of $6$ edges and $5$ vertices.

Note: the degree is the number of neighbors, see next part.


Terminology

I marked with a little star *, the keywords that we are not using often (and that you may learn later).

name description
adjacent/neighbor
Adjacent/Voisins
Two nodes are adjacent if they are linked by an edge.

The notation is $N(X)$ or $\Gamma(X)$ (gamma) for the adjacent nodes of X. With arcs, we use$N^{+}(X)$ (arc entering/arriving, in-degree) and $N^{-}(X)$ (arc exiting, out-degree).
degree
Degré
The number of neighbors.

The notation is $d(X) = |\Gamma(X)|$. In a directed graph, this is $|\Gamma^{+}(X)| + |\Gamma^{-}(X)| = d^+(X) + d^-(X)$. (called demi degré extérieur/prédécesseur (entrants) and demi degré intérieur/successeur (sortants)).
incidence
incidence
A vertex is incident to an edge if they are linked.
order
ordre
The number of vertices, $|V|$, $|V(G)|$ while the cardinal $|V|$ (=the number of elements of a set V) can also be noted, $\#V$ or $Card(V)$.
density*
Densité
This is the number of edges of our graph divided by the number of edge of the complete graph (see below).

You may also note that, if we have an arc $A \to B$, then

  • $A$ is the predecessor of $B$ (prédécesseur)
  • $B$ is the successor of $A$ (successeur)

There are names for graphs having some properties

name description
closed path*
cycle/chaine élémentaire
A cycle/circuit in which each traversed vertex is only traversed once. If the use of path is disturbing for you, then read the RandomFolkNote at the end of the course.
d-regular graph
Graphe k-régulier
A regular graph or d-regular graph is a graph where all degrees have the same value (d, for instance, 3-regular graph).
complete graph $K_n$
Graphe complet
Each and every vertex is adjacent to all other vertices aside itself, giving us $|V| = \frac{n(n-1)}{2}$.
bipartite graph $K_{a,b}$
Graphe bi-parti
We can split the vertices into 2 groups: the group having a degree a and the group having a degree b with $b > a \ge 1$. Each vertex in the first group must be adjacent to $a$ vertex in the second (resp. second group and $b$).
subgraph $G'$
Sous-graphe/Graphe induit
$G'$ is a subgraph of $G$ if we only removed $G$ vertices and their incident edges (like you can't remove an edge alone).
clique
Clique
A clique is a complete subgraph.
Complement/inverse*
Complémentaire
The complement of a graph is a graph in which we are creating all the edges that didn't exist while removing the existing ones. Like if we have $A-B-C$ then the complementary graph would be $A-C\hspace{.5cm}B$.
isomorphism*
Isomorphe
Let two graphs $G$ and $H$. If we can move some nodes and get the same graph, then there is an isomorphism. More formally, if there is a bijection between them, then there is an isomorphism.

You may do these exercises: exercises.


Advanced Terminology


Sorting and search

You can sort a graph using

You can search a graph using

And you can solve the problems of passing once by an edge/a vertex with


Graph coloring problems

You will try to color a graph (vertex/edges) will the least colors.

What you learned here is very similar to the notion of an independent set. In fact, you can use Grundy to find a coloration. I do not know why we learned those separately. Look for Grundy number or Grundy chromatic number.

A graph coloring problem could be something like "A, B, C, D, E" must pass some tests, but they can't be in the same room for the same test. We are giving you a table of which tests they are passing, and your goal is to find the minimum of rooms needed. You can also have a similar problem like "A, B, C, D, E" can't be in the same room (you got a table of which one can't be with which one) and you have to find at least how many rooms are needed (make a graph of which can't be with which and solve it).


Trees

A tree is a graph having one of these properties (they are equivalent)

  • connected and acyclic (=no cycles)
  • one path between two nodes
  • connected but would be disconnected if we are removing a vertex
  • acyclic but would be cyclic if we are adding one vertex
  • connected and $|E| = |V| - 1$
  • acyclic and $|E| = |V| - 1$

And here are new notions for trees


The shortest path problem

You have 4 algorithms explained here (out of 6)


Scheduling problem

In French, it's called Ordonnancement. You are given

  • a list of tasks and their dependencies (like a task need another one to be done first)
  • the duration of each task

And your job is to create the best schedule, meaning that you must find the best way to organize the tasks making the project the shorter possible (it's not only used in projects).

Here, we are considering that we can execute an unlimited number of tasks in parallel, and we do not take delays into account, so it's a simplified version of scheduling's problems.

You should have noticed, but our two methods are giving the same result (same critical path, same optimal duration, ...). This is a way of checking that you did things right. Note that there will be some differences with the early_start/last_start values.


The random folk note

I don't know how should I interpret this, but French and English do not seem to agree on the terminology. I'm a bit confused, but I'm not changing the course content.

They are using walk for chaine/chemin, but

  • "A trail is a walk in which all edges are distinct" wiki
  • "A path (Chemin) is a trail in which all vertices are distinct" wiki
  • you add directed if needed like "directed path" wiki
  • Chain (chaine) is a synonym for a walk wiki

They are using closed walk for cycle/circuit, but

  • "A cycle (cycle) may either refer to a closed walk (also called a tour)" wiki
  • "A tour may either refer to "a closed trail (also called a walk)" wiki
  • "A circuit (circuit) may refer to a closed trail" wiki

Sources

This is a list of all Wikipedia pages that you may want to check

Search, Scheduling methods, ...

Trees

Shortest path problem

other references