1. On effectue `enfiler(F,42)`. De quels éléments est maintenant composée `F` ?
   Après avoir enfilé l'élément `42` dans la file `F`, celle-ci est maintenant composée des éléments suivants : `22, 12, 14, 8, 7, 19, 42`.

2. Que renvoie `defiler(F)` ? De quels éléments est maintenant composée `F` ?
   • `defiler(F)` renvoie le premier élément de la file, soit `22`.
   • Après l'opération, la file `F` est composée des éléments suivants : `12, 14, 8, 7, 19, 42`.

3. Que renvoie `tete(F)` ? La file est-elle modifiée ?
   • `tete(F)` renvoie le premier élément de la file, soit `12`.
   • La file `F` n'est pas modifiée par l'opération `tete(F)`.

4. Si on applique `defiler(F)` 6 fois de suite, que renvoie `est_vide(F)` ?
   • Après avoir défilé 6 fois, la file `F` est maintenant vide.
   • `est_vide(F)` renvoie `True`, indiquant que la file est vide.
    

1. Liste chaînée (Linked List) : Une liste chaînée est une structure de données linéaire où chaque élément contient une référence au suivant. Cela permet d'insérer et de supprimer des éléments en temps constant, ce qui en fait une bonne alternative à la deque.
   
  class Node:
      def __init__(self, data):
          self.data = data
          self.next = None

  class LinkedList:
      def __init__(self):
          self.head = None

      def append(self, data):
          new_node = Node(data)
          if self.head is None:
              self.head = new_node
              return
          last_node = self.head
          while last_node.next:
              last_node = last_node.next
          last_node.next = new_node

      def insert_at_beginning(self, data):
          new_node = Node(data)
          new_node.next = self.head
          self.head = new_node


    2. Liste doublement chaînée (Doubly Linked List) : Une liste doublement chaînée est similaire à la liste chaînée, mais chaque nœud contient une référence au nœud précédent et au nœud suivant. Cela permet d'accéder plus facilement aux éléments dans les deux directions.
    
   
  class Node:
      def __init__(self, data):
          self.data = data
          self.prev = None
          self.next = None

  class DoublyLinkedList:
      def __init__(self):
          self.head = None

      def append(self, data):
          new_node = Node(data)
          if self.head is None:
              self.head = new_node
              return
          last_node = self.head
          while last_node.next:
              last_node = last_node.next
          last_node.next = new_node
          new_node.prev = last_node

      def insert_at_beginning(self, data):
          new_node = Node(data)
          new_node.next = self.head
          if self.head is not None:
              self.head.prev = new_node
          self.head = new_node


    3. Liste circulaire (Circular List) : Une liste circulaire est une variante de la liste chaînée où le dernier nœud pointe vers le premier nœud, formant une boucle.
    
   
  class Node:
      def __init__(self, data):
          self.data = data
          self.next = None

  class CircularLinkedList:
      def __init__(self):
          self.head = None

      def append(self, data):
          new_node = Node(data)
          if self.head is None:
              self.head = new_node
              new_node.next = self.head
              return
          last_node = self.head
          while last_node.next != self.head:
              last_node = last_node.next
          last_node.next = new_node
          new_node.next = self.head

      def insert_at_beginning(self, data):
          new_node = Node(data)
          if self.head is None:
              self.head = new_node
              new_node.next = self.head
              return
          last_node = self.head
          while last_node.next != self.head:
              last_node = last_node.next
          new_node.next = self.head
          self.head = new_node
          last_node.next = self.head

    

1. Transfert du contenu d'une file dans une pile:
   
  def transfer_queue_to_stack(queue, stack):
      while queue:
          stack.append(queue.pop(0))

    2. Transfert du contenu d'une pile dans une file:
    
   
  def transfer_stack_to_queue(stack, queue):
      while stack:
          queue.append(stack.pop())

    3. Inversion d'une pile:
    
   
  def reverse_stack(stack):
      temp_stack = []
      while stack:
          temp_stack.append(stack.pop())
      return temp_stack

    4. Inversion d'une file:
    
   
  def reverse_queue(queue):
      stack = []
      while queue:
          stack.append(queue.pop(0))
      return stack

    5. Fusion de deux piles:
    
   
  def merge_stacks(stack1, stack2):
      merged_stack = []
      while stack1 or stack2:
          if stack1:
              merged_stack.append(stack1.pop())
          if stack2:
              merged_stack.append(stack2.pop())
      return merged_stack   

    6. Fusion de deux files:
    
   
  def merge_queues(queue1, queue2):
      merged_queue = []
      while queue1 or queue2:
          if queue1:
              merged_queue.append(queue1.pop(0))
          if queue2:
              merged_queue.append(queue2.pop(0))
      return merged_queue
    

