 |
2. LES GRAPHES TEMPORELS |
Dans le premier chapitre, nous avons exposé quelques problèmes de synchronisation
hypermédia (inter-média plus précisément) liés à la
réalisabilité et à l'optimisation d'une planification pour la
présentation synchronisée d'objets multimédia. Nous présentons ici une
modélisation sous forme de graphe. Celle-ci ne permet pas de représenter toutes les
spécifications désirées par les auteurs de documents hypermédia
synchronisés, mais tente néanmoins d'en rassembler les principales. Travaillant en
collaboration avec les concepteurs d'HyperProp (cf. [Soares00]), le
choix des spécifications à prendre en compte dans notre modélisation a
fortement été guidée par leurs besoins.
Mais avant d'étudier cette modélisation, il nous semble nécessaire de
consacrer une section à l'introduction de notions et de propriétés
élémentaires sur les graphes indispensables pour la compréhension du document
et éventuellement pour intégrer les algorithmes des prochains chapitres dans un
logiciel de conception et/ou de présentation de documents hypermédia
synchronisés. Après quelques rappels très généraux sur les
graphes, nous introduisons les notions de flot et de tension. Nous verrons dans les
chapitres suivants qu'une relation très forte entre le flot et la tension, la
dualité, joue un rôle très important dans les méthodes de
résolution que nous présentons.
Après cette introduction, nous présentons la modélisation sous forme de
graphe retenue, et précisons les restrictions qu'elle impose. Nous montrons ensuite que les
problèmes de synchronisation hypermédia peuvent ainsi être
considérés comme des problèmes de tension dans un graphe. En particulier, nous
discutons de la pertinence des problèmes de la tension compatible et de la tension
de coût minimal pour l'aspect hypermédia, et pour lesquels nous présentons
des méthodes de résolution dans la seconde partie du mémoire. Nous exposons
finalement différentes manières de mesurer la qualité d'une planification qui
semblent significatives pour les auteurs de documents hypermédia, toutes ne seront pas
abordées par la suite.
|
2.1. INTRODUCTION AUX GRAPHES |
|
Cette section nous a semblé nécessaire pour rassembler les notions de base
concernant les graphes. Le lecteur novice dans ce domaine y trouvera tous les
éléments indispensables au suivi des chapitres suivants du mémoire. Pour le
lecteur plus confirmé, il est possible d'utiliser cette section comme
référence pour une définition ou un théorème.
En complément, nous proposons également un annexe qui regroupe des algorithmes
dont le détail est jugé peu important dans le flot de nos réflexions, mais
néanmoins utile notamment pour l'interprétation et la reproduction des
résultats numériques. Cette section introduit aussi quelques propriétés
nécessaires pour la génération aléatoire de problèmes pour nos
jeux d'essais dont les principaux algorithmes sont détaillés dans l'annexe.
Une remarque importante sur la notation employée tout au long de ce document: les
fonctions dont le domaine de définition est discret et fini (e.g. un ensemble d'arcs ou de
noeuds) seront souvent utilisées comme des vecteurs. Ainsi une fonction
pourra être considérée comme un vecteur
dont les composantes seront notées
.
|
2.1.1. Notions élémentaires |
|
Pour illustrer les définitions présentées ici, nous allons utiliser le
graphe représenté par la figure 2.1, noté
, où
est l'ensemble des noeuds et
est l'ensemble des arcs. Nous notons
le nombre de noeuds de
et
le nombre d'arcs.
Ce graphe est orienté, cela signifie qu'une distinction est faite entre les deux
extrémités (i.e. les noeuds) d'un arc. On appelle noeud origine le noeud
d'où part l'arc et noeud destination le noeud où arrive l'arc. Ainsi pour un
noeud
, on appelle arcs entrants tous les arcs ayant
pour noeud origine et arcs sortants tous les arcs ayant
comme noeud destination.
Nous désignerons souvent un arc
de source
et de destination
par le couple
, bien que cette notation soit abusive dans la mesure où plusieurs arcs peuvent
avoir même origine
et destination
. Dans un tel cas
est appelé un arc multiple. Un multigraphe est un graphe
possédant au moins un arc multiple.
On désignera par sens direct l'utilisation d'un arc dans le sens
origine-destination et par sens indirect son utilisation dans le sens destination-origine.
 |
