# Réseaux et Télécommunications

Culture générale
Problème technique :
-énoncer les avec des termes naturels
-le transformer en problème mathématique
-cette solution est-t-elle décidable ?
-non décidable
-décidable
-complexité
-polynomial (Algorythme)
-exponentielle (Heuristique)

Algorythmique : choix le plus optimal, utilisation de l'algoryhtme
Heuristique : Brut force, passage en force

## Introduction

**deux controles prévu à l'avance avec document autorisé**

## Cours 1 - Rappel sur les Graphes

### Graphe non orientés et orientés.

Un graphe G=(X,Y) non orienté est un couple formé d'un ensemble X (sommets de G) et un ensemble Y de paires des sommets(appelées arêtes de G)

G={1,2}{1,3}{2,4}

Un graphe G=(X,Y) non orienté est un couple formé d'un ensemble X (sommets de G) et un ensemble Y de **couples** des sommets(appelées **arcs** de G)

Exemple :

Un graphe G non orienté est une suite de sommets tels que {Xi,Xi+1} est une arête de ce graphe
i=1,...,k-1

### connexité

Un graphe non orienté est **connexe** si Xi,Xj appartient à une chaine de Xi à Xj

/!\ En gros si à partir de n'importe quel point tu peux accéder à n'importe quel autre, c'est connexe. Un point seul est considéré comme connexe lui même /!\

**Un point d'accumulation** est un point qui lorsqu'il est retiré coute l'accès à une partie du graphe

Une liasion, un arc ou une arête est appélé **dangereuse** si lorsque la liasion est coupé une partie du graphe est déconnecté

### Complémentarité

Un grage G| est **complémentaire** de G lorque on entoure les deux graphes avec deux bulles A et B et que l'on connecte les deux avec une super-arête quirrelie A et B

Un graphe complémentaire d'un autre est un graphe ou chaque sommet et connecté à ces sommets adjacent dans G

## Réseau sans longue chaine

On utilise le **Principe de décomposition d'un graphe en des sous-graphes **
/!\ Diviser pour mieux régner /!\

Soit G un graphe et P un problème qui porte sur G
1) on découpe G en sous graphes en suivant un ou plusieurs opérateurs de décomposition O
2) Nous essayons de résoudre P sur chacun des sous-graphes G1,G2,G3 et G4 obtenu par l'étape 1
3) On essaye de résoudre P sur G à partir des solutions sur les sous-graphes

### Coloriage d'un graphe

Soit un graphe G=(X,Y), un coloriage est l'attribution d'une couleur à chaque sommet de telle sorte que deux sommets adjacents n'aient pas la même couleur

La distribution des ressources rares peut être résolu par le coloriage

### Les cographes

Théorème : si G est non connexe et G| est connexe.
Soit C1, C2, ..., Ck les composants connexes de G K>=2
Soit x,y,z des sommets de G

A) X appartient à C1, Y appartient à C2 et i != de j, dans G| X est adjacent de Y

B) x,y appartient donc a C1 soit Z appartenant à C2, j !=i alors dans G| aura X et Z adjacent et Z et Y adjacent

#### Definition

Le graphe G est un cographe s'il peut être décomposé à son ensemble de sommets

Grpahe -> connexe ou pas -> on prend en entier ou les morceaux décomposés et on fait la complémentarité

On trouve le composant complémentaire du connexe et complémentaire du connexe après à nouveau une complémentaire
jusqu'a le décomposé en entier
Exemple : VOIR FEUILLE DE COURS A4

## Cours 2