Scribd
Importer
49 vues2 pages

Série de Travaux Dirigés N°:2

Le document présente des exercices sur les problèmes de couverture des sommets et de clique dans des graphes non orientés pour une série de travaux dirigés en optimisation. Il demande de déterminer des sous-ensembles spécifiques de sommets, d'écrire des algorithmes pour ces problèmes et de démontrer leur appartenance à la classe NP. Les exercices incluent également des questions sur les structures de données et la complexité des algorithmes proposés.

Transféré par

bltrmeryem
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd
49 vues2 pages

Série de Travaux Dirigés N°:2

Le document présente des exercices sur les problèmes de couverture des sommets et de clique dans des graphes non orientés pour une série de travaux dirigés en optimisation. Il demande de déterminer des sous-ensembles spécifiques de sommets, d'écrire des algorithmes pour ces problèmes et de démontrer leur appartenance à la classe NP. Les exercices incluent également des questions sur les structures de données et la complexité des algorithmes proposés.

Transféré par

bltrmeryem
Copyright
© © All Rights Reserved
Nous prenons très au sérieux les droits relatifs au contenu. Si vous pensez qu’il s’agit de votre contenu, signalez une atteinte au droit d’auteur ici.
Formats disponibles
Téléchargez aux formats PDF, TXT ou lisez en ligne sur Scribd

Université d’Alger 1 Benyoucef Benkhedda 1 ère année master ASD

Département de Mathématiques et Informatique Module : Optimisation


Année universitaire : 2021/2022

Série de travaux dirigés N° :2


Exercice n° 1 :

Considérer le problème de la couverture des sommets décrit comme suit :

Instance : Un graphe non orienté G = (S, A) où S = {s1, s2, …, sn} est l’ensemble des
sommets, A = {<si, sj> tel que si et sj ∈ S} est l’ensemble des arêtes et k un entier naturel.

Question : Existe-il un sous ensemble 𝑆′ de 𝑆 tel que si <si, sj> ∈ A alors si ∈ 𝑆 ′o𝑢 bien sj ∈

S′ ou bien les deux appartiennent à S′ et la cardinalité de S′ est égal à k ?

Considérer le graphe G non orienté suivant :

1. Quelles sont les couvertures des sommets de cardinalité égale à 2 de G ?

2. Ecrire un algorithme de détermination d’une couverture des sommets d’une cardinalité

égale à k. Calculer sa complexité.

3. Montrer que le problème de la couverture des sommets appartient à la classe NP.

Exercice n° 2 :

Considérer le problème de la clique décrit comme suit :

Instance : Un graphe non orienté G = (S, A) où S = {s1, s2, …, sn} est l’ensemble des
sommets, A = {<si, sj> tel que si et sj ∈ S} est l’ensemble des arêtes et k un entier naturel.

Question : G contient-il une clique de taille k ou plus, i.e., un sous-ensemble S′ inclut dans S
tel que S’ ≥ 𝑘 et chaque deux sommets de S′ sont reliés par une arête de A ?

Considérer le graphe non orienté G où G = (S, A), S = {s1, s2, s3, s4, s5} et A l’ensemble des

1/2
arêtes montrées sur le schéma suivant :

1. Quelles sont les cliques de cardinalité égale à 3 de G ?


2. Montrer que le problème de la clique appartient à la classe NP.
• Expliquer clairement les structures de données utilisées.
• Expliciter l’algorithme de vérification ou validation d’une instance.
3. Montrer que le problème de la clique est NP-complet.
• Bien expliquer l’algorithme de transformation et sa complexité

2/2

Vous aimerez peut-être aussi