|
Figure 2.1: Un exemple de graphe. |
Le degré sortant, noté
, d'un noeud
est le nombre de ses arcs sortants et son degré entrant, noté
, est le nombre de ses arcs entrants. Le degré d'un noeud est la somme de
ses degrés sortant et entrant. Un noeud dont le degré entrant est nul est
appelé noeud source du graphe. De même, un noeud dont le degré sortant
est nul est appelé noeud puits du graphe.
|
2.1.1.2. Chaîne et chemin |
On dit que deux arcs sont adjacents s'ils ont au moins une extrémité (le
noeud origine ou le noeud destination) en commun. Un noeud est adjacent à un arc s'il
est au moins l'une des deux extrémités de l'arc.
On désigne par chaîne une succession d'arcs
dans un graphe telle que deux arcs consécutifs dans la chaîne sont
adjacents dans le graphe. Si l'on considère une chaîne
, on notera
l'ensemble des arcs qui sont dans le sens de parcours et
l'ensemble des arcs qui sont dans le sens opposé.
On appelle chemin une chaîne dont les arcs sont tous orientés dans le
même sens, i.e. pour deux arcs consécutifs, le noeud destination du premier est le
noeud source du second.
On désigne par chaîne élémentaire (respectivement chemin
élémentaire) une chaîne (respectivement un chemin) qui ne passe qu'une
seule fois par un même noeud.
D'après la figure 2.1, voici quelques exemples de chaînes et de chemins.
-
est une chaîne (pas élémentaire),
-
est une chaîne élémentaire,
-
est un chemin (pas élémentaire),
-
est un chemin élémentaire.
|
2.1.1.3. Cycle et circuit |
On appelle cycle une chaîne non vide telle que le noeud de départ et le
noeud d'arrivée sont identiques (e.g. le cycle
dans la figure 2.2). Si l'on considère un cycle
et qu'on lui choisit arbitrairement un sens de parcours, on notera
l'ensemble des arcs qui sont dans ce sens de parcours et
l'ensemble des arcs qui sont dans le sens opposé. Si tous les arcs sont dans le
même sens, le cycle est appelé un circuit.
Comme les chaînes et les chemins, un cycle
élémentaire (respectivement un circuit élémentaire) est un
cycle (respectivement un circuit) qui ne passe qu'une seule fois par un même noeud. Pour des
facilités d'écriture, un cycle élémentaire noté
pourra être considéré comme un vecteur d'entiers, ses composantes
seront notées
pour tout arc
du graphe
, telles que:

Dans la figure 2.2, le cycle
peut être représenté par le vecteur
, en supposant les arcs dans l'ordre
.
 |
|
Figure 2.2: Un exemple de cycle. |
Si un graphe est sans cycle, alors
(cette propriété se démontre facilement par
récursivité sur la taille du graphe).
|
2.1.1.4. Cocycle et cocircuit |
Soit
un sous-ensemble des noeuds de
. On note
le cocycle de
. Il s'agit de l'ensemble des arcs de
qui ont une extrémité dans
et l'autre dans
, i.e. les noeuds qui ne sont pas dans
(e.g. le cocycle
dans la figure 2.3).
L'ensemble
peut être séparé en deux sous-ensembles:
qui contient les arcs du cocycle qui ont leur source dans
, et
qui contient ceux qui ont leur destination dans
. Si tous les arcs sont dans le
même sens, le cocycle est appelé un cocircuit.
 |
|
Figure 2.3: Un exemple de cocycle. |
De la même manière que le cycle, un cocycle noté
pourra être considéré comme un vecteur d'entiers, ses composantes
seront notées
pour tout arc
du graphe
, telles que:

Dans la figure 2.3, le cocycle
peut être représenté par le vecteur
, en supposant les arcs dans l'ordre
.
|
2.1.2.1. Connexité et forte connexité |
Deux noeuds
et
sont connectés si et seulement s'il existe une chaîne entre
et
ou bien
. Un graphe est dit connexe si et seulement si tous ses noeuds sont
connectés deux à deux.
Deux noeuds
et
sont fortement connectés si et seulement s'il existe un chemin de
à
et un chemin de
à
, ou bien
. Un graphe est dit fortement connexe si et seulement si tous ses noeuds sont
fortement connectés deux à deux.
Si le graphe
est connexe, alors
(cette propriété se démontre aisément par
récursivité sur la taille du graphe).
On appelle composante connexe (respectivement composante fortement connexe) un
ensemble de noeuds dont tous les noeuds sont connectés (respectivement fortement
connectés) deux à deux et tout noeud extérieur à la composante n'est
pas connecté (respectivement fortement connecté) à aucun noeud de la
composante.
Pour exemple, le graphe de la figure 2.1 est connexe, mais pas fortement connexe. En revanche,
la composante
est fortement connexe.
|
2.1.2.2. Sous-graphe et graphe partiel |
Soit un graphe
, le sous-ensemble de noeuds
, et les sous-ensembles d'arcs
et
. Voici la définition de graphes qui peuvent être formés à
partir de ces ensembles.
- Le graphe
est appelé sous-graphe de
. Autrement dit, un sous-graphe de
, c'est
privé de quelques noeuds et des arcs adjacents à ces noeuds.
- Le graphe
est appelé graphe partiel de
. Autrement dit, un graphe partiel de
, c'est
privé de quelques arcs.
|
2.1.2.3. Arbre et arbre recouvrant |
Un arbre est un graphe connexe sans cycle. De cette définition découlent
les propriétés suivantes.
- Tous les noeuds d'un arbre sont reliés par une chaîne (grâce à la
connexité) et une seule (sinon deux chaînes formeraient un cycle).
- Un arbre à
sommets contient exactement
arcs (car connexe signifie
et sans cycle signifie
).
- Un arbre possède au moins deux noeuds de degré 1 (cette propriété
se vérifie facilement par récursivité sur la taille de l'arbre).
- L'ajout d'un seul arc dans un arbre introduit un cycle (car
devient supérieur à
).
- La suppression d'un seul arc dans un arbre introduit deux composantes connexes (car
devient inférieur à
).
 |
|
Figure 2.4: Un exemple d'arbre recouvrant. |
On appelle arbre recouvrant d'un graphe
un arbre
tel que
. Autrement dit, un arbre recouvrant de
est un graphe partiel connexe de
sans cycle. Le graphe de la figure 2.4 est un arbre recouvrant du graphe de la figure
2.1. Un algorithme de recherche d'arbre recouvrant dans un graphe est détaillé dans
l'annexe.
Un noeud
est une racine du graphe
si pour tout noeud
de
il existe un chemin de
à
. Un arbre de racine
est appelé une arborescence de racine
.
En particulier, nous empruntons le terme arbre binaire au domaine des structures de
données pour la suite de ce document. Il désigne une arborescence pour laquelle tous
les noeuds ont un degré entrant égal à
(exceptée la racine pour laquelle c'est
) et un degré sortant d'au plus
. Un exemple est montré par la figure 2.5.
 |
