Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g,...
-
Upload
truongcong -
Category
Documents
-
view
215 -
download
0
Transcript of Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g,...
![Page 1: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/1.jpg)
Aspectos combinatorios en problemas de comunicaciones
Oriol Serra AlbóCombinatoria, Teoría de Grafos y aplicaciones
Dept. Matemàtica aplicada IVUniversitat Politècnica de Catalunya
![Page 2: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/2.jpg)
Aspectos combinatorios en problemas de comunicaciones
Combinatoria, Teoría de Grafos y aplicaciones
Aplicación de la Teoría de grafos al análisis y diseño de redesde interconexión:
Grandes redesTransmisión y difusión de la informaciónVulnerabilidad y fiabilidad
![Page 3: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/3.jpg)
Redes estructuradasRedes de área localRedes para sistemas multiprocesadoresRedes de comunicaciones fijas
Redes amorfasRedes de comunicaciones móvilesRed internet
Aspectos combinatorios en problemas de comunicaciones
Aplicación de la Teoría de grafos al análisis y diseño de redesde interconexión:
Grandes redesTransmisión y difusión de la informaciónVulnerabilidad y fiabilidad
![Page 4: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/4.jpg)
Redes estructuradasRedes de área localRedes para sistemas multiprocesadoresRedes de comunicaciones fijas
Redes amorfasRedes de comunicaciones móvilesRed internet
Aspectos combinatorios en problemas de comunicaciones
Construcción de redes de pequeño diámetroProblemas de encaminamientoEl problema de la asignación de frecuencias
![Page 5: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/5.jpg)
Problema ( , )Dados el grado maximo
1. Construccion de grafos de peque
y el diametro , maximizar e
ño diametro:
l numero de dos. noD
D∆
∆
![Page 6: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/6.jpg)
Problema ( , )Dados el grado maximo
1. Construccion de grafos de peque
y el diametro , maximizar e
ño diametro:
l numero de dos. noD
D∆
∆
( )G∆
![Page 7: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/7.jpg)
Problema ( , )Dados el grado maximo
1. Construccion de grafos de peque
y el diametro , maximizar e
ño diametro:
l numero de dos. noD
D∆
∆
( )G∆
( )( ( ) 1)G G∆ ∆ −
![Page 8: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/8.jpg)
Problema ( , )Dados el grado maximo
1. Construccion de grafos de peque
y el diametro , maximizar e
ño diametro:
l numero de dos. noD
D∆
∆
( )G∆
( )( ( ) 1)G G∆ ∆ −
( 1) 2( , ) , Cota de Moore2(log )
D
n D
D n∆
∆ ∆ − −∆ =
∆ −= Ω
![Page 9: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/9.jpg)
Problema ( , )Dados el grado maximo
1. Construccion de grafos de peque
y el diametro , maximizar e
ño diametro:
l numero de dos. noD
D∆
∆
?
57, 2DMonster
∆ = =1, 1n D∆ = − = 7, 2DHoffman Singleton
∆ = =3, 2DPetersen
∆ = =2∆ =
( 1) 2( , ) , Cota de Moore2(log )
D
n D
D n∆
∆ ∆ − −∆ =
∆ −= Ω
![Page 10: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/10.jpg)
Problema ( , )Dados el grado maximo
1. Construccion de grafos de peque
y el diametro , maximizar e
ño diametro:
l numero de dos. noD
D∆
∆
\ 2 3 4 5 6 7 83 10 /10 20 / 22 38 / 46 70 / 94 132 /190 190 / 382 570 /15344 15 /17 41/ 53 96 /161 364 / 485 740 /1457 1200 / 4373 3080 /131215 24 / 26 72 /106 210 / 426620 /1706 2766 / 6826 5500 / 27306 16956 /109226
D∆
Construcciones asintoticas ( ( , ))?Cotas justas para ( , )? Construcciones con (log )?
O n Dn DD O n∆
∆∆
=
![Page 11: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/11.jpg)
Problema ( , )Dados el grado maximo
1. Construccion de grafos de peque
y el diametro , maximizar e
ño diametro:
l numero de dos. noD
D∆
∆
Grafos de incidencia de planos proyectivos finitos1, 3kp D∆ = + =
( 1) 1( , ) 2 , Cota de Moore bipartitos2
(log )
D
n D
D n
∆ − −∆ =
∆ −= Ω
![Page 12: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/12.jpg)
Problema ( , )Dados el grado maximo
1. Construccion de grafos de peque
y el diametro , maximizar e
ño diametro:
l numero de dos. noD
D∆
∆
Grafos de incidencia de planos afines finitossin una clase de paralelismo
![Page 13: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/13.jpg)
Problema ( , )Dados el grado maximo
1. Construccion de grafos de peque
y el diametro , maximizar e
ño diametro:
l numero de dos. noD
D∆
∆
Grafos de incidencia de planos afines finitossin una clase de paralelismo
2 2
(3 1) / 2, 1 mod 4, 28 / 9( 1/ 2) (Cota de Moore: 1
5 Hoffman-Sing
)
letonq
q q Dn∆ = − ≡ =
= ∆ + ∆
→
+
=
![Page 14: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/14.jpg)
Problema ( , )Dados el grado maximo
1. Construccion de grafos de peque
y el diametro , maximizar e
ño diametro:
l numero de dos. noD
D∆
∆
Construcciones asintoticas ( ( , ))? Cotas justas para ( , )?
Para 2, 4, 6 (geometrias finitas)Para ( , ) - en algunos casosEscas
Construcciones con as const(log )?
Dn
O n Dn DD O n
D c
∆
∆∆
∆=
=
rucciones (pero un grafo aleatorio tiene casi seguramente diametro logaritmico!)
![Page 15: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/15.jpg)
( , )-concentradores: Dados nodos de salida y nodos de llegada, deter
2.Encaminam
minar caminos independientes que los unen
ientos en redes sin confli tos
.
cn l k k
k
Digrafo aciclico con entradas salidas y aristasn n l n⋅
![Page 16: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/16.jpg)
( , )-concentradores: Dados nodos de salida y nodos de llegada, deter
2.Encaminam
minar caminos independientes que los unen
ientos en redes sin confli tos
.
cn l k k
k
R edes de telefoniaRedes de fibra opticaRedes de permutaciones
![Page 17: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/17.jpg)
( , )-concentradores: Dados nodos de salida y nodos de llegada, deter
2.Encaminam
minar caminos independientes que los unen
ientos en redes sin confli tos
.
cn l k k
k
![Page 18: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/18.jpg)
( , )-concentradores: Dados nodos de salida y nodos de llegada, deter
2.Encaminam
minar caminos independientes que los unen
ientos en redes sin confli tos
.
cn l k k
k
01 0110011
00 11 000 111
100
010 101
010 110
2K+
2( )L K + 22( )L K +
Digrafos de de Bruijn ( , ): DB d D n d=
![Page 19: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/19.jpg)
( , )-concentradores: Dados nodos de salida y nodos de llegada, deter
2.Encaminam
minar caminos independientes que los unen
ientos en redes sin confli tos
.
cn l k k
k
01 0110011
00 11 000 111
100
010 101
010 110
2K+
2( )L K + 22( )L K +
Algoritmo local de encaminamiento: 000 001 011 110
Digrafos de de Bruijn ( , ): DB d D n d=
![Page 20: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/20.jpg)
( , )-concentradores: Dados nodos de salida y nodos de llegada, deter
2.Encaminam
minar caminos independientes que los unen
ientos en redes sin confli tos
.
cn l k k
k
01 0110011
00 11 000 111
100
010 101
010 110
2K+
2( )L K + 22( )L K +
Digrafos de de Bruijn ( , ): DB d D n d=
Algoritmo local de encaminamiento: 000 001 011 110Sequencia binaria completa de longitud minima 0 0 0 1 1 1 0 1 0 0
![Page 21: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/21.jpg)
( , )-concentradores: Dados nodos de salida y nodos de llegada, deter
2.Encaminam
minar caminos independientes que los unen
ientos en redes sin confli tos
.
cn l k k
k
01 0110011
00 11 000 111
100
010 101
010 110
2K+
2( )L K + 22( )L K +
Algoritmo local de encaminamiento: 000 001 011 110Sequencia binaria completa de longitud minima 0 0 0 1 1 1 0 1 0 0Panciclicidad, diámetro óptimo,…
Digrafos de de Bruijn ( , ): DB d D n d=
![Page 22: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/22.jpg)
( , )-concentradores: Dados nodos de salida y nodos de llegada, deter
2.Encaminam
minar caminos independientes que los unen
ientos en redes sin confli tos
.
cn l k k
k
011001
000 111
100
010 101
110
![Page 23: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/23.jpg)
( , )-concentradores: Dados nodos de salida y nodos de llegada, deter
2.Encaminam
minar caminos independientes que los unen
ientos en redes sin confli tos
.
cn l k k
k
X
X
X
X
011001
000 111
100
010 101
110
![Page 24: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/24.jpg)
( , )-concentradores: Dados nodos de salida y nodos de llegada, deter
2.Encaminam
minar caminos independientes que los unen
ientos en redes sin confli tos
.
cn l k k
k
=
=
=
=
011001
000 111
100
010 1011 factorizacion−
110
![Page 25: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/25.jpg)
( , )-concentradores: Dados nodos de salida y nodos de llegada, deter
2.Encaminam
minar caminos independientes que los unen
ientos en redes sin confli tos
.
cn l k k
k
Grupo de permutaciones de Σ
011001
000 111
100
010 1011 factorizacion − Σ
110
![Page 26: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/26.jpg)
( , )-concentradores: Dados nodos de salida y nodos de llegada, deter
2.Encaminam
minar caminos independientes que los unen
ientos en redes sin confli tos
.
cn l k k
k
Grafo de Cayley ( ( ), )Cay G ∑ ∑ Grupo de permutaciones de Σ
R ecubrimiento regular(homomorfismo localmente biyectivo)
011001
000 111
100
010 1011 factorizacion − Σ
110
![Page 27: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/27.jpg)
( , )-concentradores: Dados nodos de salida y nodos de llegada, deter
2.Encaminam
minar caminos independientes que los unen
ientos en redes sin confli tos
.
cn l k k
k
2LButterfly
Grupo de permutaciones de Σ
R ecubrimiento regular(homomorfismo localmente biyectivo)
011001
000 111
100
010 101 1 factorizacion regular
− Σ
110
![Page 28: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/28.jpg)
( , )-concentradores: Dados nodos de salida y nodos de llegada, deter
2.Encaminam
minar caminos independientes que los unen
ientos en redes sin confli tos
.
cn l k k
k
2LButterfly
Grupo de permutaciones de Σ
000 111
100
010 101 1 factorizacion regular
− Σ
R ecubrimiento regular(homomorfismo localmente biyectivo)
Generacion eficiente de permutacionesEmulacion por redes simetricas
011001
110
![Page 29: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/29.jpg)
( , )-concentradores: Dados nodos de salida y nodos de llegada, deter
2.Encaminam
minar caminos independientes que los unen
ientos en redes sin confli tos
.
cn l k k
k
1-factorizaciones y recubrimientos regulares ( , , )-expansores: graf
Construcci
os -regu
on de ( , )-concentra
lares de orden t
dor
.q.
:
)
s
(1
en
n k c k nA
A c An
l••
∂ ≥ −
AA∂
![Page 30: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/30.jpg)
( , )-concentradores: Dados nodos de salida y nodos de llegada, deter
2.Encaminam
minar caminos independientes que los unen
ientos en redes sin confli tos
.
cn l k k
k
1-factorizaciones y recubrimientos regulares ( , , )-expansores: graf
Construcci
os -regu
on de ( , )-concentra
lares de orden t
dor
.q.
:
)
s
(1
en
n k c k nA
A c An
l••
∂ ≥ −
A
,2
2 2 2 20 1 2 3
Grafos de Ramanujan:, 1mod 4
( ( ), )p qq
p qX Cay PGL S
S p a a a a
≡
=
← = + + +
A∂
![Page 31: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/31.jpg)
Asignacion de frecuencias en una red de comunicaciones movi3.Pr oblema d
lescon restr
e asignacion de frecu
icciones por interfer
e
e
ncias:
ncias
![Page 32: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/32.jpg)
Asignacion de frecuencias en una red de comunicaciones movi3.Pr oblema d
lescon restr
e asignacion de frecu
icciones por interfer
e
e
ncias:
ncias
Dos estaciones adyacentes deben asignar frecuencias distintas (sujetasa restricciones)
![Page 33: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/33.jpg)
Asignacion de frecuencias en una red de comunicaciones movi3.Pr oblema d
lescon restr
e asignacion de frecu
icciones por interfer
e
e
ncias:
ncias
G
Problemas de coloraciónde grafos
Dos estaciones adyacentes deben asignar frecuencias distintas
![Page 34: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/34.jpg)
Asignacion de frecuencias en una red de comunicaciones movi3.Pr oblema d
lescon restr
e asignacion de frecu
icciones por interfer
e
e
ncias:
ncias
10,1, , ,0 ( )C N c V−= ∈…
c
coloraciones: ( ) - ( )Objetivo: ( ) min ma
0 ( )= (G
x ( )
)x
T
T
T c x c y Ts G c x
T s G χ= →
− ∉=
Problemas de coloraciónde grafos
![Page 35: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/35.jpg)
Asignacion de frecuencias en una red de comunicaciones movi3.Pr oblema d
lescon restr
e asignacion de frecu
icciones por interfer
e
e
ncias:
ncias
10,1, , ,0 ( )C N c V−= ∈…
coloraciones: ( ) - ( )( conjunto de restricciones)
-coloraciones: ( ) ( ) ( )( ( ) distancia minima entre frecuencias)
T c x c y TT
l c x c y l xyl xy
− ∉
− ≥
c
Objetivo: ( ) min m
0 ( )= (G)1 ( )= (G)
ax ( )
T
l
l x
T
s G
s Gl s
c x
Gχχ
= →
=
≡ →Problemas de coloraciónde grafos
![Page 36: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/36.jpg)
Asignacion de frecuencias en una red de comunicaciones movi3.Pr oblema d
lescon restr
e asignacion de frecu
icciones por interfer
e
e
ncias:
ncias
NP-completo (incluso para 3-colorabilidadde grafos planos de grado máximo 4)i
Problemas de coloraciónde grafos
![Page 37: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/37.jpg)
Asignacion de frecuencias en una red de comunicaciones movi3.Pr oblema d
lescon restr
e asignacion de frecu
icciones por interfer
e
e
ncias:
ncias
NP-completo (incluso para 3-colorabilidadde grafos plan No aproxima
os de gradoble (a meno
ms
áximo que P P)
4)=N
i
i
Algoritmos de aproximacion:Entrada: Salida: coloracion de con ( ) | ( ) |
Gk Gk G V G εχ
−
≤
![Page 38: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/38.jpg)
Asignacion de frecuencias en una red de comunicaciones movi3.Pr oblema d
lescon restr
e asignacion de frecu
icciones por interfer
e
e
ncias:
ncias
Inicializar con una coloracion aleatoriaEvaluar una funcion de coste (numero de violaciones)Modificar localmente con arreglo a reglas probabilisticas
NP-completo (incluso para 3-colorabilidadde grafos planos de grado máximo 4) No aproximable (a men Algoritmos heurísticos de optimización
combinatoria (simulated annealin
os qu
g, ge
e P=
néti
NP)
cos,h
i
ii
ormigas,...)
![Page 39: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/39.jpg)
Asignacion de frecuencias en una red de comunicaciones movi3.Pr oblema d
lescon restr
e asignacion de frecu
icciones por interfer
e
e
ncias:
ncias
Clases de grafos con solucion polinomialo aproximable (clases cerradas por menores,por homomrfismos,...)
NP-completo (incluso para 3-colorabilidadde grafos planos de grado máximo 4) No aproximable (a menos que P=NP) Algoritmos heurísticos de optimización
combinatoria (simulated annealing, genéticos,h
i
ii
NP-completo para grafos de a lo sumo 3,pero aproximable
ormigas,...)
en esta clase.twi
![Page 40: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/40.jpg)
Asignacion de frecuencias en una red de comunicaciones movi3.Pr oblema d
lescon restr
e asignacion de frecu
icciones por interfer
e
e
ncias:
ncias
NP-completo (incluso para 3-colorabilidadde grafos planos de grado máximo 4) No aproximable (a menos que P=NP) Algoritmos heurísticos de optimización
combinatoria (simulated annealing, genéticos,h
i
ii
ormigas,...) NP-completo para grafos de a lo sumo 3,
pero aproximable e El número cromático de un grafo aleatorio
n esta es
c.s.
clase
2 log .
.
/n
tw
n
i
i,Modelos aleatorios: n pG
![Page 41: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/41.jpg)
Asignacion de frecuencias en una red de comunicaciones movi3.Pr oblema d
lescon restr
e asignacion de frecu
icciones por interfer
e
e
ncias:
ncias
Algoritmos exactos
NP-completo (incluso para 3-colorabilidadde grafos planos de grado máximo 4) No aproximable (a menos que P=NP) Algoritmos heurísticos de optimización
combinatoria (simulated annealing, genéticos,h
i
ii
ormigas,...) NP-completo para grafos de a lo sumo 3,
pero aproximable en esta clase. El número cr
El
omático de un grafo aleatorio esc.s. / 2 log
problema ( ) se puede resolver en tiempo( (
.
tw
spl
nG
O
n
n +
i
i
i2) ), max ( ).n l l xy=
![Page 42: Aspectos combinatorios en problemas de comunicaciones · combinatoria (simulated annealin os qu g, ge e P= néti NP) cos, h i i i ormigas,...) Asignacion de frecuencias en una red](https://reader031.fdocumento.com/reader031/viewer/2022022014/5b3b34407f8b9a4b0a8eb35e/html5/thumbnails/42.jpg)
Telecomunicaciones e Informática
Problemas combinatorios
Métodos algorítmicos, algebraicos, geométricos, probabilísticos,...
Paul Erdös (1913-1996)