--- 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.