|
Figure 2.5: Un exemple d'arbre binaire. |
En partant de la racine et en suivant les arcs dans le sens direct de gauche à droite,
une arborescence représente un ordre sur les noeuds. Nous proposons ainsi une notation
récursive des arbres binaires. Supposons
la racine d'un arbre binaire
, si l'on supprime la racine, on se retrouve avec deux arbres
et
, que l'on nomme sous-arbres.
sera alors représenté par le triplet
. Pour chaque sous-arbre, on recommence l'opération jusqu'à avoir des
sous-arbres vides qui seront symbolisés par
. Voici la représentation de l'arbre binaire
de la figure 2.5.

|
2.1.3. Représentation des graphes |
|
Nous proposons ici les structures les plus populaires pour représenter un graphe.
Très souvent, les performances d'un algorithme sont liées à la structure de
graphe employée. En effet, chaque structure est très efficace pour un certain type
d'opération, mais est souvent mauvaise pour d'autres. Ainsi, il est impossible d'avoir une
structure qui soit la plus efficace pour toutes les opérations. Dans notre étude,
nous avons choisi de ne pas favoriser une ou plusieurs opérations en particulier et nous
avons opté pour une structure qui a une efficacité à peu près
égale pour toutes les opérations de base. Notre structure n'est donc jamais la plus
efficace pour un algorithme mais n'est aussi jamais la plus médiocre.
Pour commencer, nous présentons des structures sous forme de matrice qui
s'avèrent très intéressantes à manipuler d'un point de vue
théorique. Ensuite, nous nous intéressons à une modélisation par listes
d'adjacence qui est très similaire à la structure que nous avons utilisée pour
coder les algorithmes. Le détail de notre structure est proposé dans l'annexe.
|
2.1.3.1. Matrice d'incidence noeud-arc |
Un graphe
peut être représenté par une matrice
de dimension
, dite matrice d'incidence noeud-arc, pouvant contenir uniquement les valeurs
,
et
. Chaque ligne de la matrice est associée à un noeud et chaque colonne
à un arc. Ainsi, une composante indique la relation qu'il existe entre un noeud
et un arc
. Pour chaque composante
de la matrice
, on a:

Pour exemple, voici la représentation par matrice d'incidence du graphe de la figure
2.1.

La structure de cette matrice est assez particulière. Seulement
des
composantes sont non nulles. Elle occupe donc beaucoup de place en mémoire. En
outre, son utilisation n'apporte que rarement (dans le cas où la matrice elle même a
de l'intérêt) de bons résultats au niveau des algorithmes. En effet, rien que
le parcours du graphe s'avère difficile. Cependant, cette matrice a des
propriétés mathématiques très intéressantes, notamment le fait
qu'elle soit unimodulaire.
Soit
une matrice
.
est dite unimodulaire si les conditions suivantes sont vérifiées.
-
est à composantes entières.
-
est de rang maximal (i.e. de rang
).
- Toute sous-matrice carrée de
a un déterminant égal à
,
ou
.
Le résultat intéressant de cette unimodularité est le suivant.
est unimodulaire si et seulement si toute solution de base du système
linéaire
, avec
, est entière lorsque
est un vecteur d'entiers. Autrement dit, la résolution d'un programme
linéaire de la forme:

avec la méthode du Simplex fournit une solution optimale à composantes
entières pour tout vecteur d'entiers
, à condition bien entendu que le problème soit borné et
possède au moins une solution réalisable.
|
2.1.3.2. Matrice d'adjacence noeud-noeud |
Un graphe
peut être représenté par une matrice
de dimension
, dite matrice d'adjacence noeud-noeud, pouvant contenir uniquement les valeurs
et
. Chaque ligne et chaque colonne de la matrice est associée à un noeud.
Ainsi, une composante indique la relation qu'il existe entre deux noeuds
et
. Pour chaque composante
de la matrice
, on a:

Dans cette matrice, seulement
des
composantes sont non nulles. Cette représentation sera donc efficace au niveau
de l'espace mémoire utilisé lorsque le graphe est suffisamment dense (i.e. lorsqu'il
y a suffisamment d'arcs). Néanmoins, cette représentation permet d'implémenter
assez facilement les algorithmes. Son utilisation apporte plus souvent de bons résultats au
niveau des algorithmes que la matrice d'incidence, en particulier si le graphe est dense.
Malheureusement, il faut noter une simplification importante dans la modélisation: on
suppose qu'il n'y a pas d'arc multiple dans le graphe. Pour exemple, voici la représentation
par matrice d'incidence du graphe de la figure 2.1.

|
2.1.3.3. Listes d'adjacence |
L'un des inconvénients de la représentation sous forme de matrice est la
difficulté à connaître pour un noeud tous les arcs qui lui sont adjacents,
information qui est très utilisée dans les algorithmes. D'où la
modélisation dite par listes d'adjacence. Tous les arcs sont stockés dans une
liste, tous les noeuds dans une autre et chaque noeud
possède deux listes: une pour les arcs entrants (i.e.
), une autre pour les arcs sortants (i.e.
). La figure 2.6 montre comment représenter le graphe de la figure 2.1.
 |
