Tham khảo tài liệu 'graphe planaire et probleme de coloriage', công nghệ thông tin, kỹ thuật lập trình phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Chapitre 4. Graphe Planaire et ProBleme de Coloriage CHAPITRE 4. GRAPHE PLANAIRE ET PROBLEME DE COLORIAGE. . DEFINITION DU GRAPHE PLANAIRE. C est un graphe qui peut être représenté sur un plan ou une sphere tel que deux arcs ou arêtes ne se coupent pas. La representation de G sur un plan conformément aux conditions imposées s appelle un graphe planaire topologique. REMARQUE. Deux aretes ayant un meme sommet sont dit ils ne se coupent pas. Ne Pas se couper EXEMPLE. Un graphe planaire G1 a ses representations G2 G3 comme suit GRAPHE G1 REPRESENTATIONS G2 G3 du graphe G1 Truong My Dung. Mail tmdung @ 39 Chapitre 4. Graphe Planaire et ProBleme de Coloriage Soit G un graphe topologique. Une FACE de G est par definition une region du plan limitée par des arêtes et qui ne contient ni sommets ni arêtes dans son intérieur nous désignons les faces par les lettres r s t et l ensemble des faces par R. Le CONTOUR d une face r est le cycle formé par les arêtes frontières de r. Deux faces r et s sont dites ADJACENTES si leurs contours ont au moins une arête commune deux faces qui ne se touchent que par un sommet ne sont pas adjacentes. EXEMPLE. Une carte de géographie est un graphe planaire à condition qu il n y ait pas d lles . Ce graphe a pour particularité que chacun de ses sommets a un degré 3 Enfin on notera que dans tout graphe planaire il y a une face illimitée et une seule que l on appelle la FACE INFINIE soit sur la FIG. . la face h les autres faces a b c d e f g sont les faces finies. FIG. . GRAPHE PLANAIRE. Problème des trois villas et des trois usines. On a trois villas a b c que l on veut relier par des conduites à une usine de production d eau d à une usine de production de gaz e à une usine de production d électricité f. Peut - on placer sur un plan les trois villas les trois usines et les trois conduites qui ne se croisent pas en dehors de leurs extrémités Le graphe des villas et des usines permet de définir une famille de graphes non .
