Đang chuẩn bị liên kết để tải về tài liệu:
Chương 1. Lý thuyết cơ bản của đồ thị

Một đồ thị G = G (X, U) được xác định bởi một tập hữu hạn X = {x1, x2, ., xn} mà các thành phần được gọi là đỉnh hoặc nút. Một tập hợp U = {u1, u2, ., a} của sản phẩm Đề-X x X mà các thành phần được gọi là vòng cung. Đối với một vòng cung u = (xi, xj), xi là kết thúc ban đầu, xj kết thúc cuối cùng (hoặc nguồn gốc và điểm đến). Các vòng cung từ u xi và xj đạt. Đồ họa, các u vòng cung được biểu diễn. | 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 determine par Un ensemble fini X X1 X2 . xn dont les elements sont appelés sommets ou nrauds. Un ensemble U u1 u2 . un du produit cartésien X x X dont les elements sont appelés arcs. Pour un arc u Xi Xj Xi est l extremite initiale Xj l extremite finale ou bien origine et destination . L arc u part de Xi et arrive à xj. Graphiquement l arc u se represente de la manière suivante 0------------------------K Xi Xj FIG.1.1. Arc u Xi Xj Un arc Xi Xi est appele 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 determine 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 1 orientation des arcs ne joue aucun rôle. On s intéresse simplement à 1 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 Us 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 II v. Dans la figUre FIG 1.3. noUs avons U1 II U2. 1.1.1.3 Principales Définitions. APPLICATION MULTIVOQUE. Soit G X U un graphe oriente Xi 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 xi si xj xi e U l .