|
Figure 2.6: Un exemple de représentation par listes d'adjacence. |
Plusieurs remarques pratiques peuvent être faites sur cette figure. Tout d'abord, pour
les représentations par matrice, nous n'avons parlé que de la représentation
de la structure du graphe en omettant volontairement la représentation des informations
portées par les noeuds ou par les arcs, puisque nous n'allons pas utiliser ces structures en
pratique.
Pour la représentation par listes d'adjacence, les informations seront stockées
au niveau des identifiants, par exemple pour le noeud
(resp. l'arc
), ses données seront stockées à l'endroit noté
(respectivement
) sur la figure. Ainsi les listes des arcs entrants ou sortants ne contiennent que des
références sur les arcs afin d'éviter toute redondance inutile d'information.
Il faut également noter que les listes utilisées pour cette structure peuvent
être de simples tableaux (à condition que le graphe soit statique, i.e. pas d'ajout ou
de suppression d'arcs ou de noeuds), des listes chaînées (à condition de
limiter la suppression d'arcs ou de noeuds) ou bien des structures arborescentes (qui permettent
efficacement l'ajout ou la suppression d'arcs ou de noeuds).
|
2.1.4. Algorithme de Minty |
|
L'algorithme que nous présentons ici est basé sur le lemme de Minty (cf.
[Minty61]). Minty propose d'associer une couleur à chaque arc
d'un graphe parmi quatre (généralement vert, noir, bleu et rouge). Il démontre
qu'une recherche basée sur une telle coloration conduit toujours à un cycle ou
à un cocycle avec des propriétés bien particulières.
L'intérêt de l'algorithme est que suivant la manière de colorer les arcs, on
obtient des algorithmes pour rechercher différents types de cycle ou de cocycle.
Soit un graphe
avec les arcs colorés en vert, noir, bleu et rouge. Minty a
démontré qu'une et une seule des propositions suivantes est vérifiée
pour tout arc
.
- L'arc
appartient à un cycle constitué (excepté
) seulement d'arcs verts, noirs et bleus avec les arcs noirs orientés dans la
même direction que
et les arcs bleus dans la direction opposée. Les arcs verts peuvent être
dans n'importe quel sens.
- L'arc
appartient à un cocycle constitué (excepté
) seulement d'arcs rouges, noirs et bleus avec les arcs noirs orientés dans la
même direction que
et les arcs bleus dans la direction opposée. Les arcs rouges peuvent être
dans n'importe quel sens.
La preuve de ce lemme peut être faite par la justification de l'algorithme de recherche
d'un tel cycle ou cocycle exposé dans la section qui suit.
Nous exposons ici une méthode pour trouver un cycle ou un cocycle d'après la
coloration de Minty pour un arc donné
du graphe
. L'algorithme 2.1 parcours et marque les noeuds de
un par un en partant de
. Deux ensembles de noeuds
et
sont nécessaires pour cette opération.
contient les noeuds marqués pendant le parcours et
contient les noeuds marqués pendant le parcours susceptibles de conduire
à des noeuds non marqués.
Le parcours d'un noeud à l'autre se fait en utilisant les arcs verts dans n'importe quel
sens, les arcs noirs dans le sens direct et les arcs bleus dans le sens indirect. Si le noeud
est atteint, alors il existe une chaîne de
à
et donc un cycle contenant
qui correspond à la première proposition du lemme. L'algorithme
nécessite alors une fonction
qui indique pour chaque noeud marqué l'arc qui a permis d'y accéder,
cela permettra de construire le cycle détecté.
Si
ne peut pas être marqué,
est le cocycle qui sépare
des noeuds non marqués de
. Ce cocycle correspond à la deuxième proposition du lemme. En effet, si
contenait un arc vert, alors un autre noeud aurait dû être marqué.
De manière similaire, si
contenait un arc noir dans le sens opposé à
dans le cocycle ou un arc bleu dans le même sens que
dans le cocycle, alors un autre noeud aurait dû être marqué.
Algorithme 2.1: cycleMinty(arc
,graphe
,cycle
,cocycle
)
;
;
;
tant que
et
faire
choisir
;
;
pour tout
tel que
est vert ou noir et
faire
;
;
;
fin pour;
pour tout
tel que
est vert ou bleu et
faire
;
;
;
fin pour;
fin tant que;
si
alors /* Cocycle trouvé. */
construire le cocycle
de
;
sinon /* Cycle trouvé. */
construire le cycle
en utilisant la fonction
à partir de
;
fin si;
fin algorithme;
Enfin, les deux propositions du lemme ne peuvent pas être vraies en même temps.
Pour le prouver, supposons les deux propositions vérifiées. L'arc
appartient donc à la fois au cycle et au cocycle. Dans le cocycle, il existe
forcément un arc
qui appartient au cycle comme
(en effet, le cycle contenant
doit forcément repasser dans le cocycle). Cet arc
ne peut être ni rouge, ni vert. En outre, s'il était bleu, il serait
opposé à
dans le cycle mais aussi dans le cocycle, ce qui est impossible puisque deux arcs de
même sens dans un cycle sont forcément opposés dans un cocycle. Pour la
même raison,
ne peut pas être noir. D'où la contradiction.
Cet algorithme étant un simple parcours de graphe, il permet de détecter un cycle
ou un cocycle de Minty en
opérations.
|
2.1.4.3. Détection de cycle, circuit, cocycle et
cocircuit |
L'algorithme de Minty est très intéressant puisqu'en choisissant judicieusement
la coloration des arcs, il permet la recherche de différents types de cycle ou de cocycle.
En général, il permet la détection d'un cycle ou d'un cocycle dont les
propriétés peuvent s'exprimer indépendamment sur chaque arc. Par contre une
propriété globale à tout le cycle ou le cocycle, comme par exemple la longueur
d'un cycle, ne peut pas être traduite en termes de couleurs sur les arcs. Voici quelques
colorations simples qui permettent les recherches les plus classiques.
- Colorer tous les arcs en vert permet de rechercher un cycle contenant un arc donné
(tous les arcs peuvent être employés pour trouver une chaîne de
à
).
- Colorer tous les arcs en rouge permet de déterminer le cocycle du noeud source d'un arc
donné
(aucun arc ne peut être employé pour trouver une chaîne de
à
).
- Colorer tous les arcs en noir permet de rechercher un circuit contenant un arc donné
(si un cycle est trouvé, tous ses arcs sont noirs et donc dans le même
sens que
). Si un tel circuit n'existe pas, alors un cocircuit est trouvé contenant l'arc
(si un cocycle est trouvé, tous ces arcs sont noirs et donc dans le même
sens que
).
Dans la suite du document, les chaînes, les chemins, les cycles et les cocycles seront
toujours considérés élémentaires. Nous rappelons également que
nous utiliserons sans le préciser la représentation vectorielle des fonctions quand
cela s'avérera nécessaire.
Nous supposons également que les graphes que nous étudions sont toujours connexes
(s'ils ne le sont pas, il suffit de considérer chaque composante connexe
séparément) et peuvent être des multigraphes (comme nous le verrons dans une
section suivante, il est dans la nature même des graphes représentant des
problèmes de synchronisation hypermédia de posséder des arcs multiples).
Le flot est une notion très importante en théorie des graphes puisqu'elle permet
de représenter des flux (e.g. l'information dans un réseau de
télécommunication, les passagers dans un réseau de transport, les
matières et les produits dans une chaîne de production...). De nombreux
problèmes autour de ce concept ont été modélisés et
étudiés, et par conséquent de nombreuses méthodes de résolution
et d'importants résultats théoriques sont disponibles. Comme nous l'expliquons dans
la seconde partie du document, pour résoudre des problèmes de tension, nous nous
sommes fortement inspirés d'algorithmes conçus pour des problèmes de flot. En
outre, la relation très particulière qui lie le flot et la tension est telle que la
plupart des méthodes pour résoudre les problèmes de flot (respectivement de
tension) manipulent la tension (respectivement le flot). Il semble donc important de rappeler ici
quelques définitions et propriétés élémentaires sur le flot.
On appelle flot une fonction
qui associe à chaque arc de
une valeur (réelle ou entière). La particularité de cette
fonction est que, pour chaque noeud
de
, on a la propriété suivante, appelée conservation des
flots.
 |
