Introduction auxmath´ematiques discr`etesMichel Rigohttp://www.discmath.ulg.ac.be/Ann´ee 2018-2019Organisation du cours?Cours th´eorique : 8×1h45 = 14h?S´eances d"exercices : 7 ou 8×1h30Notes de cours, listes d"exercices, journal de bord, ?http://www.discmath.ulg.ac.be/notesMDinge.htmlPodcasts viaMyULi`egeQu"est-ce que lesmath´ematiques discr`etes?Some topics Counting MethodsSequencesNumber TheoryAlgebraic StructuresDiscrete ProbabilityGraph TheoryPartially Ordered SetsCombinatorial DesignsDiscrete GeometryCoding TheoryCryptologyDiscrete OptimizationTheoretical Computer ScienceInformation StructuresData MiningContinu vs. discretPixelated Image Abstraction, T.
Gerstner, D.DeCarlo, et al.Quelques rep`eres?sept ponts de K onigsberg ´etudi´e (Euler, 1736)?"Theorie der endlichen und unendlichen Graphen"(K onig, 1936)?milieu du vingti`eme si`ecleN. Biggs, C. Berge, P. Erdos, W.T. Tutte, ?2010 Math.
Subject Classification05CGraph theory?En 2016, 3812 articles de recherche "05C"?En 2017, 4032 articles de recherche "05C"Is Graph Theory Key to Understanding Big Data?WIRED Mars 2014iStock.com/AF-studioGraph Theory : Key to Understanding Big DataWIRED Mai 2014Facebook CEO Mark Zuckerberg shows off Graph Search.Photo : Ariel Zambelich/Wiredhttp ://innovationinsights.wired.com/insights/2014/05/graph-theory-key-understanding-big-data-2/grapheorient´eD´efinition?Vun ensemble (fini ou infini)?Eune partie deV×V(i.e., unerelationsurV).LegrapheG= (V,E)est la donn´ee du couple(V,E).Les ´el´ements deVsont lessommetsdeG(vertex/vertices).Les ´el´ements deEsont lesarcsdeG(edges).SiVest fini, on parlera degraphe finiet#E≤(#V)2.!ordreau sein des couples appartenant `aEcouple(x,y)?=paire{x,y}Produit cart´esienA×B={(a,b)|a?A,b?B}graphe orient´e - vocabulaireSoientV={vi|i?I}eta= (vi,vj),i,j?Il"origineviet ladestinationvjde l"arca.vietvjsont lesextr´emit´esde l"arcaarelievi`avj.Sib= (vi,vi):best uneboucle.Deux arcsadjacentsont au moins une extr´emit´e en commun.vivjvivj=Un graphe orient´eSoit le grapheG= (V,E)o`uV={a,b,c,d,e}etE={(a,b),(a,e),(b,b),(b,c),(c,c),(c,d),(c,e),(d,a),(e,a),(e,d)}.a bdecIl s"agit d"UNErepr´esentationdu graphe (parmi d"autres)Le mˆeme grapheoudes graphes isomorphesLes graphes"r´eels»sont"grands»R´eseau Mobistar±2.106abonn´es -arXiv0803.0476, V.
Blondel et al.Graphe orient´e - vocabulaireSoita= (vi,vj)?E.vivjvivj=aest unarc sortantdeviouarc incident`avivers l"ext´erieuraest un arcentrantdansvjouarc incident`avjvers l"int´erieurensemble des arcs sortant devi=ω+(vi)ensemble des arcs entrant dansvj=ω-(vj)ensemble des arcs incidents =ω(v) :=ω+(v)?ω-(v)demi-degr´e sortant(resp.demi-degr´e entrant) d"un sommetvd+(v)= #(ω+(v))d-(v)= #(ω-(v)).Handshaking formula?v?Vd+(v) =?v?Vd-(v).D´efinition (suite )degr´edev:deg(v)=d+(v) +d-(v)ensemble dessuccesseursdev:succ(v)={s1, ,sk}sommetssitels que(v,si)?ω+(v), i.e.,(v,si)?E.ensemble despr´ed´ecesseursdev:pred(v)={s1, ,sk}sommetssitels que(si,v)?ω-(v), i.e.,(si,v)?E.ensemble des voisins dev:ν(v)= pred(v)?succ(v)Siuappartient `aν(v),uetvsont des sommetsvoisinsExemple (suite )a bdecω+(a) ={(a,b),(a,e)},ω-(d) ={(c,d),(e,d)},succ(a) ={b,e},succ(b) ={b,c},pred(d) ={c,e},ν(a) ={b,d,e},les arcs(e,a)et(d,a)sont adjacents,d+(c) = 3D´efinition na
ıveUn multi-ensemble :{1,1,2,3},{1,2,3}et{1,2,2,3}{11,12,13,21,22,3}D´efinitionUnmulti-grapheG= (V,E)est un graphe pour lequel l"ensembleEdes arcs est un multi-ensemble.aecbdUn multi-grapheG= (V,E)estfinisiVetEsont finis!Vfini n"implique pasEfini.Pour les multi-graphes?"handshaking formula»OKon adapte?ω+(v),d+(v),succ(v)?ω-(v),d-(v),pred(v)ω+(v)etω-(v)sont en g´en´eral des multi-ensembles.D´efinitionUn grapheG= (V,E)estsimple?il ne s"agit pas d"un multi-graphe,pas d"arˆete multiple,?Eest irr´eflexif :?v?V,(v,v)??E,pas de bouclea bdecEn r´esum´eUn graphe (orient´e) simple, un graphe et un multi-grapheQuelques exemples de graphes orient´es?le graphe de Twitter?le graphe des pages web?les flux de migration entre pays du globe?un r´eseau routier avec des sens uniques?relation d"ordreVisualizing my Twitter Network by number of followers.Michael Atkisson http ://woknowing.wordpress.com/Les pages et les liens entre les pagesp.4p.2p.1p.5p.3http://download.gsb.bund.de/BIB/global_flow/Quantifying Global International Migration Flows, G.
J. Abel, N.
Sande, Science 2014blogs politiques avant l"´election pr´esidentielle aux USA de 2004.http ://www-personal.umich.edu/˜ladamic/img/politicalblogs.jpghttp ://eigenfactor.orgLe cas non orient´eD´efinitionSoitG= (V,E)un graphe (resp. un multi-graphe).SiEest une relation sym´etrique surV,alorsGest un graphe (resp. un multi-graphe)non orient´e, i.e.,?v1,v2?V: (v1,v2)?E?(v2,v1)?E.On identifie les arcs(vi,vj)et(vi,vj)avec une uniquearˆete(non orient´ee) : la paire{vi,vj}.En r´esum´eUn graphe (non orient´e) simple, un graphe et un multi-grapheDes co-auteurs scientifiques et le nombre d"ErdosPaul Erdos (1913-1996), math´ematicien hongroisTotal Publications : 1425, Total Citations : 12847co-authorship network of 8,500 doctors and scientists publishing on hepatitis C virus between 2008 and 2012M.
Newman, the structure of scientific collaboration networks (2001).Small-world phenomenom"I read somewhere that everybody on this planet is separated onlyby six other people.Six degrees of separation.
Between us andeveryone else on this planet."John GuareUn peu de vocabulaireSoientG= (V,E)multi-graphenon orient´e,a={vi,vj} ?E.aestincident`avietvj.degr´edevi,deg(vi)=#arˆetes incidentes `avi.!lesbouclesapportent unedoublecontribution au degr´e.ensemble des arˆetes incidentes `avi:ω(vi).SiGest simple,deg(vi) = #(ω(vi)).?Notations compatibles avec le cas orient´e.Deux arˆetes sontadjacentessi au moins une extr´emit´e en commun.Deux sommetsvi,vj?Vsontadjacents/voisins, si{vi,vj} ?E.ensemble des voisins dev:ν(v)Handshaking formula (bis)SiG= (V,E)est un multi-graphe non orient´e, alors?v?Vdeg(v) = 2#E.On comprend mieux la double contribution des boucles pour ledegr´e d"un sommet D´efinitionSoitk≥1.
Un multi-graphe orient´e (resp. non orient´e)G= (V,E)estk-r´eguliersi?v?V,d+(v) =k(resp.deg(v) =k).D´efinition (suite )Un grapheG= (V,E)estcompletsiE=V×Vet il estsous-entendu que ce graphe estsimpleetnon orient´e, i.e.,E=V×V\ {(v,v)|v?V}notationKnD´efinitionUn grapheG= (V,E)estbipartisiVpartitionn´e enV1etV2t.q.E?V1×V2.VV21Graphebiparti completKm,n:#V1=m,#V2=n,E=V1×V2.graphesn-partis,n≥2,Vpartitionn´e ennsous-ensemblesV1, ,Vnt.q.E??i?=jVi×Vj.K2,3Leprobl`emes des 3 villas, eau, gaz, ´electricit´e, K3,3D´emonstration? nous verrons queK3,3n"est pas planaire Sur un tore (surface de genre1)Probl`emes d"affectationouvriers:O1, ,Okpostes de travail:T1, ,TtChaque ouvrierOiposs`ede certaines qualifications lui permettantde travailler sur certains postesTi,1, ,Ti,di.Comment r´epartir les ouvriers pour que chaque poste de travailsoit occup´e par au moins un ouvrier?O O O OT T T T1 2 3 41 2 3 4CheminsD´efinitionSoitG= (V,E)un multi-graphe non orient´e.Uncheminde longueurk≥1est une suite ordonn´ee(e1, ,ek)dekarˆetes adjacentesei={ei,1,ei,2},?i? {1, ,k-1},ei,2=ei+1,1.Ce cheminjointles sommetse1,1etek,2,passepar les arˆetese1, ,ek, les sommetse1,1,e1,2, ,ek,1,ek,2.Un chemin de longueur0joint toujours un sommet `a lui-mˆeme.Sie1,1=ek,2:cycle,circuit,chemin ferm´e!Terminologie variable suivant les auteurs et la langue CheminsD´efinitions (suite)chemin dont les arˆetes sont toutes distinctes :pisteouchemin ´el´ementairecircuit dont les arˆetes sont toutes distinctes :piste ferm´eeoucircuit ´el´ementairechemin ne passant pas deux fois par un mˆeme sommet(en particulier, toutes ses arˆetes sont distinctes) :chemin simplecircuit ne passant pas deux fois par un mˆeme sommet - `al"exception du "point de d´epart" :circuit simplePiste (ou chemin´el´ementaire) - chemin simple1e2e3e2e3e1e5467eeee(e1,e2,e3,e4,e5,e6,e7) (e1,e2,e3)Piste (ou chemin´el´ementaire) - chemin simple1e2e3e2e3e1e5467eeee(e1,e2,e3,e4,e5,e6,e7) (e1,e2,e3)Piste (ou chemin´el´ementaire) - chemin simple1e2e3e2e3e1e5467eeee(e1,e2,e3,e4,e5,e6,e7) (e1,e2,e3)Piste (ou chemin´el´ementaire) - chemin simple1e2e3e2e3e1e5467eeee(e1,e2,e3,e4,e5,e6,e7) (e1,e2,e3)Piste (ou chemin´el´ementaire) - chemin simple1e2e3e2e3e1e5467eeee(e1,e2,e3,e4,e5,e6,e7) (e1,e2,e3)Piste (ou chemin´el´ementaire) - chemin simple1e2e3e2e3e1e5467eeee(e1,e2,e3,e4,e5,e6,e7) (e1,e2,e3)Piste (ou chemin´el´ementaire) - chemin simple1e2e3e2e3e1e5467eeee(e1,e2,e3,e4,e5,e6,e7) (e1,e2,e3)Piste (ou chemin´el´ementaire) - chemin simple1e2e3e2e3e1e5467eeee(e1,e2,e3,e4,e5,e6,e7) (e1,e2,e3)circuit, piste ferm´ee et circuit simple1e2e3e4e5e6e1e2e3e4e7e5e6e6e1e2e5e4e3e(e1,e2,e3,e4,e5,e6,e4) (e1,e2,e3,e4,e5,e6)circuit, piste ferm´ee et circuit simple1e2e3e4e5e6e1e2e3e4e7e5e6e6e1e2e5e4e3e(e1,e2,e3,e4,e5,e6,e4) (e1,e2,e3,e4,e5,e6)circuit, piste ferm´ee et circuit simple1e2e3e4e5e6e1e2e3e4e7e5e6e6e1e2e5e4e3e(e1,e2,e3,e4,e5,e6,e4) (e1,e2,e3,e4,e5,e6)circuit, piste ferm´ee et circuit simple1e2e3e4e5e6e1e2e3e4e7e5e6e6e1e2e5e4e3e(e1,e2,e3,e4,e5,e6,e4) (e1,e2,e3,e4,e5,e6)circuit, piste ferm´ee et circuit simple1e2e3e4e5e6e1e2e3e4e7e5e6e6e1e2e5e4e3e(e1,e2,e3,e4,e5,e6,e4) (e1,e2,e3,e4,e5,e6)circuit, piste ferm´ee et circuit simple1e2e3e4e5e6e1e2e3e4e7e5e6e6e1e2e5e4e3e(e1,e2,e3,e4,e5,e6,e4) (e1,e2,e3,e4,e5,e6)circuit, piste ferm´ee et circuit simple1e2e3e4e5e6e1e2e3e4e7e5e6e6e1e2e5e4e3e(e1,e2,e3,e4,e5,e6,e4) (e1,e2,e3,e4,e5,e6)circuit, piste ferm´ee et circuit simple1e2e3e4e5e6e1e2e3e4e7e5e6e6e1e2e5e4e3e(e1,e2,e3,e4,e5,e6,e4) (e1,e2,e3,e4,e5,e6)RemarqueDans le cas d"un graphe (qui n"est pas un multi-graphe),un chemin de longueurkest aussi univoquement d´etermin´e parunesuite de sommets(v0, ,vk)de mani`ere telle que{vi,vi+1}est une arˆete du graphe.Connexit´eD´efinitionDeux sommetsaetbsontconnect´es,s"il existe un chemin les joignant :a≂bRemarque :un sommet est connect´e `a lui-mˆeme(reflexivit´e)composante connexe:?classe d"´equivalence pour≂, ou,?ensemble maximal (pour?) de sommets2`a2connect´es.Un multi-graphe non orient´e estconnexesi?V/≂contient une seule composante connexe, ou,??a,b?V,a≂bRemarque :on supposera queG= ({v},∅)est connexeChemins dans le cas orient´eD´efinition!G= (V,E)multi-graphe orient´e.cheminde longueurk≥1: suite ordonn´ee(e1, ,ek)dekarcsei= (ei,1,ei,2)t.q.?i? {1, ,k-1},ei,2=ei+1,1.Ce cheminjointles sommetse1,1etek,2.S"il existe un chemin joignant deux sommetsaetb:a→b.aetbso
