# Théorie des graphes
# Cryptographie
##### Introduction : stéganographie, cryptographie, codes, chiffres, chiffrer, déchiffrer, décrypter, cryptanalyse.
**Stéganographie** : Art de dissimuler un message dans un autre message ou objet pour qu'il passe inaperçu.\
**Cryptographie** : Art de brouille un message pour le rendre inintelligible à toute personne non autorisée.\
**Codes** : Remplacent des unités linguistiques par d'autres mots ou groupes de mots à l'aide d'un dictionnaire.\
**Chiffres** : Transforment les caractères ou blocs de caractères sans tenir compte de la valeur linguistique ou sémantique.\
**Chiffrer** : Action de transformer un message en une forme initelligible pour le protéger.\
**Déchiffrer** : Action de reconvertir le message chiffré en sa forme originale.\
**Décrypter** : casser un code ou chiffre sans avoir la clé de déchiffrement, généralement par des techniques de cryptanalyse.\
**Cryptanalyse** : étude des systèmes de cryptographie et des techniques pour casser les codes et chiffres afin de retrouver le message original sans connaitre la clé de
déchiffrement.
##### Quelles sont les caractéristiques des différentes méthodes de chiffrement abordées dans le cours ? (Transposition / substitution / permutation, mono / poly-alphabétique, cohérente / incohérente). Quelles sont leurs faiblesses éventuelles ?
**Transposition** : Consiste à réarranger les caractères du message en clair selon un certain schéma pour obtenir le message chiffrer. Cela n'altère pas les caractères eux-même, mais change leur ordre.
- Faiblesse :
- Sensible à l'analyse fréquentielle, car les fréquences des caractères restent inchangées.
- Relativement facile à casse si l'attaquant connait ou devine le schéma de transposition.
**Substitution** : Consiste à remplacer chaque caractère du message en clair par un autre caractère.
- Type :
- **Monoalphabetique** : Un seul alphabet de substitution est utilisé.
- **Polualphabétique** : Plusieurs alphabets de substitution seront utilisés.
# Graphes non orientés
##### Définir et illustrer les notions suivantes : graphe fini (non orienté), ordre, graphe pondéré, liste d'adjacence.
**Graphe fini** : Ensemble fini d'arrêtes et de sommets.\
**Ordre**: Nombre de sommets du graphe\
**Graphe pondéré** : Graphe où chaque arête à une valeur numérique.\
**Liste d'adjacence** : Représentation d'un graphe sous forme de liste. On liste, pour chaque sommet, ses sommets adjacents.
##### Définir et illustrer mes notions suivantes : graphe simple, multigraphe, p-graphe, graphe complet, graphe bipartie/biparti complet.
**Graphe simple** : Un graphe est simple si une arête relie au plus 2 sommets et n'a pas de boucle sur un sommet.\
**Multigraphe** : Contraire au graphe simple.\
**P-graphe** : Graphe mutligraphe pour lequel il y a au plus p arêtes entre 2 sommets.\
**Graphe complet** : Si chaque sommet du graphe est relié directement à tous les autres sommets.\
**Graphe biparti** : Si ses sommets peuvents être divisé en 2 ensembles X et Y, pour que chaque sommet de X soit lié à au moins un sommet de Y et vice versa.\
**Graphe biparti complet** : Graphe biparti où chaque sommet de X est relié à tous les sommets de Y et vice versa.
##### Définir et illustrer les notions suivantes : graphe connexe, non connexe, pont, graphe partiel, sous-graphe, clique.
**Graphe connexe** : possible d'atteindre n'importe quel sommet depuis un sommet de départ en suivant les arêtes.\
**Grpahe non connexe** : se décompose en plusieurs composants connexes.\
**Pont** : Est une arête si quand elle est supprimée, ça augment le nombre de composantes connexes.\
**Graphe partiel** : Graphe où on a enlevé des arêtes.\
**Sous-graphe** : Grpahe où on a enlevé un ou plusieurs sommets (et ses arêtes associées).\
**Clique** : sous-graphe complet d'un graphe.
##### Définir et illustrer les notions suivantes : dégré d'un sommets, degré d'un graphe nnon orienté, graphe k-régulier.
**Degré d’un sommet** : nombre d’arêtes associées à ce sommet et noté d(v).\
**Degré d’un graphe non orienté** : degré maximum de tout ses sommets.\
**Graphe k-régulier** : graphe où tous les sommets ont le même degré.\
##### Démontrer que la somme des degrés des sommets d’un graphe est égale à 2 fois le nombre d’arrêtes.
Chaque arête ajoute 1 degré aux sommets qu'elle relie => chaque arête ajoute 2 degrés (un pour chaque sommet). \
Donc, la somme des degrés est bien égale au double du nombre d'arêtes.
##### Démontrer qu'un graphe simple a un nombre pair de sommets de degré impair.
La somme des degrés des sommets d’un graphe est égale à 2 |E|, donc elle est paire. Or, la somme d’un nombre impair de degrés impairs est elle-même impaire. En l’ajoutant aux degrés pairs (qui donnent une somme paire), on obtiendrait une somme totale impaire, ce qui est impossible. Ainsi, le nombre de sommets de degré impair doit être pair.
##### Démontrer que dans une assemblée de n personnes, il y a toujours au moins 2 personnes qui ont le même nombre d’amis présents.
Dans un graphe simple avec n sommets, le degré d'un sommet peut varier entre 0 (aucun ami) et n-1 (ami avec tous les autres sommets).\
Si quelqu'un a 0 ami, alors cette personne n'est amie avec personne.\
Si quelqu'un a n-1 ami, alors cette personne est amie avec tout le monde.\
Si une personne est amie avec tout le monde alors il n'y a personne sans amis et le contraire est aussi viable. Alors aucune personne ne peut avoir n-1 amis ce qui nous donne une contradiction : \
Impossible que toutes les personnes aient un nombre unique d'amis.\
Au moins 2 personnes doivent partager le même nombre d'amis.
# PERT exercices
#### Exercice 73
| A
| | 3
|
| B
| | 9
|
| C
| | 5
|
| D
| A
| 8
|
| E
| B
| 4
|
| F
| B
| 7
|
| G
| B
| 20
|
| H
| C, F
| 6
|
| I
| D, E
| 5
|
[](https://wiki.hugo-pierret.be/uploads/images/gallery/2025-08/image.png)
#### Exercice 74
| A
| | 4
|
| B
| | 2
|
| C
| A
| 1
|
| D
| A, B
| 1
|
| E
| A
| 2
|
| F
| C
| 2
|
| G
| D, F
| 2
|
| H
| E
| 10
|
| I
| G
| 4
|
| J
| H, I
| 1
|
[](https://wiki.hugo-pierret.be/uploads/images/gallery/2025-08/uXuimage.png)
#### Chemin Critique 1
| A
| | 10
|
| B
| A
| 9
|
| C
| B
| 1
|
| D
| C
| 9
|
| E
| C
| 1
|
| F
| D
| 5
|
| G
| D
| 9
|
| H
| A, F
| 2
|
| I
| A, F
| 5
|
| J
| G, H
| 9
|
# Annexe
[](https://wiki.hugo-pierret.be/uploads/images/gallery/2025-08/image-1755867107257.jpg)
[](https://wiki.hugo-pierret.be/uploads/images/gallery/2025-08/image-1755953759591.png)
[](https://wiki.hugo-pierret.be/uploads/images/gallery/2025-08/image-1755959590242.gif)