|
(2.1) |
Autrement dit,
est un flot si et seulement si, pour chaque noeud, la somme des flots sur les arcs
entrants est égale à la somme des flots sur les arcs sortants. Par exemple, si
représente un circuit électrique, l'intensité du courant est un
flot sur
. Ainsi, si on note
la matrice d'incidence de
, la formule 2.1 peut s'écrire:
 |
|
(2.2) |
|
2.2.1.2. Propriétés élémentaires |
Voici quelques propriétés élémentaires sur le flot très
simplement vérifiables.
- Si
est un flot et
un réel, alors
est un flot.
- Si
et
sont des flots, alors
est un flot.
- Le seul flot possible sur un arbre est le flot
.
- Le vecteur qui représente un cycle est un flot (il est très facile de
vérifier la conservation des flots).
On dit que
vecteurs
,
...
de
sont dépendants s'il existe
coefficients non tous nuls
,
...
dans
tels que:
 |
|
(2.3) |
A l'inverse, si la relation 2.3 n'est vérifiée que pour tous les
nuls, alors les vecteurs
,
...
sont dits indépendants.
Une base de vecteurs est un ensemble de vecteurs indépendants tel que tout
vecteur
de
est une combinaison linéaire des vecteurs de la base, i.e. pour tout
vecteur
il existe des coefficients
,
...
tels que:
 |
|
(2.4) |
Les cycles pouvant être considérés comme des vecteurs, il est possible de
construire une base de cycles. Nous rappelons ici une manière simple d'obtenir une
telle base. Considérons un arbre recouvrant
du graphe
. Il ne contient pas de cycles, mais tout ajout dans l'arbre d'un arc
de
(i.e. un arc qui n'est pas déjà dans
) engendre un cycle
. Si on considère l'ensemble des cycles
engendré en ajoutant séparément chaque arc
de
dans l'arbre
, on obtient un ensemble
de cycles indépendants (car chaque cycle
possède un arc qu'aucun autre ne possède, c'est
). Il faut s'assurer maintenant que tout cycle de
est une combinaison linéaire des cycles de
.
Considérons un flot
. Soit
.
est une combinaison linéaire de flots donc un flot. La différence
est également un flot. Or, pour tout arc
de
,
puisque l'arc
n'apparaît que dans le cycle
. Le flot
étant nul pour tout arc n'appartenant pas à
, il représente donc un flot défini strictement sur
, or tout flot sur un arbre est nul donc
.
En conclusion, tout flot est une combinaison linéaire de la base
. Un cycle pouvant être considéré comme un flot, tout cycle est une
combinaison linéaire de
. On remarque également que la base
contient
cycles (car
possède
arcs). Enfin, l'algorithme pour construire
est détaillé dans l'annexe.
Nous présentons maintenant la notion de tension dont nous verrons par la suite la
pertinence pour modéliser des problèmes de synchronisation hypermédia. La
plupart des résultats théoriques liés à ce concept proviennent du
développement de méthodes de résolution pour des problèmes de flot.
L'utilisation de la tension pour modéliser des problèmes dans les graphes est
beaucoup moins répandue que pour le flot, cependant il existe de nombreux problèmes
que la tension peut représenter (e.g. [Rockafellar84]). Notamment
dans le domaine de la planification, la tension peut être assimilée à une
durée comme nous le verrons à la section suivante. Nous rappelons ici quelques
définitions et propriétés élémentaires sur la tension (issues de
[Berge62]) utiles pour notre étude.
On désigne par potentiel une fonction
qui associe à chaque noeud de
une valeur (entière ou réelle). Associée à ce potentiel,
on peut définir une fonction
appelée tension qui attribue à chaque arc
de
une valeur de la manière suivante.
 |
