Đang chuẩn bị liên kết để tải về tài liệu:
Phần tích thiết kế giải thuật (phần 9)

Tham khảo tài liệu 'phần tích thiết kế giải thuật (phần 9)', 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. 4.1. DEFINITION DU GRAPHE PLANAIRE. C est un graphe qui peut être représenté sur un plan ou une sphère tel que deux arcs ou arêtes ne se coupent pas. La représentation de G sur un plan conformément aux conditions imposées s appelle un graphe planaire topologique. REMARQUE. Deux arêtes ayant un meme sommet sont dit ils ne se coupent pas. Ne Pas se couper EXEMPLE. Un graphe planaire Gi a ses représentations G2 G3 comme suit GRAPHE Gi REPRESENTATIONS G2 G3 du graphe Gi Truong My Dung. Mail tmdung @fit.hcmuns.edu.vn 39 Chapitre 4. Graphe Planaire et ProBleme de Coloriage Soit G un graphe topologique. Une FACE de G est par définition une région 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 îles . 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. 3.1. la face h les autres faces a b c d e f g sont les faces finies. FIG. 4.1. 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 .