Tham khảo tài liệu 'chapitre 1. fondements de la theorie des graphes', khoa học tự nhiên, toán học phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả | Chapitre 1. Fondements de la Theorie des Graphes. CHAPITRE 1. FONDEMENTS DE LA THEORIE DES GRAPHES. DEFINITIONS ET EXEMPLES. DEFINITIONS. 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 . 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. . 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@ 1 Chapitre 1. Fondements de la Theorie des Graphes. 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. . 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 . nous avons u1 Il U2. 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 .