|
(2.5) |
Une fonction est donc une tension s'il est possible de lui associer un potentiel. Ces notions
de tension et de potentiel peuvent être comparées à celles d'un circuit
électrique. Si on note
la matrice d'incidence de
, la définition 2.5 de la tension peut se traduire:
 |
|
(2.6) |
|
2.2.2.2. Propriétés élémentaires |
Voici quelques propriétés élémentaires sur la tension très
simplement vérifiables.
- Si
est une tension et
un réel, alors
est une tension.
- Si
et
sont des tensions, alors
est une tension.
- Toute fonction qui associe à chaque arc d'un arbre une valeur est une tension.
- Le vecteur qui représente un cocycle est une tension (il est très facile d'y
associer un potentiel).
Tout vecteur tension
et tout vecteur flot
sur un graphe
sont orthogonaux, i.e. le produit scalaire
(d'après la définition 2.6, il existe un potentiel
tel que
où
est la matrice d'incidence de
, donc
). Il est alors possible d'en déduire une nouvelle définition de la
tension.
 |
|
(2.7) |
Preuve:
( )
est orthogonale à tout flot sur
et donc en particulier à tout cycle (le vecteur cycle représentant un
flot).
( ) Si l'égalité est vérifiée, un potentiel
peut être associé à
. Dans le cas contraire, cela signifierait qu'il existe pour un arc
une chaîne
de
à
pour laquelle
. Or si l'on considère le cycle
formé de
et de
, on doit avoir
, d'où la contradiction.
Il n'est pas nécessaire de vérifier l'égalité pour tous les cycles
du graphe pour confirmer une tension. En effet, si l'égalité est
vérifiée pour une base de cycles
, i.e.
, alors toute combinaison linéaire, donc tout cycle
, vérifie
. La définition suivante suffit donc à caractériser une tension.
 |
|
(2.8) |
|
2.2.2.3. Base de cocycles |
De manière analogue aux cycles, nous rappelons ici une manière simple d'obtenir
une base de cocycles. Considérons un arbre recouvrant
du graphe
. En supprimant un arc
de l'arbre, on fait apparaître deux composantes connexes. Notons
la composante qui contient le noeud source de
et notons
le cocycle de
dans le graphe
. Si on considère l'ensemble des cocycles
engendré en supprimant séparément chaque arc
de
, on obtient un ensemble
de cocycles indépendants (car chaque cocycle
possède un arc qu'aucun autre ne possède, c'est
). Il faut s'assurer maintenant que tout cocycle de
est une combinaison linéaire des cocycles de
.
Considérons une tension
. Soit
.
est une combinaison linéaire de tensions donc une tension. La différence
est également une tension. Or, pour tout arc
de
,
puisque l'arc
n'apparaît que dans le cocycle
. La tension
étant nulle pour tout arc de
, tous les noeuds de l'arbre et donc du graphe ont le même potentiel. Donc
.
En conclusion, toute tension est une combinaison linéaire de la base
. Un cocycle pouvant être considéré comme une tension, tout cocycle
est une combinaison linéaire de
. On remarque également que la base
contient
cocycles (car
possède
arcs).
|
2.3. MODELISATION SOUS FORME DE GRAPHE
TEMPOREL |
|
|
2.3.1. Définition d'un graphe temporel |
|
Un graphe
est dit temporel lorsque ses noeuds représentent des
événements et ses arcs des contraintes de précédence entre deux noeuds,
i.e. l'arc
signifie que l'événement modélisé par
doit se produire avant l'événement modélisé par
.
Un graphe temporel est également accompagné d'un vecteur
, appelé durée, qui associe à chaque arc
une durée
et d'un vecteur
, appelé date, qui associe à chaque noeud
une date
. Un graphe temporel peut également être muni d'un vecteur
, appelé capacité, qui associe à chaque arc
un ensemble
, indiquant les valeurs autorisées pour la durée
.
 |
