Je te donnes tout de suite 3 nouveaux sujets pour que tu aies le temps de préparer ton Meetup.
Exercice n°1 (difficult)
An undirected graph is called
biconnected
if for every pair of nodes
u
and
v
there are two node disjoint paths between
u
and
v
. To disconnect a biconnected graph you need to delete at least two nodes. The
biconnected components
of an undirected graph are its maximal biconnected subgraphs.
Theorem:
any biconnected graph can be
st-Numbered
.
Exercice:
given a biconnected graph return its
st-Numbering
(
here is one possible algo description
).
Note:
the
st-Numbering
is used by numerous graph-drawing algos.
Exercice n°2 (hard)
Exercice:
given an undirected graph return its
modular decomposition
.
Note:
the
modular decomposition
is used by some graph-drawing algos and various graph preprocessings.
Exercice n°3 (easy)
Exercice:
given two directed graphs return their
categorical product
.
Note:
the
categorical product
is used when computing the
least
generalization
of two Entity/Relation graphs.
Good Luck!
|