graph.rtf

{\rtf1\ansi\ansicpg1252\uc1 \deff0\deflang1033\deflangfe1036{\fonttbl{\f0\froman\fcharset0\fprq2{\*\panose 02020603050405020304}Times New Roman;}{\f3\froman\fcharset2\fprq2{\*\panose 05050102010706020507}Symbol;}
{\f50\froman\fcharset238\fprq2 Times New Roman CE;}{\f51\froman\fcharset204\fprq2 Times New Roman Cyr;}{\f53\froman\fcharset161\fprq2 Times New Roman Greek;}{\f54\froman\fcharset162\fprq2 Times New Roman Tur;}
{\f55\froman\fcharset186\fprq2 Times New Roman Baltic;}}{\colortbl;\red0\green0\blue0;\red0\green0\blue255;\red0\green255\blue255;\red0\green255\blue0;\red255\green0\blue255;\red255\green0\blue0;\red255\green255\blue0;\red255\green255\blue255;
\red0\green0\blue128;\red0\green128\blue128;\red0\green128\blue0;\red128\green0\blue128;\red128\green0\blue0;\red128\green128\blue0;\red128\green128\blue128;\red192\green192\blue192;}{\stylesheet{\widctlpar\adjustright \fs20\lang1036\cgrid \snext0 
Normal;}{\s1\qj\keepn\widctlpar\tqc\tx1560\tqc\tx2268\tqc\tx2977\tqc\tx3828\tqc\tx4678\tqc\tx5529\tqc\tx7088\adjustright \fs28\lang3084\cgrid \sbasedon0 \snext0 heading 1;}{\s2\keepn\widctlpar\adjustright \fs28\lang3084\cgrid \sbasedon0 \snext0 
heading 2;}{\s3\qj\keepn\widctlpar\adjustright \fs28\lang3084\cgrid \sbasedon0 \snext0 heading 3;}{\s4\qj\keepn\widctlpar\adjustright \i\fs28\lang3084\cgrid \sbasedon0 \snext0 heading 4;}{\s5\qj\keepn\widctlpar\outlinelevel4\adjustright \cbpat8 
\fs32\lang1036\cgrid \sbasedon0 \snext0 heading 5;}{\*\cs10 \additive Default Paragraph Font;}{\s15\qj\widctlpar\adjustright \fs20\lang3084\cgrid \sbasedon0 \snext15 Body Text;}{\s16\widctlpar\tqc\tx4536\tqr\tx9072\adjustright \fs20\lang1036\cgrid 
\sbasedon0 \snext16 header;}{\s17\widctlpar\tqc\tx4536\tqr\tx9072\adjustright \fs20\lang1036\cgrid \sbasedon0 \snext17 footer;}{\*\cs18 \additive \sbasedon10 page number;}{\s19\qc\widctlpar\adjustright \b\fs40\lang1036\cgrid \sbasedon0 \snext19 Title;}}
{\*\listtable{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid91127304}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid101263196}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid112213811}
{\list\listtemplateid149727062\listsimple{\listlevel\levelnfc4\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid256598335}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid276521112}
{\list\listtemplateid-677723658\listsimple{\listlevel\levelnfc4\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid388384051}
{\list\listtemplateid1400022468\listsimple{\listlevel\levelnfc4\leveljc0\levelfollow0\levelstartat3\levelspace0\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\ul\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid446512072}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid455149969}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid492331463}
{\list\listtemplateid202113025\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid523134276}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid636646447}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid676419356}
{\list\listtemplateid202113025\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid678047910}
{\list\listtemplateid202113043\listsimple{\listlevel\levelnfc1\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\fbias0 \fi-720\li720\jclisttab\tx720 }{\listname ;}\listid710303928}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid817189982}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid854921403}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid889995458}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid907425566}
{\list\listtemplateid1922226558\listsimple{\listlevel\levelnfc4\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid930505682}
{\list\listtemplateid202113043\listsimple{\listlevel\levelnfc1\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\fbias0 \fi-720\li720\jclisttab\tx720 }{\listname ;}\listid966470971}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid969869714}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1026254634}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1100566026}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1105491731}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1170019314}
{\list\listtemplateid67895311\listsimple{\listlevel\levelnfc0\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1261992416}
{\list\listtemplateid-71032708\listsimple{\listlevel\levelnfc4\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1268611396}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1315376499}
{\list\listtemplateid202113025\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1343388334}
{\list\listtemplateid2141615388\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat0\levelspace0\levelindent0{\leveltext\'01\u-3880 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1359159486}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1433470354}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1524978330}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1564245719}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1600216071}
{\list\listtemplateid202113025\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1608346556}
{\list\listtemplateid202113025\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1697192023}
{\list\listtemplateid202113025\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1710228177}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1786265726}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1803308890}
{\list\listtemplateid-1143574308\listsimple{\listlevel\levelnfc4\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'02\'00.;}{\levelnumbers\'01;}\ul\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1812213648}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1881086485}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1898399692}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid1922258069}
{\list\listtemplateid67895297\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid2032877011}
{\list\listtemplateid202113025\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid2127960328}
{\list\listtemplateid202113025\listsimple{\listlevel\levelnfc23\leveljc0\levelfollow0\levelstartat1\levelspace0\levelindent0{\leveltext\'01\u-3913 ?;}{\levelnumbers;}\f3\fbias0 \fi-360\li360\jclisttab\tx360 }{\listname ;}\listid2129229158}}
{\*\listoverridetable{\listoverride\listid1812213648\listoverridecount0\ls1}{\listoverride\listid446512072\listoverridecount0\ls2}{\listoverride\listid930505682\listoverridecount0\ls3}{\listoverride\listid636646447\listoverridecount0\ls4}
{\listoverride\listid256598335\listoverridecount0\ls5}{\listoverride\listid492331463\listoverridecount0\ls6}{\listoverride\listid1105491731\listoverridecount0\ls7}{\listoverride\listid1524978330\listoverridecount0\ls8}{\listoverride\listid388384051
\listoverridecount0\ls9}{\listoverride\listid1170019314\listoverridecount0\ls10}{\listoverride\listid1359159486\listoverridecount0\ls11}{\listoverride\listid276521112\listoverridecount0\ls12}{\listoverride\listid1898399692\listoverridecount0\ls13}
{\listoverride\listid676419356\listoverridecount0\ls14}{\listoverride\listid112213811\listoverridecount0\ls15}{\listoverride\listid1433470354\listoverridecount0\ls16}{\listoverride\listid1026254634\listoverridecount0\ls17}{\listoverride\listid1922258069
\listoverridecount0\ls18}{\listoverride\listid455149969\listoverridecount0\ls19}{\listoverride\listid969869714\listoverridecount0\ls20}{\listoverride\listid1261992416\listoverridecount0\ls21}{\listoverride\listid1803308890\listoverridecount0\ls22}
{\listoverride\listid1786265726\listoverridecount0\ls23}{\listoverride\listid2032877011\listoverridecount0\ls24}{\listoverride\listid91127304\listoverridecount0\ls25}{\listoverride\listid1315376499\listoverridecount0\ls26}{\listoverride\listid907425566
\listoverridecount0\ls27}{\listoverride\listid889995458\listoverridecount0\ls28}{\listoverride\listid101263196\listoverridecount0\ls29}{\listoverride\listid817189982\listoverridecount0\ls30}{\listoverride\listid1600216071\listoverridecount0\ls31}
{\listoverride\listid854921403\listoverridecount0\ls32}{\listoverride\listid1881086485\listoverridecount0\ls33}{\listoverride\listid1564245719\listoverridecount0\ls34}{\listoverride\listid1268611396\listoverridecount0\ls35}{\listoverride\listid1100566026
\listoverridecount0\ls36}{\listoverride\listid1697192023\listoverridecount0\ls37}{\listoverride\listid1710228177\listoverridecount0\ls38}{\listoverride\listid678047910\listoverridecount0\ls39}{\listoverride\listid2127960328\listoverridecount0\ls40}
{\listoverride\listid2129229158\listoverridecount0\ls41}{\listoverride\listid523134276\listoverridecount0\ls42}{\listoverride\listid710303928\listoverridecount0\ls43}{\listoverride\listid966470971\listoverridecount0\ls44}{\listoverride\listid1608346556
\listoverridecount0\ls45}{\listoverride\listid1343388334\listoverridecount0\ls46}}{\info{\title La logique propositionnelle}{\author matinft2}{\operator Dept. Math-Info}{\creatim\yr2000\mo2\dy23\hr23\min11}{\revtim\yr2000\mo2\dy23\hr23\min11}
{\printim\yr1999\mo1\dy13\hr20\min57}{\version2}{\edmins0}{\nofpages15}{\nofwords1755}{\nofchars10007}{\*\company UQTR}{\nofcharsws12289}{\vern113}}\paperw15842\paperh12242\margl1418\margr1418\margt1418\margb1418 
\deftab708\widowctrl\ftnbj\aenddoc\hyphhotz425\hyphcaps0\formshade\viewkind1\viewscale100\pgbrdrhead\pgbrdrfoot \fet0\sectd \lndscpsxn\psz1\linex0\headery709\footery709\colsx709\endnhere\pgbrdropt32\sectdefaultcl {\header \pard\plain \s16\widctlpar\brdrb
\brdrs\brdrw10\brsp20 \tqc\tx6237\tqr\tx12758\adjustright \fs20\lang1036\cgrid {\lang3084 MAP-1011   \tab }{\field{\*\fldinst {\cs18  PAGE }}{\fldrslt {\cs18\lang1024 15}}}{\lang3084 \tab Isma\'efl BISKRI
\par }}{\*\pnseclvl1\pnucrm\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl2\pnucltr\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl3\pndec\pnstart1\pnindent720\pnhang{\pntxta .}}{\*\pnseclvl4\pnlcltr\pnstart1\pnindent720\pnhang{\pntxta )}}
{\*\pnseclvl5\pndec\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl6\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl7\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl8
\pnlcltr\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}{\*\pnseclvl9\pnlcrm\pnstart1\pnindent720\pnhang{\pntxtb (}{\pntxta )}}\pard\plain \s19\qc\widctlpar\adjustright \b\fs40\lang1036\cgrid {La th\'e9orie des Graphes
\par }\pard\plain \qc\widctlpar\adjustright \fs20\lang1036\cgrid {\b\fs40 
\par 
\par {\pntext\pard\plain\f3\fs32\lang1036\cgrid \loch\af3\dbch\af0\hich\f3 \'b7\tab}}\pard \qj\fi-360\li360\widctlpar\jclisttab\tx360{\*\pn \pnlvlblt\ilvl0\ls37\pnrnot0\pnf3\pnstart1\pnindent360\pnhang{\pntxtb \'b7}}\ls37\adjustright {\fs32 
Euler se servit de la th\'e9orie des graphes pour r\'e9soudre le probl\'e8me des ponts de K\'f6nigsbourg. 
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par {\pntext\pard\plain\f3\fs32\lang1036\cgrid \loch\af3\dbch\af0\hich\f3 \'b7\tab}}\pard \qj\fi-360\li360\widctlpar\jclisttab\tx360{\*\pn \pnlvlblt\ilvl0\ls38\pnrnot0\pnf3\pnstart1\pnindent360\pnhang{\pntxtb \'b7}}\ls38\adjustright {\fs32 De nos jours la th
\'e9orie des graphes sert \'e0 r\'e9soudre des probl\'e8mes du genre\~:
\par {\pntext\pard\plain\f3\fs32\lang1036\cgrid \loch\af3\dbch\af0\hich\f3 \'b7\tab}}\pard \qj\fi-360\li1068\widctlpar\jclisttab\tx1068{\*\pn \pnlvlblt\ilvl0\ls38\pnrnot0\pnf3\pnstart1\pnindent360\pnhang{\pntxtb \'b7}}\ls38\adjustright {\fs32 D\'e9
terminer si un circuit peut \'eatre \'e9tabli sur une carte planaire,
\par {\pntext\pard\plain\f3\fs32\lang1036\cgrid \loch\af3\dbch\af0\hich\f3 \'b7\tab}}\pard \qj\fi-360\li1068\widctlpar\jclisttab\tx1068{\*\pn \pnlvlblt\ilvl0\ls38\pnrnot0\pnf3\pnstart1\pnindent360\pnhang{\pntxtb \'b7}}\ls38\adjustright {\fs32 D\'e9
terminer les connexions entre deux ordinateurs dans un r\'e9seau informatique,
\par {\pntext\pard\plain\f3\fs32\lang1036\cgrid \loch\af3\dbch\af0\hich\f3 \'b7\tab}}\pard \qj\fi-360\li1068\widctlpar\jclisttab\tx1068{\*\pn \pnlvlblt\ilvl0\ls38\pnrnot0\pnf3\pnstart1\pnindent360\pnhang{\pntxtb \'b7}}\ls38\adjustright {\fs32 Permettre de r
\'e9soudre des probl\'e8mes strat\'e9giques du genre\~: trouver le chemin le plus court entre deux points d\rquote un r\'e9seau routier par exemple,
\par {\pntext\pard\plain\f3\fs32\lang1036\cgrid \loch\af3\dbch\af0\hich\f3 \'b7\tab}}\pard \qj\fi-360\li1068\widctlpar\jclisttab\tx1068{\*\pn \pnlvlblt\ilvl0\ls38\pnrnot0\pnf3\pnstart1\pnindent360\pnhang{\pntxtb \'b7}}\ls38\adjustright {\fs32 Etc.
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 Introduction aux graphes\~(d\'e9finition informelle)\~:
\par }{\fs32 Les graphes sont des structures discr\'e8tes form\'e9es de sommets et d\rquote arcs reliant ces sommets.
\par }\pard \qj\widctlpar\adjustright {\b\fs32 
\par 
\par }{\b\fs32\ul A. Types de graphes\~:
\par }{\fs32 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 1 (un graphe simple) :}{\fs32  
\par Un graphe simple G = (N, A) est constitu\'e9 de N, un ensemble non vide de }{\i\fs32 n\'9cuds}{\fs32 , et A un ensemble d\rquote }{\i\fs32 arcs}{\fs32  reliants les n\'9cuds. Il y a au plus un arc reliant deux n\'9cuds et aucun arc ne relie un n\'9c
ud avec lui m\'eame (pas de boucles).
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 2 (un multigraphe) :
\par }{\fs32 Un multigraphe G = (N, A) est constitu\'e9 de N, un ensemble non vide de }{\i\fs32 n\'9cuds}{\fs32 , et A un ensemble d\rquote }{\i\fs32 arcs}{\fs32  reliants les n\'9cuds. Il peut y avoir plusieurs arcs pour relier deux n\'9c
uds. Aucun arc ne relie un n\'9cud avec lui m\'eame (pas de boucles).
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 3 (un pseudographe)\~:
\par }{\fs32 Un pseudographe G = (N, A) est constitu\'e9 de N, un ensemble non vide de }{\i\fs32 n\'9cuds}{\fs32 , et A un ensemble d\rquote }{\i\fs32 arcs}{\fs32  reliants les n\'9cuds. Il peut y avoir plusieurs arcs pour relier deux n\'9c
uds. Il peut y avoir aussi boucles.
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par }\pard \qj\widctlpar\adjustright \shading2000\cbpat8 {\b\fs32 D\'e9finition 4 (un graphe orient\'e9)\~:
\par }{\fs32 Un graphe orient\'e9 G = (N, A) est constitu\'e9 de N, un ensemble non vide de }{\i\fs32 n\'9cuds}{\fs32 , et A un ensemble d\rquote }{\i\fs32 arcs}{\fs32  reliants les n\'9cuds. Les arcs sont orient\'e9s. Si a et b sont deux n\'9cuds l\rquote 
arc (a,b) est diff\'e9rent de l\rquote arc (b,a).
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 5 (un multigraphe orient\'e9)\~:
\par }{\fs32 Un multigraphe orient\'e9 est un multigraphe dont les arcs sont orient\'e9s.
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par 
\par }{\b\fs32\ul B. Mod\'e8les de graphes\~:
\par }{\fs32 
\par Plusieurs exemples de mod\'e8les de graphes\~: voir Kenneth H. Rosen pages 411, 412, 413.
\par 
\par 
\par 
\par }{\b\fs32\ul C. Terminologie des graphes\~:
\par }{\fs32 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 6\~:
\par }{\fs32 Deux n\'9cuds a et b dans un graphe non-orient\'e9 G sont dits adjacents si (a,b) est un arc de G reliant a et b. 
\par On dit que l\rquote arc (a,b) est incident aux n\'9cuds a et b.
\par On dit que a et b sont les n\'9cuds terminaux de (a,b).
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 7\~:
\par }{\fs32 Le degr\'e9 d\rquote un n\'9cud dans un graphe non orient\'e9 est le nombre d\rquote arcs incidents \'e0 ce n\'9cud. Une boucle sur un n\'9cud contribue deux fois au degr\'e9 de ce n\'9cud.
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 Remarque\~:
\par }{\fs32 Un n\'9cud dont le degr\'e9 est \'e9gal \'e0 0 est un n\'9cud isol\'e9.
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 Th\'e9or\'e8me 1 (lemme des poign\'e9es de mains) :
\par }{\fs32 Soit G = (N, A) un graphe non orient\'e9 avec x arcs, alors Somme(degr\'e9s(N)) = 2 x.
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 Th\'e9or\'e8me 2\~:
\par }{\fs32 Un graphe non orient\'e9 a un nombre pair de sommets de degr\'e9s impairs.
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 8\~: 
\par }{\fs32 Soit G un graphe orient\'e9. Soit l\rquote arc (a,b) orient\'e9 qui relie les n\'9cuds a et b. on dit\~:
\par {\pntext\pard\plain\f3\fs32\lang1036\cgrid \loch\af3\dbch\af0\hich\f3 \'b7\tab}}\pard \qj\fi-360\li360\widctlpar\jclisttab\tx360{\*\pn \pnlvlblt\ilvl0\ls39\pnrnot0\pnf3\pnstart1\pnindent360\pnhang{\pntxtb \'b7}}\ls39\adjustright \shading1500\cbpat8 {
\fs32 a est adjacent \'e0 b, b est adjacent \'e0 a.
\par {\pntext\pard\plain\f3\fs32\lang1036\cgrid \loch\af3\dbch\af0\hich\f3 \'b7\tab}}\pard \qj\fi-360\li360\widctlpar\jclisttab\tx360{\*\pn \pnlvlblt\ilvl0\ls39\pnrnot0\pnf3\pnstart1\pnindent360\pnhang{\pntxtb \'b7}}\ls39\adjustright \shading1500\cbpat8 {
\fs32 a est l\rquote extr\'e9mit\'e9 initiale de (a, b) et b est l\rquote extr\'e9mit\'e9 terminale ou finale de (a, b). Les extr\'e9mit\'e9s initiales et finales d\rquote une boucle sont identiques.
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 9\~:
\par }{\fs32 Soit G un graphe orient\'e9. 
\par {\pntext\pard\plain\f3\fs32\lang1036\cgrid \loch\af3\dbch\af0\hich\f3 \'b7\tab}}\pard \qj\fi-360\li360\widctlpar\jclisttab\tx360{\*\pn \pnlvlblt\ilvl0\ls40\pnrnot0\pnf3\pnstart1\pnindent360\pnhang{\pntxtb \'b7}}\ls40\adjustright \shading1500\cbpat8 {
\fs32 Le degr\'e9 int\'e9rieur d\rquote un n\'9cud a, not\'e9 deg}{\fs32\super -}{\fs32 (a), est le nombre d\rquote arcs qui ont le n\'9cud a comme extr\'e9mit\'e9 finale. 
\par {\pntext\pard\plain\f3\fs32\lang1036\cgrid \loch\af3\dbch\af0\hich\f3 \'b7\tab}}\pard \qj\fi-360\li360\widctlpar\jclisttab\tx360{\*\pn \pnlvlblt\ilvl0\ls40\pnrnot0\pnf3\pnstart1\pnindent360\pnhang{\pntxtb \'b7}}\ls40\adjustright \shading1500\cbpat8 {
\fs32 Le degr\'e9 ext\'e9rieur d\rquote un n\'9cud a, not\'e9 deg}{\fs32\super +}{\fs32 (a), est le nombre d\rquote arcs qui ont le n\'9cud a comme extr\'e9mit\'e9 finale.
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 Th\'e9or\'e8me 3\~:
\par }{\fs32 Soit G = (N, A) un graphe orient\'e9. Alors\~:
\par Somme (deg}{\fs32\super -}{\fs32 (A)) = Somme (deg}{\fs32\super +}{\fs32 (A)) = |A|
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par 
\par }{\b\fs32\ul D. Exemples de quelques graphes simples\~:
\par }{\fs32 
\par }\pard \qj\widctlpar\adjustright \shading2000\cbpat8 {\b\fs32 D\'e9finition 10 (Graphes complets) :
\par }{\fs32 Le graphe complet de n n\'9cuds est le graphe simple qui contient exactement un arc entre chaque paire de n\'9cuds distincts.
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 11 (Cycles) : 
\par }{\fs32 Un cycle C}{\fs32\sub k}{\fs32  (k >= 3), consiste en n n\'9cuds n}{\fs32\sub 1}{\fs32 , n}{\fs32\sub 2}{\fs32 , n}{\fs32\sub 3}{\fs32 , \'85, n}{\fs32\sub k}{\fs32  et les arcs (n}{\fs32\sub 1}{\fs32 , n}{\fs32\sub 2}{\fs32 ), (n}{\fs32\sub 2}{
\fs32 , n}{\fs32\sub 3}{\fs32 ), \'85, (n}{\fs32\sub k}{\fs32 , n}{\fs32\sub 1}{\fs32 ).
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par 
\par voir Kenneth H. Rosen pages 419, 420 pour les notions de roues et de cubes.
\par 
\par 
\par }{\b\fs32\ul E. Graphes bipartis\~:
\par }{\fs32 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 12\~:
\par }{\fs32 Un graphe simple G est dit biparti si l\rquote ensemble N de ses sommets peut \'eatre partitionn\'e9 en deux ensembles non vides et disjoints N1 et N2 de telle sorte que quelque soit l\rquote arc du graphe, celui ci relie un n\'9cud de N1 a un n
\'9cud de N2 (autrement dit aucun arc du graphe ne relie les noeuds de N1 entre eux ou les n\'9cuds de N2 entre eux).
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par Exemple\~:
\par }{\fs16 
\par }{\fs32 C}{\fs32\sub 6}{\fs32  est un graphe biparti.
\par 
\par voir exemple 10 dans Kenneth H. Rosen page 421
\par 
\par 
\par }{\b\fs32\ul F. Applications de graphes particuliers\~:
\par }{\fs32 
\par voir Kenneth H. Rosen pages 422, 423, 424, 425
\par }{\b\fs32\ul G. Nouveaux graphes extraits d\rquote un ancien\~:
\par }{\fs32 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 13\~:
\par }{\fs32 Un sous-graphe SG = (SN, SA) du graphe G = (N, A) est un graphe o\'f9 SN }{\fs32 {\field{\*\fldinst SYMBOL 205 \\f "Symbol" \\s 16}{\fldrslt\f3\fs32}}}{\fs32  N et SA }{\fs32 {\field{\*\fldinst SYMBOL 205 \\f "Symbol" \\s 16}{\fldrslt\f3\fs32}}}{
\fs32  A.
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 14\~:
\par }{\fs32 L\rquote union   de   deux   graphes   simples   G1 = (N1, A1)  et  G2 = (N2, A2)  est  un  graphe  simple  G3 = (N3, A3) o\'f9 N3 = N1 }{\fs32 {\field{\*\fldinst SYMBOL 200 \\f "Symbol" \\s 16}{\fldrslt\f3\fs32}}}{\fs32  N2 et A3 = A1 }{\fs32 
{\field{\*\fldinst SYMBOL 200 \\f "Symbol" \\s 16}{\fldrslt\f3\fs32}}}{\fs32  A2. On notera G3 = G1 }{\fs32 {\field{\*\fldinst SYMBOL 200 \\f "Symbol" \\s 16}{\fldrslt\f3\fs32}}}{\fs32  G2.
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par 
\par 
\par }{\b\fs32\ul H. Repr\'e9sentation des graphes\~:
\par }{\fs32 
\par 
\par Plusieurs fa\'e7ons de repr\'e9senter un graphe\~:
\par }{\fs16 
\par {\pntext\pard\plain\f3\fs32\lang1036\cgrid \loch\af3\dbch\af0\hich\f3 \'b7\tab}}\pard \qj\fi-360\li360\widctlpar\jclisttab\tx360{\*\pn \pnlvlblt\ilvl0\ls41\pnrnot0\pnf3\pnstart1\pnindent360\pnhang{\pntxtb \'b7}}\ls41\adjustright {\fs32 \'c9num\'e9
rer les arcs. (s\rquote il n\rquote y a pas d\rquote arcs multiples)
\par }\pard \qj\widctlpar{\*\pn \pnlvlcont\ilvl0\ls0\pnrnot0\pndec }\adjustright {\fs16 
\par {\pntext\pard\plain\f3\fs32\lang1036\cgrid \loch\af3\dbch\af0\hich\f3 \'b7\tab}}\pard \qj\fi-360\li360\widctlpar\jclisttab\tx360{\*\pn \pnlvlblt\ilvl0\ls41\pnrnot0\pnf3\pnstart1\pnindent360\pnhang{\pntxtb \'b7}}\ls41\adjustright {\fs32 
Utiliser des listes d\rquote adjacence qui sp\'e9cifient les n\'9cuds adjacents \'e0 chaque n\'9cud du graphe.
\par }\pard \qj\fi360\widctlpar\adjustright {\fs32 (Voir exemples dans Kenneth H. Rosen pages 429 et 430)
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par }{\b\fs32\ul 
\par 
\par 
\par 
\par Les Matrices d\rquote adjacence et d\rquote incidence\~:
\par }{\fs32 
\par \'c0 des fins d\rquote \'e9laboration d\rquote algorithmes, les graphes peuvent \'eatre repr\'e9sent\'e9s au moyen de matrices. Deux types de matrices les plus commun\'e9ment utilis\'e9s\~:
\par }{\fs16 
\par {\pntext\pard\plain\f3\fs32\lang1036\cgrid \loch\af3\dbch\af0\hich\f3 \'b7\tab}}\pard \qj\fi-360\li360\widctlpar\jclisttab\tx360{\*\pn \pnlvlblt\ilvl0\ls42\pnrnot0\pnf3\pnstart1\pnindent360\pnhang{\pntxtb \'b7}}\ls42\adjustright {\fs32 Premier type fond
\'e9 sur l\rquote adjacence des n\'9cuds,
\par }\pard \qj\widctlpar{\*\pn \pnlvlcont\ilvl0\ls0\pnrnot0\pndec }\adjustright {\fs16 
\par {\pntext\pard\plain\f3\fs32\lang1036\cgrid \loch\af3\dbch\af0\hich\f3 \'b7\tab}}\pard \qj\fi-360\li360\widctlpar\jclisttab\tx360{\*\pn \pnlvlblt\ilvl0\ls42\pnrnot0\pnf3\pnstart1\pnindent360\pnhang{\pntxtb \'b7}}\ls42\adjustright {\fs32 Deuxi\'e8me 
type fond\'e9 sur l\rquote incidence des n\'9cuds et des arcs.
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par Voir exemples dans Kenneth H. Rosen pages 431, 432, 433.
\par 
\par 
\par }{\b\fs32\ul I.Isomorphisme des Graphes\~: 
\par }{\fs32 
\par {\pntext\pard\plain\f3\fs32\lang1036\cgrid \loch\af3\dbch\af0\hich\f3 \'b7\tab}}\pard \qj\fi-360\li360\widctlpar\jclisttab\tx360{\*\pn \pnlvlblt\ilvl0\ls45\pnrnot0\pnf3\pnstart1\pnindent360\pnhang{\pntxtb \'b7}}\ls45\adjustright {\fs32 
Il est souvent utile de savoir si on peut tracer deux graphes de la m\'eame mani\'e8re.
\par }\pard \qj\widctlpar\adjustright {\fs32 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 15\~:
\par }{\fs32 Les graphes simples G1 = (N1, A1) et G2 = (N2, A2) sont isomorphes s\rquote il existe une fonction bijective f de N1 dans N2 avec la propri\'e9t\'e9
 suivante a et b sont adjacents dans G1 si et seulement si f(a) et f(b) sont adjacents dans G2 pour toutes les valeurs de a et de b dans N1. une telle fonction est un isomorphisme. 
\par \'c9tymologie\~: du grec isos (\'e9gal) et morphe (forme)
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 Remarque\~:
\par {\pntext\pard\plain\f3\fs32\lang1036\cgrid \loch\af3\dbch\af0\hich\f3 \'b7\tab}}\pard \qj\fi-360\li360\widctlpar\jclisttab\tx360{\*\pn \pnlvlblt\ilvl0\ls46\pnrnot0\pnf3\pnstart1\pnindent360\pnhang{\pntxtb \'b7}}\ls46\adjustright \shading1500\cbpat8 {
\fs32 Il est souvent tr\'e8s difficile de prouver que deux graphes sont isomorphes. Il y a en effet pour un graphe de n n\'9cuds n\~! possibilit\'e9s de bijections possibles entre l\rquote ensemble des sommets des deux graphes.
\par {\pntext\pard\plain\f3\fs32\lang1036\cgrid \loch\af3\dbch\af0\hich\f3 \'b7\tab}}\pard \qj\fi-360\li360\widctlpar\jclisttab\tx360{\*\pn \pnlvlblt\ilvl0\ls46\pnrnot0\pnf3\pnstart1\pnindent360\pnhang{\pntxtb \'b7}}\ls46\adjustright \shading1500\cbpat8 {
\fs32 Il est plus facile de prouver que deux graphes ne sont pas isomorphes. 
\par {\pntext\pard\plain\f3\fs32\lang1036\cgrid \loch\af3\dbch\af0\hich\f3 \'b7\tab}}\pard \qj\fi-360\li360\widctlpar\jclisttab\tx360{\*\pn \pnlvlblt\ilvl0\ls46\pnrnot0\pnf3\pnstart1\pnindent360\pnhang{\pntxtb \'b7}}\ls46\adjustright \shading1500\cbpat8 {
\fs32 Deux graphes isomorphes doivent avoir le m\'eame nombre de n\'9cuds, le m\'eame nombre d\rquote arcs. De plus les degr\'e8s des n\'9cuds des graphes isomorphes sont identiques.
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par Voir exemples dans Kenneth H. Rosen pages 434 et 435, 436, 437.
\par 
\par 
\par }{\b\fs32\ul J. Connexit\'e9\~:
\par }{\fs32 
\par Si par exemple nous voulons, pour un r\'e9seau informatique, savoir si un message, envoy\'e9 \'e0 partir d\rquote un ordinateur A, va se rendre \'e0 un ordinateur B, nous devons nous int\'e9resser \'e0 la connexit\'e9 du r\'e9seau.
\par 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 16\~ (la cha\'eene) :
\par }{\fs32 Une cha\'eene de longueur n de x}{\fs32\sub 0}{\fs32  \'e0 x}{\fs32\sub n}{\fs32  (n un entier positif) dans un graphe non orient\'e9, est une s\'e9quence d\rquote arcs a}{\fs32\sub 1}{\fs32 , \'85, a}{\fs32\sub n}{\fs32 
, du graphe, de telle sorte que a}{\fs32\sub 1}{\fs32  = (x}{\fs32\sub 0}{\fs32 , x}{\fs32\sub 1}{\fs32 ), a}{\fs32\sub 2}{\fs32  = (x}{\fs32\sub 1}{\fs32 , x}{\fs32\sub 2}{\fs32 ), \'85, a}{\fs32\sub n}{\fs32  = (x}{\fs32\sub n-1}{\fs32 , x}{\fs32\sub n}
{\fs32 ).
\par Quand le graphe est simple, on repr\'e9sente cette cha\'eene par les n\'9cuds parcourus.
\par Quand une cha\'eene ne passe pas plus d\rquote une fois par le m\'eame arc alors on dit que c\rquote est une cha\'eene simple.
\par Une cha\'eene qui commence et qui se termine au m\'eame n\'9cud est appel\'e9e cycle
\par }{\b\fs32 D\'e9finition 16\~ (le chemin) :
\par }{\fs32 Un chemin de longueur n de x}{\fs32\sub 0}{\fs32  \'e0 x}{\fs32\sub n}{\fs32  (n un entier positif) dans un graphe orient\'e9, est une s\'e9quence d\rquote arcs a}{\fs32\sub 1}{\fs32 , \'85, a}{\fs32\sub n}{\fs32 , du graphe, de telle sorte que a}
{\fs32\sub 1}{\fs32  = (x}{\fs32\sub 0}{\fs32 , x}{\fs32\sub 1}{\fs32 ), a}{\fs32\sub 2}{\fs32  = (x}{\fs32\sub 1}{\fs32 , x}{\fs32\sub 2}{\fs32 ), \'85, a}{\fs32\sub n}{\fs32  = (x}{\fs32\sub n-1}{\fs32 , x}{\fs32\sub n}{\fs32 ).
\par Quand le graphe ne comporte pas d\rquote arcs multiples, on repr\'e9sente ce chemin par les n\'9cuds parcourus.
\par Un chemin est simple s\rquote il ne passe pas deux fois par le m\'eame arc.
\par Un chemin qui commence et qui se termine au m\'eame n\'9cud est appel\'e9 circuit.
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 17\~(la connexit\'e9 dans un graphe non orient\'e9 ) : 
\par }{\fs32 Un graphe non-orient\'e9 est dit connexe s\rquote il y a une cha\'eene entre n\rquote importe quelle paire de n\'9cuds distincts du graphe.
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 Th\'e9or\'e8me 4\~:
\par }{\fs32 Il existe une cha\'eene simple reliant n\rquote importe quelle paire de sommets distincts d\rquote un graphe non orient\'e9 connexe.
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 Remarque\~:
\par }{\fs32 Un graphe non connexe est l\rquote union de deux ou plusieurs sous-graphes connexes. 
\par Les sous-graphes connexes disjoints sont les composantes connexes du graphe.
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par 
\par 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 18 (forte connexit\'e9 dans les graphes orient\'e9s)\~:
\par }{\fs32 Un graphe orient\'e9 est }{\fs32\ul fortement connexe}{\fs32  s\rquote il existe un chemin d\rquote un n\'9cud a au n\'9cud b et un chemin du n\'9cud b au n\'9cud a, quels que soit la paire de n\'9cud a et b du graphe G.
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 19 (faible connexit\'e9 dans les graphes orient\'e9s)\~: 
\par }{\fs32 Un graphe orient\'e9 est faiblement connexe s\rquote il y a une cha\'eene entre n\rquote importe quelle paire de n\'9cuds dans le graphe non-orient\'e9 sous-jacents.
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 Remarque\~:
\par }{\fs32 Il existe diff\'e9rentes mani\'e8res des notions de chemins, de circuits et de cycles si deux graphes ne sont pas isomorphes. (Voir exemple dans Kenneth H. Rosen page 446).
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par 
\par }{\b\fs32\ul K. Cha\'eenes Eul\'e9riennes et Hamiltoniennes\~:
\par }{\fs32 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 20 (cycle eul\'e9rien)\~:
\par }{\fs32 Un cycle eul\'e9rien dans un graphe G est un cycle simple contenant tous les arcs de G (qui ne passe au plus une seule fois par chaque arc de G).
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 21 (cha\'eene eul\'e9rienne)\~:
\par }{\fs32 Une cha\'eene Eul\'e9rienne est une cha\'eene simple qui contient tous les arcs de G.
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par Voir exemple dans Kenneth H. Rosen pages 453, 454.
\par }{\fs32\ul Conditions n\'e9cessaires et suffisantes pour l\rquote existence des cycles et des cha\'eenes Eul\'e9riens\~:
\par }{\fs32 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 Th\'e9or\'e8me 5\~: 
\par }{\fs32 un multigraphe connexe admet un cycle Eul\'e9rien si et seulement si chacun de ses n\'9cuds est de degr\'e9 pair.
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par }\pard\plain \s5\qj\keepn\widctlpar\outlinelevel4\adjustright \cbpat8 \fs32\lang1036\cgrid Voir Algorithme de construction des cycles Eul\'e9riens dans Kenneth H. Rosen pages 456
\par \pard\plain \qj\widctlpar\adjustright \cbpat8 \fs20\lang1036\cgrid {\fs32 
\par Voir Exemple dans Kenneth H. Rosen pages 456
\par 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 Th\'e9or\'e8me 6\~:
\par }{\fs32 Un multigraphe connexe admet une cha\'eene Eul\'e9rienne si et seulement s\rquote il a exactement deux sommets de degr\'e9 impair.
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par Voir Exemple dans Kenneth H. Rosen pages 457
\par 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 22 (cha\'eene hamiltonienne)\~:
\par }{\fs32 Une cha\'eene x}{\fs32\sub 0}{\fs32 , x}{\fs32\sub 1}{\fs32 , \'85, x}{\fs32\sub n}{\fs32  dans un graphe G = (N, A) est dite hamiltonienne si N = \{ x}{\fs32\sub 0}{\fs32 , x}{\fs32\sub 1}{\fs32 , \'85, x}{\fs32\sub n}{\fs32  \} et x}{\fs32\sub i
}{\fs32  }{\fs32 {\field{\*\fldinst SYMBOL 185 \\f "Symbol" \\s 16}{\fldrslt\f3\fs32}}}{\fs32  x}{\fs32\sub j }{\fs32 pour tout 0 <= i < j <= n. Autrement dit une cha\'eene hamiltonienne est une cha\'ee
ne qui passe au plus une seule fois par tous les sommets du graphe.
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 23 (cycle hamiltonien)\~:
\par }{\fs32 Un cycle x}{\fs32\sub 0}{\fs32 , x}{\fs32\sub 1}{\fs32 , \'85, x}{\fs32\sub n}{\fs32 , x}{\fs32\sub 0}{\fs32  dans le graphe G = (N, A) est dit hamiltonien si x}{\fs32\sub 0}{\fs32 , x}{\fs32\sub 1}{\fs32 , \'85, x}{\fs32\sub n}{\fs32  est une cha
\'eene hamiltonienne. Autrement dit un cycle hamiltonien est un cycle qui passe au plus une seule fois par tous les sommets du graphe.
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par Voir Exemple dans Kenneth H. Rosen pages 459
\par 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 Th\'e9or\'e8me 7\~: 
\par }{\fs32 Soit un graphe simple connexe G avec n n\'9cuds (n >= 3), G a un cycle hamiltonien si le degr\'e8 de chaque sommet est au moins \'e9gal \'e0 n/2.
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 Remarque\~: 
\par }{\fs32 Le th\'e9or\'e8me 7 \'e9tablit les conditions suffisantes pour d\'e9terminer l\rquote existence des cycles hamiltoniens mais non n\'e9cessaires.
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par 
\par }{\b\fs32\ul L. Probl\'e8mes du plus court chemin (chemin minimal)\~:
\par }{\fs32 
\par Voir Exemples dans Kenneth H. Rosen pages 468 et 469.
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\fs32 Voir Algorithme de Dijkstra dans Kenneth H. Rosen pages 471, 472.
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par Voir Exemple 2 dans Kenneth H. Rosen page 472
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 Th\'e9or\'e8me 8\~: 
\par }{\fs32 L\rquote algorithme de Dijkstra permet de trouver la longueur du chemin minimal entre deux noeuds dans un graphe valu\'e9 non orient\'e9, simple et connexe.
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 Th\'e9or\'e8me 9\~:
\par }{\fs32 L\rquote algorithme de Dijkstra est de complexit\'e9 O(n}{\fs32\super 2}{\fs32 ).
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 Remarque\~: 
\par }{\fs32 Il existe un autre algorithme qui permet de trouver le chemin minimal entre deux n\'9cuds. Il s\rquote agit en l\rquote occurrence de l\rquote algorithme de Floyd.
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par 
\par }{\b\fs32\ul M. Graphes planaires\~:
\par }{\fs32 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 24\~:
\par }{\fs32 Un graphe est planaire s\rquote il peut \'eatre trac\'e9 dans un plan sans qu\rquote aucun de ses arcs en croise un autre. Un tel trac\'e9 est appel\'e9 une repr\'e9sentation planaire du graphe.
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par 
\par Voir Exemples dans Kenneth H. Rosen page 478
\par 
\par 
\par }{\b\fs32\ul Formule d\rquote Euler\~:
\par }{\fs32 
\par Une repr\'e9sentation planaire d\rquote un graphe divise le plan en r\'e9gions dont une r\'e9gion ouverte.
\par 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 Th\'e9or\'e8me 10\~: 
\par }{\fs32 Soit G un graphe simple planaire connexe avec n arcs et m n\'9cuds. Soit r le nombre de r\'e9gions dans une repr\'e9sentation planaire de G. Alors, r = n \endash  m + 2.
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par 
\par Voir Exemple 4 dans Kenneth H. Rosen page 481
\par 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 Corollaire 1\~: 
\par }{\fs32 Si G est un graphe simple planaire connexe avec n arcs et m n\'9cuds, o\'f9 m >= 3 alors n <= 3 m \endash  6
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 Corollaire 2\~: 
\par }{\fs32 Si G est un graphe simple planaire connexe avec n arcs et m n\'9cuds (o\'f9 m >= 3) et aucun cycle de longueur 3 alors n <= 2 m \endash  4
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par 
\par 
\par 
\par 
\par }{\b\fs32\ul Th\'e9or\'e8me de Kuratowski\~:}{\b\fs32\ul 
\par }{\fs32 
\par }{\fs32 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 D\'e9finition 25 (graphes hom\'e9omorphes)\~:
\par }{\fs32 Deux graphes G1 = (N1, A1) et G2 = (N2, A2) sont hom\'e9omorphes s\rquote ils peuvent \'eatre obtenus \'e0 partir du m\'eame graphe au moyen d\rquote une suite de sous-divisions \'e9l\'e9mentaires. 
\par Une op\'e9ration de sous-division \'e9l\'e9mentaire sur un graphe consiste \'e0 enlever au graphe un arc (a,b) et \'e0 lui additionner un n\'9cud c et les arcs (a,c) et (c,b).
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par 
\par Voir Figure 12 dans Kenneth H. Rosen page 484
\par 
\par 
\par }\pard \qj\widctlpar\adjustright \shading1500\cbpat8 {\b\fs32 Th\'e9or\'e8me 11\~:
\par }{\fs32 Un graphe est non planaire si et seulement s\rquote il contient un sous graphe hom\'e9omorphe \'e0 K}{\fs32\sub 3,3 }{\fs32 ou \'e0 K}{\fs32\sub 5}{\fs32 .
\par }\pard \qj\widctlpar\adjustright \cbpat8 {\fs32 
\par 
\par }{\fs32 Voir }{\fs32 Exemple 7}{\fs32  dans Kenneth H. Rosen page 484
\par }{\fs32 
\par 
\par 
\par }}