Đ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 6)

tìm hiểu về đồ thị | Chapitre 1. Fondements de la Theorie des Graphes. CHAPITRE 1. FONDEMENTS DE LA THEORIE DES GRAPHES. 1.1 DEFINITIONS ET EXEMPLES. 1.1.1 DEFINITIONS. 1.1.1.1 Graphes Orientés. Un GRAPHE G G X U est déterminé par Un ensemble fini X x1 x2 . xn dont les éléments sont appelés sommets ou nœuds. Un ensemble U u1 u2 _ un du produit cartésien X x X dont les éléments sont appelés arcs. Pour un arc u xi xj xi est l extrémité initiale xj l extrémité finale ou bien origine et destination . L arc u part de x et arrive à xj. Graphiquement l arc u se représente de la manière suivante 0---------------------------------------------------- 0 xi xj FIG.1.1. Arc u xh xj Un arc xi xi est appelé une boucle. Un p-graphe est un graphe dans lequel il n existe jamais plus de p arcs de la forme i j entre deux sommets quelconques. Exemple. FIG. 1.2. Graphe déterminé par X U X X1 X2 X3 X4 X5 U U1 U2 U3 U4 U5 U6 U7 Truong My Dung Mail tmdung@fit.hcmuns.edu.vn 1 Chapitre 1. Fondements de la Theorie des Graphes. 1.1.1.2 Graphes non Orientés. Lors de l étude de certaines propriétés il arrive que l orientation des arcs ne joue aucun rôle. On s intéresse simplement à l existence d arc s entre deux sommets sans en préciser l ordre . Un arc sans orientation est appelé arête. Pour une arête u xi xj on dit que u est INCIDENTE aux sommets xi et xj. Exemple. FIG. 1.3. Graphe determine par X U X X1 X2 X3 X4 X5 U U1 U2 U3 U4 U5 U6 U7 Ug Un multigraphe est un graphe pour lequel il peut exister plusieurs arêtes entre deux sommets. Un graphe est simple 1. s il n est pas un multigraphe 2. s il n existe pas de boucle. Deux aretes u v sont dites paralelles si et seUlement s elles sont des aretes incidentes entre deux sommets distincts. Notation u v. Dans la figure FIG 1.3. nous avons u1 Il U2. 1.1.1.3 Principales Définitions. APPLICATION MULTIVOQUE. Soit G X U un graphe oriente x Xj deux sommets de G. On a xj est SUCCESSEUR de xi si xi xj e U l ensemble des successeurs de xi est noté r xi . xj est PREDECESSEUR de .