1. L'élément issu du défilage de F1 :
   Étant donné que nous utilisons une file (queue) qui suit la règle FIFO (First In, First Out), l'élément qui sera défilé en premier de F1 est le premier élément ajouté à la file. Comme les éléments sont classés par ordre alphabétique et la file est :

                                 F1 = ('A', 'B', 'C', 'D', 'E')

   L'élément défilé en premier est 'A'.

2. Pour défilage, nous devons transférer tous les éléments de P1 à P2 (ce qui inversera l'ordre), puis dépiler de P2.
   Voici un algorithme Python pour ce processus :
   
  class FileAvecDeuxPiles:
      def __init__(self):
          self.P1 = []  # Pile d'entrée
          self.P2 = []  # Pile de sortie

      def enfiler(self, element):
          # Empiler l'élément dans P1
          self.P1.append(element)

      def defiler(self):
          # Si P2 est vide, transférer tous les éléments de P1 à P2
          if not self.P2:
              while self.P1:
                  self.P2.append(self.P1.pop())
          # Dépiler et retourner l'élément de P2
          if self.P2:
              return self.P2.pop()
          else:
              return None  # Si les deux piles sont vides

  # Exemple d'utilisation
  file = FileAvecDeuxPiles()
  elements = ['A', 'B', 'C', 'D', 'E']

  # Enfiler les éléments
  for elem in elements:
      file.enfiler(elem)

  # Dépiler les éléments comme s'ils sortaient d'une file
  while True:
      elem = file.defiler()
      if elem is None:
          break
      print(elem)

    Explication du code :
 1. Classe FileAvecDeuxPiles :

 • __init__ : Initialise deux piles, P1 pour l'entrée et P2 pour la sortie.
 • enfiler : Empile un élément dans P1.
 • defiler : Si P2 est vide, transfère tous les éléments de P1 à P2 (cela inverse l'ordre des éléments), puis dépile et retourne l'élément de P2.

 2. Utilisation :

 • Nous créons une instance de FileAvecDeuxPiles.
 • Nous ajoutons les éléments ['A', 'B', 'C', 'D', 'E'] à la file.
 • Nous dépilons et affichons les éléments jusqu'à ce que la file soit vide.
 
 Ce code affiche les éléments dans l'ordre 'A', 'B', 'C', 'D', 'E', imitant le comportement d'une file.

class FileAvecDeuxPiles:
    def __init__(self):
        self.P1 = []  # Pile pour enfiler
        self.P2 = []  # Pile pour défiler

    def enqueue(self, value):
        self.P1.append(value)  # Ajouter l'élément à la pile P1

    def dequeue(self):
        if not self.P2:  # Si la pile P2 est vide
            while self.P1:  # Déplacer tous les éléments de P1 à P2
                self.P2.append(self.P1.pop())
        if not self.P2:  # Si la pile P2 est toujours vide, la file est vide
            return "La file est vide."
        return self.P2.pop()  # Retirer l'élément en tête de la file

    def is_empty(self):
        return not self.P1 and not self.P2  # La file est vide si P1 et P2 sont vides

# Exemple d'utilisation
file = FileAvecDeuxPiles()
file.enqueue(10)
file.enqueue(20)
file.enqueue(30)
file.enqueue(40)

print(file.dequeue())  # Affiche 10
print(file.dequeue())  # Affiche 20

print(file.is_empty())  # Affiche False

1. Représentation par une matrice d'adjacence
Considérons le graphe non orienté suivant :

   Sommets : A, B, C, D
   Arêtes : (A-B), (A-C), (B-C), (C-D)

a. Construction de la matrice d'adjacence du graphe ci-dessus:
Une matrice d'adjacence est une matrice carrée utilisée pour représenter un graphe. Si le graphe possède n sommets, la matrice sera de dimension n×n. Les éléments de la matrice sont définis comme suit :
   M[i][j] = 1 si le sommet i est adjacent au sommet j.
   M[i][j] = 0 sinon.

Pour le graphe donné, les sommets sont A, B, C, et D. La matrice d'adjacence M sera une matrice :
    
    
 
 
 
 
 
A
 
B
 
C
 
D
 
 
 
 
 
A
 
0
 
1
 
1
 
0
 
 
 
B
 
1
 
0
 
1
 
0
 
 
 
C
 
1
 
1
 
0
 
1
 
 
 
D
 
0
 
0
 
1
 
0
 
 
 
 

    Explication :
 • M[A][B]=1 car il y a une arête entre A et B.
 • M[A][C]=1 car il y a une arête entre A et C.
 • M[A][D]=0 car il n'y a pas d'arête entre A et D.
 • M[B][C]=1 car il y a une arête entre B et C.
 • M[C][D]=1 car il y a une arête entre C et D.
 • Les autres valeurs sont déterminées de manière similaire.

b. Le degré de chaque sommet:
Le degré d'un sommet dans un graphe non orienté est le nombre d'arêtes qui lui sont incidentes. En termes de la matrice d'adjacence, le degré d'un sommet est la somme des éléments de la ligne (ou de la colonne) correspondante à ce sommet.

 • Degré de A : 
 M[A][B]+M[A][C]=1+1=2
 • Degré de B : 
 M[B][A]+M[B][C]=1+1=2
 • Degré de C : 
 M[C][A]+M[C][B]+M[C][D]=1+1+1=3
 • Degré de D : 
 M[D][C]=1

2. Représentation par une liste d'adjacence:
Considérons le graphe orienté suivant :

 Sommets : A, B, C, D
 Arêtes : (A→B), (A→C), (B→C), (C→D), (D→A)

a. Représentation de ce graphe par une liste d'adjacence:
 Une liste d'adjacence est une structure de données où chaque sommet d'un graphe est associé à une liste de ses voisins directs. Pour un graphe orienté, chaque entrée de la liste contient les sommets vers lesquels il existe une arête sortante depuis le sommet correspondant.

La liste d'adjacence pour le graphe donné est :
 • A : [B, C] (A a des arêtes vers B et C)
 • B : [C] (B a une arête vers C)
 • C : [D] (C a une arête vers D)
 • D : [A] (D a une arête vers A)

b. Les degrés entrant et sortant de chaque sommet:
 Pour un graphe orienté :
 Le degré sortant d'un sommet est le nombre d'arêtes sortantes depuis ce sommet.
 Le degré entrant d'un sommet est le nombre d'arêtes entrantes vers ce sommet.
Calculons les degrés entrant et sortant pour chaque sommet :

 • A :
 Degré sortant : 2 (A a des arêtes vers B et C)
 Degré entrant : 1 (D a une arête vers A)
 • B :
 Degré sortant : 1 (B a une arête vers C)
 Degré entrant : 1 (A a une arête vers B)
 • C :
 Degré sortant : 1 (C a une arête vers D)
 Degré entrant : 2 (A et B ont des arêtes vers C)
 • D :
 Degré sortant : 1 (D a une arête vers A)
 Degré entrant : 1 (C a une arête vers D)

1. Parcours en profondeur (DFS)
   Le parcours en profondeur (DFS) explore aussi loin que possible le long de chaque branche avant de revenir en arrière. Voici le détail de l'exercice :

Graphe donné :
   • Sommets : A, B, C, D, E
   • Arêtes : (A-B), (A-C), (B-D), (C-E), (D-E)

    
        
    
Étapes du DFS en partant du sommet A :

 1. Départ du sommet A. Marquer A comme visité.
 • Visité : A
 • Pile : [A]
 2. Explorer le voisin de A, choisir B (premier voisin non visité). Marquer B comme visité.
 • Visité : A, B
 • Pile : [A, B]
 3. Explorer le voisin de B, choisir D. Marquer D comme visité.
 • Visité : A, B, D
 • Pile : [A, B, D]
 4. Explorer le voisin de D, choisir E (C est non adjacent à D). Marquer E comme visité.
 • Visité : A, B, D, E
 • Pile : [A, B, D, E]
 5. Explorer le voisin de E, revenir en arrière car tous les voisins sont visités ou non accessibles.
 6. Retour à D, tous les voisins visités. Revenir à B.
 7. Retour à B, explorer C. Marquer C comme visité.
 • Visité : A, B, D, E, C
 • Pile : [A, B, C]
 8. Fin du parcours, tous les sommets sont visités.

 Ordre de visite en DFS :
 A,B,D,E,C

2. Parcours en largeur (BFS)
 Le parcours en largeur (BFS) explore tous les voisins d'un sommet avant de passer aux voisins de ces voisins. Voici le détail de l'exercice :

Graphe donné :
 • Sommets : A, B, C, D, E
 • Arêtes : (A-B), (A-C), (B-D), (C-E), (D-E)

    
        
    
Étapes du BFS en partant du sommet A :
 1. Départ du sommet A. Marquer A comme visité et ajouter à la file d'attente.
 • Visité : A
 • File d'attente : [A]
 2. Défilement de la file, traiter A. Ajouter les voisins non visités B et C à la file.
 • Visité : A, B, C
 • File d'attente : [B, C]
 3. Défilement de la file, traiter B. Ajouter le voisin non visité D à la file.
 • Visité : A, B, C, D
 • File d'attente : [C, D]
 4. Défilement de la file, traiter C. Ajouter le voisin non visité E à la file.
 • Visité : A, B, C, D, E
 • File d'attente : [D, E]
 5. Défilement de la file, traiter D. Tous les voisins sont déjà visités.
 • Visité : A, B, C, D, E
 • File d'attente : [E]
 6. Défilement de la file, traiter E. Tous les voisins sont déjà visités.
 • Visité : A, B, C, D, E
 • File d'attente : []

 7. Fin du parcours, tous les sommets sont visités.

 Ordre de visite en BFS :
 A,B,C,D,E
    

Algorithme de Dijkstra
L'algorithme de Dijkstra est utilisé pour trouver les plus courts chemins à partir d'un sommet source vers tous les autres sommets dans un graphe pondéré. Voici le détail de l'exercice :

Graphe donné :
  • Sommets : A, B, C, D, E
   • Arêtes pondérées : (A-B, 1), (A-C, 4), (B-C, 2), (B-D, 5), (C-E, 3), (D-E, 1)

    

Étapes de l'algorithme de Dijkstra :

1. Initialisation :
 • Distance de A à lui-même est 0 : d(A)=0
 • Distance de A à tous les autres sommets est infinie : d(B) = ∞, d(C) = ∞, d(D) = ∞, d(E)= ∞
 • Prédécesseur de chaque sommet est inconnu : prédécesseur(B) = NIL, prédécesseur(C) = NIL,prédécesseur(D) = NIL,prédécesseur(E) = NIL.
 • Ensemble des sommets non traités : Q = {A,B,C,D,E}

2. Choisir le sommet avec la plus petite distance non traitée (initialement A) et le marquer comme traité :
 • Sommet courant = A
 • Q = {B,C,D,E}

3. Mettre à jour les distances des voisins de A :
 • d(B)= min(∞,0+1) = 1 et prédécesseur(B) = A
 • d(C)= min(∞,0+4) = 4 et prédécesseur(C) = A

4. Choisir le sommet avec la plus petite distance non traité (B) et le marquer comme traité :
 • Sommet courant = B
 • Q = {C,D,E}

5. Mettre à jour les distances des voisins de B :
 • d(C) = min(4,1+2)=3 et prédécesseur(C) = B
 • d(D) = min(∞,1+5)=6 et prédécesseur(D) = B

6. Choisir le sommet avec la plus petite distance non traité (C) et le marquer comme traité :
 • Sommet courant = C
 • Q = {D,E}

7. Mettre à jour les distances des voisins de C :
 d(E) = min(∞,3+3) = 6 et prédécesseur(E) = C

8. Choisir le sommet avec la plus petite distance non traité (D) et le marquer comme traité :
 • Sommet courant = D
 • Q = {E}

9. Mettre à jour les distances des voisins de D :
 d(E) = min(6,6+1) = 6 (pas de changement) et prédécesseur(E) = C

10. Choisir le sommet avec la plus petite distance non traité (E) et le marquer comme traité :
 • Sommet courant = E
 • Q = {}

Finalement, voici la liste des distances et les chemins les plus courts en partant du sommet A:
        
 
 
 
 
Noeud
 
Valeur
 
Chemin
 
 
 
 
 
A
 
0
 
A
 
 
 
B
 
1
 
A → B
 
 
 
C
 
3
 
A → B → C
 
 
 
D
 
6
 
A → B → D
 
 
 
E
 
6
 
A → B → C → E
 
 
 
   
    

a. Est-ce que ce graphe est biparti ? Justifiez votre réponse.
    Un graphe est biparti s'il est possible de diviser les sommets en deux ensembles disjoints U et V tels que chaque arête connecte un sommet de U à un sommet de V, et qu'il n'y a pas d'arête entre deux sommets du même ensemble.

   Pour vérifier si un graphe est biparti, on peut utiliser un parcours en largeur (BFS) ou en profondeur (DFS) pour essayer de colorier le graphe avec deux couleurs (disons rouge et bleu) de telle manière que deux sommets adjacents n'ont pas la même couleur. Si c'est possible, le graphe est biparti ; sinon, il ne l'est pas.

Vérification avec un parcours en largeur (BFS) :
 1. Initialisation :
     • Marquer tous les sommets comme non colorés.
       • Choisir un sommet de départ, par exemple A, et le colorier en rouge.
  2.Parcours en largeur :
     • Colorier les voisins du sommet de départ en bleu.
     • Pour chaque sommet colorié en bleu, colorier ses voisins non colorés en rouge.
        • Continuer ce processus pour chaque sommet jusqu'à ce que tous les sommets soient colorés ou qu'une contradiction soit trouvée (deux sommets adjacents avec la même couleur).

Application de l'algorithme :
 1. Coloration de départ :
       • A : rouge 
        • B,C,D : non colorés
   2. Coloration des voisins de A :
        B, C, D : bleu
  3. Vérification des voisins de B :
      • A (rouge) est correct
     • C (bleu) → contradiction car B est aussi bleu

Une contradiction a été trouvée. Le graphe n'est donc pas biparti.

b. Coloriez le graphe en utilisant le minimum de couleurs possibles. Expliquez votre démarche.
 Pour colorier un graphe en utilisant le minimum de couleurs possibles, on peut utiliser l'algorithme de coloration gloutonne. Cet algorithme attribue à chaque sommet la couleur la plus basse possible qui n'a pas encore été utilisée par ses voisins.

Démarche de coloration gloutonne :
  1. Initialisation :
     • Marquer tous les sommets comme non colorés.
       • Préparer une liste de couleurs disponibles.

   2. Choix des couleurs pour chaque sommet :
      Pour chaque sommet, attribuer la couleur la plus basse qui n'est pas utilisée par ses voisins.

  Application de l'algorithme :

   1. Coloration du sommet A :
     Couleur : 1 (rouge)
 2. Coloration du sommet B :
     Voisins colorés : A (rouge)
     Couleur disponible : 2 (bleu)
       Couleur : 2 (bleu)
  3. Coloration du sommet C :
     Voisins colorés : A (rouge), B (bleu)
       Couleur disponible : 3 (vert)
       Couleur : 3 (vert)
  4. Coloration du sommet D :
     Voisins colorés : A (rouge), C (vert)
       Couleur disponible : 2 (bleu)
       Couleur : 2 (bleu)

Résultat de la coloration :
    
 
 
 
 
Noeud
 
Valeur (Couleur)
 
 
 
 
 
A
 
1 (rouge)
 
 
 
B
 
2 (bleu)
 
 
 
C
 
3 (vert)
 
 
 
D
 
2 (bleu)
 
 
 
 

Solution en cours...

Solution en cours...

Solution en cours...

Solution en cours...

Solution en cours...

    
1. Algorithme de Kruskal :
 Arêtes sélectionnées :
 • (D-E, 1)
 • (B-C, 2)
 • (A-D, 3)
 • (B-D, 4)
 Poids total = 1 + 2 + 3 + 4 = 10

2. Algorithme de Prim :
 Arêtes sélectionnées :
 • (A-D, 3)
 • (D-E, 1)
 • (B-D, 4)
 • (B-C, 2)
 Poids total = 3 + 1 + 4 + 2 = 10

Solution en cours...

Solution en cours...

Solution en cours...

Solution en cours...

Solution en cours...

Solution en cours...

Solution en cours...

Solution en cours...

Solution en cours...

Solution en cours...