---
# System prepended metadata

title: Theorie des graphs 1
tags: [' ING1', theorie des graphs, ' S6']

---

---
lang: fr
tags: theorie des graphs, S6, ING1
title: Theorie des graphs 1
---

# Theorie des graphs 1


### Quels sont les problèmes qui utilisent les graphs ?

- Flots
    - Réseaux
- Plus court chemins :warning:
    - Itinéraire
    - Ordonnancement
    - Finance
- arches courants
    - Réseaux
- Tri topologique :+1:
    - Tableur, ordonnencement
- Connexité, k-connexité :+1:
    - Réseaux, automates
- planarité
    - Chimie, elec, représentationn -> éppaisseur d'un graph
    - NP-Hard
- coloration de graph
    - allocation de ressources
    - NP-Complet
- Circuit eulériens :warning:
    - CNS: Un circuit eulérien existe ssi le graph est connexe et tous ses sommets sont de degrès paire
- Circuit hemiltonien
    - NP-Hand -> Optimisation
- Voyageur de commerce
    - NP-Hand -> Optimisation
- isomorphisme de graph
    - Crypto, chimie
    - NP
- couplage/mariage :warning:
- Clique maximal
    - matching de structure
    - NP-Complet

> :warning: : Au programme
> :+1: : Si on a le temps...

En algo un arbre est un graphe non orienté acyclique et connexe.

++Ex:++ Deux arbres égaux

```graphviz
graph G {
    1--2--3--4
    2--5
    6--2
}
```

```graphviz
graph G {
    rankdir=LR
    1--2--3--4
    2--5
   
   6--2
}
```

==Graphs isomorphes==: 

==Tri topologique==: Pour gérer les dépendances (dans un makefile par exemple).

```graphviz
digraph G {
    rankdir = LR
    node [shape=box]
    make->main [color=red]
    main->{file1,file2}
    file1->{lib1}
    file2->{file3,lib2}
}
```

==Connexité==: Un graph est dit connexe si on peut relier n'importe quelle paire de sommet.

==k-connexe==: Quand on retire k arrêtes, alors on reste connexe. Par exemple, un bi-connexe (2-connexe) est arbre qui reste connexe même en retiré 2 arrêtes. Autrement dit, pour chaque sommet on peut atteindre tous les autres points via 2 chemins différents.

== composante fortement connexe==: Quand on a un sous graphs connexe dans le graph.

++Ex++: deux sous graphs fortement connexe

```graphviz
digraph G {
    rankdir = LR
    subgraph cluster_0 {
        A->B->C->D->A
    }
    subgraph cluster_1 {
        E->F->G->H->E
    }
    D->E
}
```

==graph planaire==: si on **peut** le dessiner sans croiser d'arrêtes.