|
Figure 2.7: Modélisation d'un simple objet multimédia par un
graphe temporel. |
Un objet multimédia
de durée idéale
et d'ensemble de tolérance
sera donc représenté dans un graphe temporel par ses
événements de début
et de fin
reliés par un arc indiquant la relation de précédence entre
et
(cf. figure 2.7) et portant toutes les informations associées à l'objet
telles que la durée idéale
et l'ensemble de tolérance
.
En outre, un graphe temporel doit posséder un seul noeud source
et un seul noeud puits
, chacun représentant respectivement les événements de
début et de fin du scénario complet modélisé. Il est possible de fixer
la date de l'événement
à
, la date de
représentera ainsi la durée totale de présentation du
scénario. Et si l'on connaît le vecteur durée, on peut en déduire le
vecteur date, et réciproquement.
A partir du principe qu'un arc représente une contrainte de précédence
entre deux objets multimédia, la figure 2.8b modélise sous forme de graphe temporel
un exemple de scénario illustré par la figure 2.8a (une flèche entre deux
objets signifie que la fin de l'objet source coïncide avec le début de l'objet cible).
Des simplifications peuvent être apportées à ce graphe temporel: deux
événements liés par une contrainte de précédence de
capacité
signifient qu'ils sont confondus (cf. figure 2.8c).
 |
|
Figure 2.8: Un exemple de modélisation d'un scénario par un graphe
temporel. |
|
2.3.2. Relations temporelles modélisables |
|
Il est relativement simple d'exprimer les relations d'Allen par un graphe temporel (cf. figure
2.9). Nous ne prenons pas en compte dans cette représentation les durées et les
événements imprévisibles. Nous supposons que la planification doit
établir une durée pour tous les objets multimédia et une date relative au
début de la présentation du document pour tous les événements. En
outre, la disjonction qui est préconisée sur les relations d'Allen n'est pas toujours
représentable. Soulignons deux disjonctions modélisables importantes, nous les
nommons
et
.
signifie que les objets
et
démarrent en même temps, ce qui s'exprime par
.
signifie de façon similaire que
et
se terminent en même temps, et s'exprime par
. Comme le souligne [Allen91], les possibilités de
disjonctions entre deux relations d'Allen sont au nombre de
, mais il explique également que seulement
sont modélisables par une représentation sous forme
d'événements comme la nôtre.
 |
|
Figure 2.9: Modélisation des relations d'Allen par un graphe temporel.
|
|
2.4. PROBLEMES DE TENSION |
|
Nous allons montrer ici que les durées
portées par les arcs correspondent à la notion de tension définie
à la section 2.2. Une fois établi le fait que les problèmes que nous tentons
de résoudre sont des problèmes de tension, nous en exposons les deux principaux, la
tension compatible et la tension de coût minimal, qui modélisent les
problématiques de synchronisation hypermédia soulignées au chapitre
1.
Supposons un graphe
muni d'un vecteur durée
et d'un vecteur date
. La durée
d'une chaîne
entre deux noeuds
et
est définie par la somme
. Pour un chemin
du noeud
au noeud
, sa durée se résume à
. Notons qu'un chemin dans un graphe temporel représente une succession d'objets
multimédia et la durée du chemin représente la durée totale de
présentation de ces objets. La satisfaction des contraintes temporelles par une
planification (i.e. un vecteur durée ou un vecteur date sur
) peut être exprimée de la manière suivante: pour chaque paire de
noeuds
et
, tous les chemins entre
et
doivent avoir la même durée.
En d'autres termes,
telle que, pour tout chemin
de
à
,
. Tentons alors de prouver la propriété suivante.
Soit un graphe
et un vecteur durée
.
telle que, pour tout chemin
de
à
,
, si et seulement si
est une tension. |
|
(2.9) |
Preuve:
( ) Soit
l'ensemble des cycles de
.
est une tension dans
, donc
,
. Ainsi, un cycle
formé de deux chemins
et
de
à
, e.g.
et
, vérifie
. Donc deux chemins de mêmes extrémités sont de même
durée.
( ) Notons
la durée des chemins de la source
au noeud
(tous les chemins de mêmes extrémités sont de même
durée). Soit
un cycle de
, considérons
et
deux noeuds consécutifs dans ce cycle. Il y a deux cas possibles:
- L'arc
. De la définition d'un graphe temporel, il est toujours possible de trouver un
chemin
de
à
avec la durée
. Le chemin de
à
passant par
en utilisant l'arc
du cycle
est également de durée
, et vaut aussi
(cf. figure 2.10). D'après l'hypothèse de départ,
.
- L'arc
. De manière analogue au premier cas, on trouve que
.
En résumé, on obtient l'égalité
:
.
Numérotons les arcs du cycle
consécutivement
. En sommant les égalités
, on obtient:
. Or les noeuds
et
sont confondus, donc
. Le vecteur
est donc une tension.
 |
