# Les graphes

### Partie 1 : Caractériser un graphe

1. **Qu'est ce qu'un graphe ?**
> Les graphes sont des **objets mathématiques**. Les cercles sont appelés des **sommets** et les segments de droites qui relient 2 sommets des **arêtes**.
:::info
> en informatique, les graphes sont utilisés pour sotocker de la donnée (information) : ce sont doncees structures de données
:::

2. Définir ce qu'est l'ordre d'un graphe.
> C'est le nombre de sommets contens dans un graphe
3. Etablirr un comparatif entre les graphes et les structures de données jusque là (arbres, listes, dictionnaires, tuples).

| | Graphes | Arbres | listes, tuples, dictionnaires |
|:-----------:|:---------------------------------------------------:|:--------------------------------------------------------------------------:|:---------------------------------------------------------------------:|
| Utilisation | résaux sociaux résaux informatiques, résaux routier | organigrammes, arbre généralogique, arbre de décision, systeme de fichiers | Données à parcourir séquenciellement, données avec mappinf clé/valeur |
| Type | Structure de données relationnelles | structure de données hiérarchiques | Structure de données linéaires |

4. Défnir la notion d'adjacence dans le cadre des graphes
> L'adjacence dans un graphe signifie que deux nœuds sont directement connectés par un bord.
5. Qu'est ce que le degré d'un sommet
> C'est le nombre d'arrete qui sont liées à ce sommet
6. Qu'est ce qu'un sommet isolé au sein d'un graphe ?
> Un sommet dont le degrés == 0
> sommet qui n'est pas adjacents aux autres noeuds du graphe
7. Qu'est ce qu'un graphe complet ?
> Un graphe complet est un graphe où chaque paire de sommets est reliée par une arête. Tous les sommets sond adjacents entre eux
8. Qu'est ce qu'un graphe orienté ?
> Une arete ne peut être parcourue que dans 1 sens indiquée par une fleche
9. Qu'est ce qu'un graphe non orienté ?
> Chaques arretes peuvent être parcourue dans les 2 sens

#### Application du cours :

1/ Degres des sommets :
* A : 3
* B : 2
* C : 3
* D : 5
* E : 3
* F : 2

2/ Lordre de ce graphe est de 6
3/ Non le graphe n'est pas complet.

### Partie 2 :
#### Propriété de la somme des degres
Le nombre d'arretes est égal à la moitiée de la somme des degrès des sommets
Ce résultat s'explique assez facilement : en ajoutant les degres de chaques sommets (c'est à dire le nombred'aretes issues de ce sommet), on comptabilise deux fois chauqes arretes (une fois avec le sommet d'un extrémitée et une seconde fois avec le sommet de l'autre extrémitée de l'arrete). D'où le résultat.
Il découle de cette propriétée que la somme des degrès des sommets est nécéssairement paire et donc que le nombre de sommets de degres impaire est paire
#### Matrice d'adjacence


### Matrice d'adjacence du graphe du réseau social :

| | A | B | C | D | E | F |
|:---:|:---:| --- | --- |:---:|:---:|:---:|
| A | 0 | 1 | 1 | 1 | 0 | 0 |
| B | 1 | 0 | 0 | 1 | 0 | 0 |
| C | 1 | 0 | 0 | 1 | 1 | 0 |
| D | 1 | 1 | 1 | 0 | 1 | 1 |
| E | 0 | 0 | 1 | 1 | 0 | 1 |
| F | 0 | 0 | 0 | 1 | 1 | 0 |

matrice d'ajacence avec diagonale de 0 : noeud n'as pas d'arrete sur lui même

1. Qu'est ce qu'une chaine ?
> On appelle chaine toute succession d'arretesdont l'éxtrémitées de l'une (sauf la dernierre) est l'orifine de la suivante? Le nombre d'aretes qui composent une chaine est appelé longeur de la chaîne.
2. Qu'est ce qu'une chaine fermée?
> Une chaine fermée est une chaine dont le début et la fin est le même point
> On appele chaine fermée toute chaine dont l'origine et l'extrémitée coincides.
3. Qu'est ce qu'un cycle?
> C'est une chaîne fermée dont les arêtes sont toutes distinctes


https://math.univ-lyon1.fr/irem/Formation_ISN/formation_parcours_graphes/graphe/3_chaine_cycle.html

### Conexité
1. Qu'est-ce qu'un graphe connexe ? (à schématiser)
> Un graphe est connexe quand tout sommet peut être relié à tout autre sommet par une arête ou une suite d'arêtes. Le graphe connexe est un graphe en un seul morceau.
>
> 

2. Qu'est-ce qu'un graphe complet ? (à schématiser)
>Un graphe complet est un graphe dont chaque sommet est relié directement à tous les autres sommets.
> Remarque : un graphe complet est donc nécéssairement connexe mais la réciproque est fausse
> 

> Il est connexe mais pas complet.

### Chaînes et cycles eulériens

1. Qu'est-ce qu'une chaîne eulérienne ?
> C'est une chaîne qui contient une fois et une seule toutes les arêtes du graphe.
2. Qu'est-ce qu'un cycle eulérien ?
> C'est une chaine eulérienne fermée
3. Définir le théorème d'Euler
> Soit G un graphe connexe.
>
> G admet un cycle eulérien si et seulement si tous les sommets de G sont de degré pair.
>
> G admet une chaîne eulérienne (non fermée) si et seulement si le nombre de sommets de degré impair dans G est 2.
>
> Si tel est le cas, les extrémités de la chaîne eulérienne sont les deux sommets de degré impair
>
> Non ce n'est ni une chaine eulérienne ni un cycle eulérien


## Partie 3 : parcourir un graphe
### 3.1 : représentation machine

Il existe de nombreuses fasons de représenter un graphe en machine selon la nature du graphe et la nature desopérations et la nature des opérations/algo à effectuer sur ce graphe.

Il existe 2 sortes d'opérations qu'il est possible d'executer sur un graphe :
- les opérations de construction
- initialisation / ajout / supression de noeuds / d'arretes
- les opérations de parcours
- représentation matrice d'adjacence

Proposer une implémentation de graphe
Elle doit inclure :
- ajout / supression de Noeuds
- ajout / supression d'arretes
- des parcours

Faire plusieurs propositions : théorie
poo : diagramme de classe
dictionnaire : montrer a quoi il ressemble (ex: {1: [2,4], 2: [1], 3: [4], 4: [1,3]})

trouve la meilleur implémentation possible

rendu : g-sheet
description

(noeud avec la liste des sommets dont il est relié)

Mercredi :intero tri insertion / rendu partie 1 de l'activitée
Jeudi : présentation tri selection (1h) debut sql

https://www.zonensi.fr/NSI/Terminale/C09/graphe_python/

### Implémentation du graphe:
#### Par matrice d'adjacence

exemple : tab = [[0,1,01], [1,0,0,1], [0,0,0,1], [1,1,1,0]]

#### Par liste d'adjacence

ex: {1: [2,4], 2: [1], 3: [4], 4: [1,3]}

pour densite : matrice d'adjacence sinon : objets
matrice d'adjacence interessante car modules déjà axistant (panda, numpy,...) (mais possède une limite :objects sont des objets consécutifs connus d'avance)