Download NOM Prénom : .......................................... 30 mai 2007 Examen de

NOM Prénom : ..........................................
30 mai 2007
Examen de graphes - 3 heures
Notations : dans les exercices suivants, le mot complexité désignera la complexité en temps
dans le pire des cas. Pour un graphe, on notera n son nombre de sommets et m son nombre
d’arêtes (cas non orienté) ou d’arcs (cas orienté). Pour les questions algorithmiques, on
suppose que les graphes sont donnés par leurs listes d’adjacence (N dans le cas non orienté,
N + dans le cas orienté). Les notes et documents de cours sont autorisés.
Exercice 1 - QCM sur le cours et les exposés (6 pts)
Mode d’emploi : Pour chacune des questions, entourer la (ou les) réponse(s) justes (il
peut éventuellement y en avoir plusieurs ou aucune de juste). Le terme O(nω ) désigne la
meilleure complexité connue à ce jour pour multiplier deux matrices n × n.
1
2
3
4
5
6
7
8
9
10
11
12
13
QUESTION
Considérer la classe des graphes d’intersection de rectangles : les
sommets sont des rectangles du plan et deux sommets sont adjacents
si et seulement si l’intersection de leurs rectangles est non vide. Est-ce
que cette classe est incluse dans la classe des graphes parfaits ?
La proposition suivante est-elle vraie : toute classe caractérisée par
une famille infinie de mineurs interdits peut aussi être caractérisée
par une famille finie de mineurs interdits ?
Quelle est la complexité du problème consistant à enlever le minimum
de sommets à un graphe non orienté pour qu’il devienne acyclique ?
Donner la meilleure complexité avec laquelle on sait calculer le cardinal max d’un indépendant pour les graphes de clique-width ≤ 5.
Avec quelles complexités sait-on résoudre le problème de fermeture
transitive d’un graphe orienté ?
Est-ce que le graphe de Petersen ci-dessous est planaire ?
Soit G = (V, E) non orienté. Parmi les deux familles suivantes,
lesquelles sont des matroı̈des ?
A = {A ⊆ E | GA = (V, A) est sans cycle}
B = {B ⊆ E | GB = (V, B) a au moins un cycle}
Dans le modèle d’Erdös-Renyi avec probabilité 12 d’avoir une arête
pour chaque paire de sommets, quand n → +∞, quel est en moyenne
le diamètre d’un graphe à n sommets ?
Soit G un graphe biparti à 10 sommets ayant un indépendant de
cardinal maximum avec 6 sommets, quel est le cardinal maximum
d’un couplage ?
Quelle est la meilleure complexité avec laquelle on sait vérifier si deux
arbres à n sommets (non enracinés) sont isomorphes ?
Avec quelle complexité sait-on calculer un cycle de longueur minimum
dans un graphe non orienté ?
Si on sait effectuer la multiplication dans l’algèbre (min, +) de deux
matrices n × n en O(nα ), avec quelle complexité sait-on calculer
les distances pour tout couple de sommets dans un graphe orienté
pondéré (sans cycle de poids strictement négatif) ?
Est-ce qu’on peut exprimer l’existence d’une 4-coloration d’un graphe
avec une formule du langage logique τ1 (quantification sur les
sommets et les ensembles de sommets, tests d’appartenance et
d’adjacence, opérations logiques de base) ?
OUI
REPONSE
NON
OUI
NON
P
O(n)
NP-dur
O(n2 )
O(n5 )
NP-dur
O(nω ) O(nω log n) O(n2 ) O((m + n)n)
OUI
NON
A
B
2
π
4
O(n)
√
Θ( n)
6
O(n log n)
Θ(n)
ça dépend
O(n2 )
NP-dur
O(n)
O(n(n + m))
NP-dur
O(nα )
O(nα log n)
O(nα+1 )
OUI
NON
Exercice 2 - Coloration de graphes particuliers (6 pts)
On rappelle qu’une technique pour calculer une coloration valide des sommets d’un
graphe consiste prendre une séquence des sommets, puis colorer les sommets dans l’ordre
de la séquence en donnant comme couleur le plus petit entier pas utilisé parmi les voisins
déjà colorés (coloration goutonne).
1 - Si G est un cographe, montrer que pour n’importe quelle séquence des sommets, la
coloration gloutonne est optimale (càd. utilise exactement χ(G) couleurs).
2 - Si G est triangulé, monter qu’il existe une séquence des sommets telle que la coloration
gloutonne est optimale.
Exercice 3 - Une nouvelle espèce pour le Zoo des Graphes (4 pts)
Un graphe G = (V, E) est divisible s’il existe une partition des sommets V = I ∪ K,
I ∩ K = ∅, telle que I soit un indépendant et K une clique, et telle que tout sommet de K
a au moins un voisin dans I, et aucun des sommets de I n’est relié à tous les sommets
de K. La figure ci-dessous donne un exemple.
Clique
Indépendant
1 - Est-ce que la classe des divisibles peut être caractérisée par une famille de mineurs
interdits ? Est-ce que la classe des divisibles est incluse dans la classe des cographes ? Et
dans la classe des graphes triangulés ?
2 - Donner un algorithme de reconnaissance des divisibles, avec la meilleure complexité
que vous pouvez. Justifier la correction de votre algorithme.
Exercice 4 - Calcul de résistance dans les réseaux électriques (4 pts)
Vous avez sûrement déjà été amenés à calculer la résistance équivalente entre deux
points s et t, s 6= t, d’un réseau électrique qui est un graphe non orienté G = (V, E) où
chaque arête xy porte une résistance Rxy > 0. Le mot graphe désignera éventuellement
un multigraphe s’il y a des résistances en parallèle entre deux sommets.
Pour rappel, entre s et t, un tel réseau composé uniquement de résistances se comporte
comme une unique résistance dont on cherche la valeur. Une manière de résoudre le
problème est d’introduire les variables ixy (intensité) et uxy (tension) pour xy ∈ E, et
d’écrire un nombre suffisant d’équations à partir de la loi d’Ohm (uxy = Rxy ixy ) et des
lois de Kirchhoff (loi des nœuds, loi des mailles). On peut ainsi se ramener à la résolution
d’un système d’équations linéaires dont on tire la résistance équivalente.
Une autre méthode consiste à réaliser une suite de transformations locales qui remplacent chaque fois un morceau du réseau par un nouveau morceau au comportement
équivalent mais de taille plus petite. La figure ci-dessous présente trois règles classiques
de transformation, avec respectivement R = R1 + R2 (réduction série), R1 = R11 + R12
(réduction parallèle) et S = R1 R2 +R2 R3 +R3 R1 (réduction étoile-triangle). Les pointillés
indiquent la présence éventuelle d’autres arêtes (qui elles ne sont pas modifiées).
Ces réductions suppriment une arête et/ou un sommet à chaque fois. Pour avoir la
résistance équivalente entre s et t, il faut réussir à appliquer ces transformations jusqu’à
série
R1
R
R2
R1
parallèle
R
R2
R1
R2
étoile−triangle
S/R3
S/R2
R3
S/R1
ce que le graphe soit réduit à une seule arête st.
1 - Montrer pour le graphe ci-dessous qu’on peut appliquer les trois règles jusqu’à obtenir
le graphe réduit à l’arête st (les valeurs des résistances sont omises car ne jouant aucun
rôle dans le succès ou pas de la méthode). Est-ce que les trois règles présentées permettent
toujours de se ramener à une unique arête st, pour tout graphe connexe et tout couple
s 6= t de sommets ?
b
d
s
t
a
c
2 - Démontrer le théorème suivant pour G = (V, E) et s, t ∈ V , en supposant que
G′ = (V, E ∪ {st}) est 2-connexe :
Pour les trois règles présentées, il existe une suite de réductions transformant G en l’arête st
si et seulement si G′ = (V, E ∪ {st}) est de largeur arborescente ≤ 3.
Indication : Utiliser la caractérisation tw(G′ ) = min{ω(H)−1 | H surgraphe triangulé de G′ }.
Pour le sens ⇒, construire un bon surgraphe de G qui soit triangulé. Pour le sens ⇐,
construire la suite en travaillant sur un surgraphe triangulé de G.
Remarque : dans le cas général, plutôt que de générer puis résoudre de gros systèmes
linéaires, les meilleurs algorithmes utilisent la théorie des graphes.
Question subsidiaire - Une dernière classe pour la route (1 pt)
En relachant les conditions sur la classe des divisibles, on définit la classe des splits :
G = (V, E) est un split s’il existe une partition des sommets V = I ∪ K, I ∩ K = ∅, telle
que I soit un indépendant et K une clique. Donner une caractérisation des splits par une
famille finie de sous-graphes induits interdits.
Remarque : exceptionnellement pas de justification demandée pour cette dernière question,
vous pouvez juste donner votre proposition.