Algorithmique de Graphes L3

Frédéric Roupin

Description

Niveau: Supérieur, Licence, Bac+3

• cours - matière potentielle : frédéric

Algorithmique de Graphes L3 Frédéric ROUPIN Institut Galilée 2011/2012 Frédéric Roupin L3 Algorithmique de Graphes 2011/2012 1

• l3 algorithmique de graphes


• lipn


• univ-paris13


• notions élémentaires de théorie des graphes

Sujets

• Frédéric
• Grappe
• Institut Galilée
• Soldano

Informations

• Publié par: ondey
• Nombre de lectures: 273
• Langue: Français
• Poids de l'ouvrage: 3 Mo

Extrait

Algorithmiquede.frRoupindeGraphesFL3AlgoF2011/2012r?d?ric2011/2012ROUPINr?d?ricInstitutL3Galil?erithmiquefrederic.roGraphesupin@lipn-univ-paris131PlanducoursFAlgode2011/2012r?d?ricrithmiqueRoupinGraphesL32I
I
organisationducoursmsduction,2011/2012Objectifs(petFDomainesducoursrmatiqueObjectifstrans:rchandises),Notionsgestion?l?mentairesAlgodesth?ocomplexit?.rie:detelecsrgraphesoDonnerrsonnes,les(pporipncipauxRoupinalgoderithmesrobl?meutilis?sr?elsdansImpl?mentation,les..graphesconcern?setinfoleurs,applicationsoMettre/en?seaux,ppratirtsqueecemas?nergiealgororithmestransp:rt),ObjectifsdeExemplesrojets/plannings,...der?d?ricmoL3d?lisationrithmiquedeGraphesp3Objectifsetorganisationderis13.frlipn.univ-paduocourse,OrganisationRoupindudini,coursatCoursRolandFer?d?ricFRoupin,Algoroupin2011/2012atolivier.blipn.univ-padiniris13.frlipn.univ-paTD/TPTD/TPHenryGrappSoldano,Roland.Grappsoldanoatatris13.frlipn.univ-par?d?ricris13.frL3TD/TPrithmiqueOlivierGraphesBo4= ( ; )

=f ; g =f( ; )g =f ; g =f( ; )g
:ensembleni)UD?nitionsD?nitionsU:coursetXXduXXGrapheadreXc?l?mentairesle:(dans2FURoupinGAlgo1de22011/2012r?sentationrient?)repX3sommets4:U1:a4rcs3Graphes(orient?)r?d?ricouL3arithmiquer?tesGraphes(non-o5( ; )2
+2 ( )
2 ( )
+ ( ) = ( )[ ( )
( ) =j ( )j
( ) =j ( )j
+ +( ) =j ( )j
dessuccesseursdexxxySoitdexext?rieurr?sentationD?nitionsXre,:repxxyetleestDenitionl'ensembleXdessommetspDemi-degr?rx?d?cesseursxdelexdOnetnotepr?d?cesseur?l?mentairesxxxD?nitionsSoit:,2011/2012nombxdexvoisins,xUint?rieurl'ensembledFxRoupinSoitAlgodelessuccesseurvoisinsDemi-degr?de:xestDenitionxDegr?,:dedxestyder?d?ricestL3,rithmiquexGraphesGraphes6P
= ( ; ) ( ) = j j2
( ; ) ( ) ( )
= ( ; )
P P
( ) = j j ( )2 2 ; ( )
D?monstration.Chaquear?teestdlaSoitdxxLemmeGyXri?t?sxcontribueXexactementx?toutdeuxdegr?deD?monstration.g2rx?sgraphe,:obtientdonPropdxsommetsr?sentationLemmeetidderepimpairypair.etPuisque.xLemmeXSoitUGun.2impairUGonUquepair.xilXaetnombapair?l?mentairesD?nitionsdXx:estexistDoncauydeuxunderedegr?der?d?ricdansL3somme.rithmiqueDansegraphe2011/2012lUeGraphesmoinsunsommetsgraphe.m?meLeFnombRoupinreAlgodedsommetsGraphesde7= ( ; )
=f ; ; ; g
=f( ; ); ( ; ); ( ; )g
0 ( ; )
0( ; )2 ( ; )2
( ; )
2 ( ; ) ( ; )
rtielspaDenitionSoitpaet4Y3graphes5XDenition.leLexsous-grapheexisteengendr?UpaUrWYWest2le3grapheY6siGaWXAlgoetYYSous-graphesF5yU5Le.pSoitrtielUr?sentation.repgrapheo?aetengendr?xr?l?mentairesestygrapheD?nitionsYdeW2011/2012o?2:sisietseulementseulementilsiunxrcetxyysontoudansyYxetdansW.Roupinr?d?ricxL33rithmiqueGraphesGraphesU8+( ) ( ) ( )
;
( ; ) ( ; ) ( ; )
de3?3Xles2Demi-degr?deint?rieurrdeU6n?paDemi-degr?3ext?rieurade?2,Degr?,5162011/20126rpasommetsd?ni?4etr?sentation?repGraphe1rtieletpa,les?l?mentairesrcs11D?nitions3,,:4Exemple3FetRoupin3Algo64?Graphesr?d?ric?L35rithmiqueSous-grapheGraphesd?ni9;:::;
+ +
;:::; ;:::;
Uncheminn'appacircuitexistedeectivementlongueurChemins,ruesteuneensemblerithmiqued'uarcspu:1fois.onaleCasco?ncident,DenitioncycleitsRoupincircu2011/2012ureprtelteloquelaquu?l?mentairesjaucunetplusursquejinitialeetcha?ne1cheminsontpaadjacentsrspectivementourFtoutAlgje,cha?nes,etr?sentationl'extretcyclesrrient?.qu'ilruneunrientationDenitionourcha?neelleun1minD?nitions?l?mentaires?mit?iunitialeestdchemin.eUneuoujcheGraphessont1siestsommetl'extr?mit?ra?tterminaled'unedeLoulesjxtr?mit?s.etDenitiond'uneCas(respnond'uno)rient?.onUnerlcha?nealodedelongueur(resprdeest)unr?d?ricensembleL3d'oar?tesduGraphes110