Journees Graphes et Algorithmes

De
Publié par

Journees Graphes et Algorithmes 2009 Deux variantes autour des codes identifiants Olivier Delmas, Sylvain Gravier, Mickael Montassier, Aline Parreau 5 novembre 2009 ANR IDEA Aline Parreau Variantes autour des codes identifiants 5 novembre 2009 1 / 13

  • codes identifiants

  • presentation des variantes codes

  • autour des codes identifiants

  • journees graphes


Publié le : mardi 19 juin 2012
Lecture(s) : 13
Tags :
Source : lirmm.fr
Nombre de pages : 40
Voir plus Voir moins
AlineParetnatuasuaeriraVsidentderdoucoesrb2evomestn5ina
ANR IDEA
OlivierDelmas,SylvainGravier,Micka¨elMontassier,AlineParreau
5 novembre 2009
Deux variantes autour des codes identiants
Journ´eesGraphesetAlgorithmes2009
/130091
xV,yV,Br(x)C6=Br(y)C
G= (V,E) un graphe,rN.
atntse´ePrsedodi-ritnetnandiovaesanrisCtesAlineidesodscdeurtoausetnairaVuaerraP
CVest uncoder-identifiantsi :
Cest un ensemble dominant :
xV,Br(x)C6=
C romsstsmetoreleuss-ape´:
13
Codesrtns-identia
092/re20evbm5sonatnneit
doCs-rseiravetnasntenidatiationdesPr´esent,3,4,1,22,3,}51{154{32Vuraaitnseuaotru,4,5}AlineParrea5,4{,3{}}5,43,2{}{,42,1,{13}5}}{
8
7
1
9
2
4
6
5
Codesrtienid-snta
3
Exemple avecr= 2 surC8:
/3310920rembvenos5ntaitnedisedocsed
1{2,,4}5,2,3{,1}{{13}2,1,}{,4,32{}5,4,3{}5,4{}5tesCodesesvarianatns-rdineit31
Codesratisnt-enid
90/3
6
5
8
7
3
Exemple avecr= 2 surC8:
2
4
9
1
3,4,5,A}ilenaPrreauVariantesautoedrudocsdiseitnentanos5mbve20rentationdPr´ese
3,4,1{2,tnesoitae´rPitatnsse-rdineantesCodndesvariintdesiov5ntsanuotuasetedocsedr
7
8
B2(9) 9
Exemple avecr= 2 surC8:
2
4
5
6
1
2e00merb3
3
Codesrntatienid-s
391/}{,3{51}4,}{{35}{}5,,2,1}4,32,1{ineParreauVarian4,5,{},2,3,4}5lA
inttsansrdede-iesentatiPr´aitnseoCnoedvsraenilrraPVuaeairaesnttoaudeurodsc,2}31{{}}54{5,{}3,4,5}{2,3,4,5}A,3,2,1{,2{15}4,1,}{,4,3
{1,2} 9
1
5
6
7
8
Exemple avecr= 2 surC8:
3
4
2
Codesrtnedsntaii-
31/39002erbmevnos5ntatienides
lAniPeraersedredocedisitnVaauanrisateouut3
Exemple avecr= 2 surC8:
Codesrantenti-dis
391/
4{2,3,4,5}
5 {3,4,5}
3{1,2,3,4,5}
{1}8
{1,29{}1,12,3}
{5}7 {4,5}6
2{1,2,3,4}
5novantse200embrrPe´tnsitaodsCteanenidr-esoitatnesiravsedn
4{2,3,5}
3{1,2,3,5}
{5}7 {5}6
5 {3,5}
90/3er02
{1,29}{1,12,3}
Exemple avecr= 2 surC8:
2{1,2,3}
{1}8
31
Codesrsi-tndeitna
antentivembs5noneliAtnseraaiaeVuaPrresidscodurdeauto´eProitatnesiravsednsCodanteidenesr-tnsita
se´eatntPr
C r:smmteseosslouetareps´-
xV,yV,Br(x)C6=Br(y)C
G= (V,E) un graphe,rN.
/13
Unepremie`revariante
CVest uncoder-identifiantsi :
Cest un ensemble dominant :
xV,Br(x)C6=
edtninaseocedisbre20094ts5novemraPeuaernilAutsardouriVateanblessfaivaesndiosCteanridi-rsedotnaitne
Pr´eatiosentenidr-essfntatiiravsedndoCsetna
G= (V,E) un graphe,rN.
C rrae´spe-faiblementtous les sommets :
Cest un ensemble dominant :
CVest uncoder-identifiantfaiblesi :
xV,rx[0,r],yV,Brx(x)C6=Brx(y)C
erraPeninairaVuaouutsatedecoesrdtniisedn5vonaste200embr3
Une premiere variante `
xV,Br(x)C6=
94/1Alblaies
Pesr´n5vomerb2e00591/3
Codesr-identifiants faibles
1
2
3
4
5
9
6
7
8
nairasetuotusedrdecodesiinttsan,1r2166,01100x10ineP21AlauVaarreC)x(2B1,12,12,1,6,5522,5,,6655,B1(x)C1256,5566,6,1122,52x(0B9C)x43218765sibletsfaianiaarsvdeontitaentnedi-rsedoCsetn
Soyez le premier à déposer un commentaire !

17/1000 caractères maximum.