Annexe 1
Solution donnée par l'Algorithme exacte de coloration
|
N° de la cellule
|
Antenne principale
|
Fréquence attribuée
|
|
Cellule 1
|
A
|
La 2~eme fréquence
|
|
Cellule 2
|
C
|
La 3~eme fréquence
|
|
Cellule 3
|
C
|
La 1~erefréquence
|
|
Cellule 4
|
P
|
La 2~eme fréquence
|
|
Cellule 5
|
A
|
La 3~eme fréquence
|
|
Cellule 6
|
A
|
La 1~erefréquence
|
|
Cellule 7
|
D
|
La 2~eme fréquence
|
|
Cellule 8
|
G
|
La 3~eme fréquence
|
|
Cellule 9
|
P
|
La 3~eme fréquence
|
|
Cellule 10
|
Q
|
La 1~erefréquence
|
|
Cellule 11
|
R
|
La 2~eme fréquence
|
|
Cellule 12
|
B
|
La 1~erefréquence
|
|
Cellule 13
|
E
|
La 2~eme fréquence
|
|
Cellule 14
|
D
|
La 3~eme fréquence
|
|
Cellule 15
|
G
|
La 1~eme fréquence
|
|
Cellule 16
|
K
|
La 2~erefréquence
|
|
Cellule 17
|
M
|
La 3~eme fréquence
|
|
Cellule 18
|
M
|
La 1~erefréquence
|
|
Cellule 19
|
Q
|
La 2~eme fréquence
|
|
Cellule 20
|
Q
|
La 3~eme fréquence
|
|
Cellule 21
|
R
|
La 1~eme fréquence
|
|
Cellule 22
|
B
|
La 2~eme fréquence
|
|
Cellule 23
|
F
|
La 3~eme fréquence
|
|
Cellule 24
|
E
|
La 1~erefréquence
|
|
Cellule 25
|
H
|
La 2~eme fréquence
|
|
Cellule 26
|
H
|
La 3~eme fréquence
|
|
Cellule 27
|
K
|
La 1~erefréquence
|
|
Cellule 28
|
N
|
La 2~eme fréquence
|
|
Cellule 29
|
N
|
La 3~eme fréquence
|
|
N° de la cellule
|
Antenne principale
|
Fréquence attribuée
|
|
Cellule 30
|
F
|
La 1~eme fréquence
|
|
Cellule 31
|
F
|
La 2~eme fréquence
|
|
Cellule 32
|
I
|
La 3~erefréquence
|
|
Cellule 33
|
I
|
La 1~erefréquence
|
|
Cellule 34
|
L
|
La 2~eme fréquence
|
|
Cellule 35
|
O
|
La 3~eme fréquence
|
|
Cellule 36
|
O
|
La 1~erefréquence
|
|
Cellule 37
|
J
|
La 3~eme fréquence
|
|
Cellule 38
|
J
|
La 1~erefréquence
|
|
Cellule 39
|
I
|
La 2~eme fréquence
|
|
Cellule 40
|
L
|
La 3~erefréquence
|
|
Cellule 41
|
L
|
La 1~erefréquence
|
Annexe 2
Rappel sur la théorie des graphes
Introduction
La théorie des graphes est utilisée dans un
grand nombre de disciplines (mathématiques, physique, économie,
etc.). Les recherches en théorie des graphes sont essentiellement
menées par des informaticiens, du fait de l'importance des aspects
algorithmiques (recherche de solutions). Il s'agit essentiellement de
modéliser des problèmes :
· on exprime un problème donné en termes de
graphes;
· il devient alors un problème de «
théorie des graphes » que l'on sait le plus souvent résoudre
car il rentre dans une catégorie de problèmes connus.
Les solutions de problèmes de graphes peuvent être
:
· faciles et efficaces (car le temps nécessaire pour
les traiter par informatique est raisonnable car il dépend
polynomialement du nombre de sommets du graphe) ;
· difficiles (car le temps de traitement est exponentiel) ;
dans ce cas on utilisera une heuristique, c'est-à-dire un processus de
recherche d'une solution - pas forcément la meilleure.
Qu'est-ce qu'un graphe?
Définition 1
On appelle graphe G = (X; A) la donn ee d'un ensemble X dont
les el ements sont appelés sommets et d'une partie de A
symétrique((x; y) E A (y; x) E A) dont les éléments sont
appelés arêtes.
En présence d'une arête a = (x; y) qui peut
être notée simplement xy, on dit que x et y sont les
extrémités de a, que a est incidente en x et en y, et que y est
un successeur ou voisin de x (et vice versa).
On dit qu'un graphe est sans boucle si A ne contient pas
d'arête de la forme (x; x), c'esta-dire joignant un sommet a
lui-même.
Le nombre de sommets est appelé ordre du graphe.
Un graphe ne possédant pas de boucle ni d'arêtes
parallèles (deux arêtes distinctes joignant la même paire de
sommets) est appelé graphe simple ou 1-graphe. En revanche un p-graphe
ou graphe généralisé est un graphe pour lequel il n'existe
jamais plus de p arêtes de la forme (x;x).
Graphiquement, les sommets peuvent être
représentés par des points et l'arête a = (x; y) par un
trait reliant x à y. On notera que la disposition des points et la
longueur ou la forme (rectiligne ou incurvée) des traits n'a aucune
importance. Seule l'incidence des différentes arêtes et sommets
compte.
Définition 2
On appelle graphe orienté ou digraphe G = (X; A) la
donnée d'un ensemble X dont les éléments
sont
appelés sommets et d'une partie A de X x X dont les
éléments sont appelés arcs ou arêtes.
En présence d'un arc a = (x; y) qui peut être
noté simplement xy, on dit que x est l'origine (ou
extrémité initiale) et y l'extrémité (terminale) de
a, que a est sortant en x et incident en y, et que y est un successeur de x
tandis que x est un prédécesseur de y. On dit aussi que x et y
sont adjacents.
Définition 3
Un graphe non orienté n'est qu'un graphe
orienté symétrique ; si un arc relie le sommet a au sommet b, un
autre arc relie le sommet b au sommet a : on ne trace alors qu'un trait entre a
et b que l'on appelle une « arête ».
Degré d'un graphe
On appelle degré sortant ou demi-degré
extérieur d'un sommet x le nombre d'arcs de la forme a = (x; y) avec y
=6 x, c'est- a-dire le nombre d'éléments de ['(x)\ {x} ( ['(x)
l'ensemble des successeurs d'un sommet x E X).
On note d5(x)ce degré.
On appelle degré entrant ou demi-degré
intérieur d'un sommet x le nombre d'arcs de la forme a = (y; x) avec y
=6 x, c'est- a-dire le nombre d'éléments de ['~1(x)\
{x} (['~1(x) l'ensemble des prédécesseurs d'un sommet
x E X).
On note de(x) ce degré.
On appelle degré de x (ou valence) la somme du
degré entrant et du degré sortant.
Un sommet de degré entrant non nul et de degré
sortant nul est appelé puits, tandis qu'un sommet de degré
entrant nul et de degré sortant non nul est appelé source.
Un sommet n'ayant pas d'arcs incidents est appelé
sommet isolé ; ces sommets ont un degré nul. Deux arcs adjacents
sont dits "en série" si leur sommet commun est de degré egal
à deux. Dans la définition d'un graphe, l'ensemble des arcs A
peut être vide; dans ce cas, on a affaire à un graphe nul. Tous
les sommets d'un graphe nul sont donc des sommets isolés. En revanche,
l'ensemble des sommets X ne peut être vide sinon le graphe correspondant
n'existe pas. Cela signifie donc qu'un graphe comporte au moins un sommet.
Matrice d'adjacence
Considérons un graphe G = (X; A) comportant n sommets. La
matrice d'adjacence de G est égale à la matrice U = (uij) de
dimension n x n telle que
~ 1 si (i; j) E A (c'est-a-dire (i; j) est une arête)
uij = 0 sinon
Une telle matrice, ne contenant que des "0" et des "1" est appel
ee, de manière générale, une matrice booléenne.
Un graphe orienté quelconque à une matrice
d'adjacence quelconque, alors qu'un graphe non orienté possède
une matrice d'adjacence symétrique. L'absence de boucle se traduit par
une diagonale nulle.
La matrice d'adjacence poss ede quelques propri et es qui
peuvent être exploitées. Considérons un graphe G et sa
matrice d'adjacence associée U :
· la somme des eléments de la i~eme ligne
de U est égale au degré sortant d5(xi) du sommet xi de
G.
· la somme des eléments de la j~eme
colonne de U est égale au degré entrant de(xj) du
sommet xj de G.
· U est symétrique si, et seulement si, le graphe G
est symétrique.
Définition d'un stable:
Un sous ensemble de sommetsI C X d'un graphe G = (X, A) est un
stable s'il ne comprend que des sommets non adjacents deux à deux:
ViE I,Vj E I - (i,j) E= A.
Coloriage des sommets d'un graphe
Définitions
La coloration des sommets d'un graphe consiste à
affecter à tous les sommets de ce graphe une couleur de telle sorte que
deux sommets adjacents ne portent pas la même couleur. Une coloration
avec k couleurs est donc une partition de l'ensemble des sommets en k parties
stables. Le nombre chromatique, noté x(G); du graphe G est le plus petit
entier k pour lequel il existe une partition de X en k sous-ensembles
stables.
Encadrement du nombre chromatique
Majoration x (G) < A (X) + 1, où A (X) est le plus
grand degré de ses sommets.
Minoration Le nombre chromatique d'un graphe est supérieur
ou égal à celui de chacun de
ses sous graphes.
Le nombre chromatique du graphe sera supérieur ou
égal à l'ordre de sa plus grande clique
x(G) ~ w(G).
Acronymes
ADSL: Asymetric Digital Subscriber Line.
BS : Base Station.
BTS: Base Transceiver Station. CPE: Customer Premise
Equipement.
DSL: Digital Subscriber Line.
EDGE: Enhanced Data Rates for GSM Evolution.
FAP: Frequency Assignement Problem.
IEEE: Institute of Electrical and Electronics Engineer.
IP: Internet Protocol.
LOS: Line Of Sight.
NLOS: Non Line Of Sight.
OFDM: Orthogonal Frequency Division Multiplexing.
OFDMA: Orthogonal Frequency Division Multiple Access. QoS: Qualiy
of Service.
UMTS: Universal Mobile Telecomunication System.
WiFi: Wirless Fidelity.
Wimax: Worldwide Interoperability for Microwave Acces.
| 