|
Figure 2.10: Illustration de la preuve. |
En résumé, le vecteur durée
est une tension. En outre, pour tout arc
, la durée
, le vecteur date
est donc un potentiel. Etudions maintenant la relation entre certains problèmes
de tension et la synchronisation hypermédia.
|
2.4.2. Problème de la tension compatible |
|
On dit qu'une tension
d'un graphe
est compatible (ou réalisable) avec une capacité
si et seulement si, pour tout arc
,
. Le problème de la tension compatible consiste à
déterminer une telle tension. Dans le contexte de la synchronisation hypermédia, cela
signifie chercher une durée
pour chaque objet hypermédia
qui soit dans l'ensemble de tolérance
associé. La résolution de ce problème permet également de
répondre à la question: est-il possible de présenter le document en
secondes ? Il suffit pour cela d'ajouter un arc de capacité
entre le noeud source et le noeud puits du graphe, et de tenter de déterminer
une tension compatible sur ce nouveau graphe.
Au cours de notre étude sur des méthodes de résolution de ce
problème de réalisabilité, nous nous intéresserons au
problème de la tension maximale (ou minimale). Il s'agit, pour un arc donné
d'un graphe
muni d'une capacité
, de trouver la tension maximale (ou minimale)
qu'il peut atteindre,
restant compatible avec
. Là aussi, en ajoutant un arc de capacité
entre le noeud source et le noeud puits du graphe, il est possible de répondre
à la question: quelle est la durée maximale (ou minimale) de présentation d'un
document hypermédia ? Il suffit pour cela de déterminer la tension maximale (ou
minimale) du nouvel arc.
|
2.4.3. Problème de la tension de coût minimal |
|
L'un des principaux problèmes liés à la synchronisation hypermédia
est tout de même de déterminer une planification de la meilleure qualité
possible. Mais avant de tenter une résolution, il faut être capable de formaliser la
notion de qualité d'une planification. Pour cela, nous avons choisi d'attribuer un
coût (pour l'instant nous le supposerons quelconque) pour chaque arc en fonction de sa
tension. Ce coût étant naturellement le plus faible lorsque la tension de l'arc est
égale à sa tension idéale (i.e. sa durée idéale). Nous
discutons à la section suivante des différents types de fonction de coût
pertinents pour la synchronisation hypermédia.
En d'autres termes, pour chaque arc
, on définit un coût sur un graphe
comme étant un vecteur
, qui attribue à chaque arc
une fonction de coût
. Le problème d'optimisation qui se pose alors est de trouver une tension
compatible
qui minimise la somme totale des coûts, i.e.
. Ce problème est appelé le problème de la tension de
coût minimal.
|
2.5. QUANTIFIER LA QUALITE D'UNE
PRESENTATION |
|
Comme il l'a déjà été souligné, afin de déterminer la
meilleure planification d'un document hypermédia, il est nécessaire d'en mesurer la
qualité. Pour cela, nous retenons la solution qui consiste à attribuer à
chaque arc
une fonction de coût
dépendante de la valeur de la tension
, telle que
, i.e. le coût de la tension
est nul si celle-ci est à sa valeur idéale
(i.e. l'objet multimédia est planifié à sa durée
idéale). Naturellement, ce coût augmente à mesure que la tension
s'éloigne de
. A travers la littérature, nous avons constaté trois types de coût
pertinents pour représenter la qualité de la planification d'un document
hypermédia.
|
2.5.1. Pénalité, coûts convexes linéaires
par morceaux |
|
La première idée consiste à affecter à un arc
un coût proportionnel à l'écart entre la tension
et sa tension idéale
. Ce type de coût a été proposé et traité dans
[Buchanan93b] et [Kim95]. Alors que
[Kim95] propose un coût unitaire identique selon que la tension
soit inférieure ou supérieure à la durée idéale (cf. figure
2.11a), [Buchanan93b] propose de différencier les deux cas (cf.
figure 2.11b). [Kim95] considère même simplement la
fonction
. En résumé, ces approches similaires expriment la fonction de coût
d'un arc
par un coût unitaire
de diminution de la tension et un coût unitaire
d'augmentation de la tension d'un arc
. Cette fonction s'écrit de la manière suivante.

|
2.5.2. Plus d'égalité, coûts convexes
dérivables |
|
La tension optimale obtenue avec le type de coût présenté
précédemment peut produire une inégalité entre les objets
multimédia (cf. [Kim95]). Autrement dit, certains objets peuvent
subir une importante déformation alors que d'autres n'en subissent qu'une
légère.
 |
|
Figure 2.11: Exemples de coûts convexes pour mesurer la qualité
d'une planification hypermédia. |
Afin d'équilibrer ces altérations, i.e. que chacun est à peu près
la même déformation, [Kim95] propose une fonction de la
forme
(cf. figure 2.11c). Nous nous intéresserons donc par la suite à
déterminer une tension optimale avec des fonctions de coût convexes dérivables
quelconques.
|
2.5.3. Comptabilisation des objets touchés par une
déformation |
|
Un dernier type de coût présenté dans [Medina04]
semble également illustrer la qualité d'un document hypermédia. La
déformation de la durée d'un objet multimédia peut entraîner un temps
d'exécution important au moment de la présentation du document. Une mesure de
qualité qui intéresse donc les auteurs de documents hypermédia est simplement
le nombre d'objets qui ne sont pas planifiés à leur durée idéale.
Autrement dit, la fonction de coût
est de la forme suivante.

Nous avons exposé ici une modélisation possible des relations temporelles
d'objets multimédia à synchroniser. Nous avons supposé les ensembles de
tolérance quelconques. Dans notre étude, nous nous limiterons pour l'instant à
des intervalles de tolérance continu (pour tout arc
, un intervalle
), simplement parce que les problèmes sont plus faciles à aborder dans le
domaine continu que dans le domaine discret, où la combinatoire peut rapidement devenir trop
importante. Nous choisissons également d'aborder l'étude du problème
d'optimisation avec des fonctions convexes linéaires par morceaux ou simplement
dérivables. Nous n'étudierons pas pour l'instant la minimisation du nombre d'objets
touchés par une déformation dans une planification hypermédia. Cette
modélisation est également de nature discrète.
|
|
Copyright (c) 1999-2016 - Bruno Bachelet - bruno@nawouak.net -
http://www.nawouak.net |
La permission est accordée de copier, distribuer et/ou modifier ce document
sous les termes de la licence GNU Free Documentation License, Version 1.1 ou toute
version ultérieure publiée par la fondation Free Software Foundation. Voir
cette licence pour plus de détails (http://www.gnu.org). |
|
|