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...
Nội dung trích xuất từ tài liệu:
Chương 1. Lý thuyết cơ bản của đồ 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 bienorigine et destination). L’arc u part de xi et arrive à xj.Graphiquement, l’arc u se représente de la manière suivante : xi xj FIG.1.1. Arc u=(xi, 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. u4 x4 x1 u7 u1 u3 u5 x5 u6 x2 u2 x3 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, 1Mail=tmdung@fit.hcmuns.edu.vn 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 joueaucun 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êteu=(xi,xj), on dit que u est INCIDENTE aux sommets xi et xj.Exemple. x1 u6 x4 u7 u1 u2 u3 u4 x5 u8 x2 u5 x3 FIG. 1.3. Graphe determineù par (X,U), X = {x1, x2, x3, x4, x5} ; U = {u1, u2, u3, u4, u5, u6, u7, u8}Un multigraphe est un graphe pour lequel il peut exister plusieurs arêtes entredeux sommets.Un graphe est simple : 1. s’il n’est pas un multigraphe ; 2. s’il n’existe pas de boucle.Deux areâtes u, v sont dites paraleølles si et seulement s’elles sont des areâtes incidentesentre deux sommets distincts. Notation : u v. Dans la figure FIG 1.3. nous avons u1 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) ∈ U ; l’ensemble des successeurs de xi est noté Γ(xi). xj est PREDECESSEUR de xi si (xj,xi) ∈ U ; l’ensemble des prédécesseurs de xi est noté Γ-1(xi). L’application Γ qui, à tout élément de X, fait correspondre une partie de X est appelée une APPLICATION MULTIVOQUE. Pour un 1-graphe, G peut être parfaitement déterminé par (X,Γ), notation à la base d’une représentation informatique très utilisée, les LISTES D’ADJACENCE.Truong My Dung, 2Mail=tmdung@fit.hcmuns.edu.vn Chapitre 1. Fondements de la Theorie des Graphes. X = {x1,x2,x3,x4,x5} ;Γ(x1) = x2 ;Γ(x2) = {x3,x4} ; Γ(x3)={x4,x5} ; EXEMPLE. Γ(x4)={x1} ; Γ(x5)={x4}. x4 x1 x5 x2 x3 FIG. 1.4. Graphe déterminé par (X,Γ) ADJACENCE. Deux sommets sont adjacents s’ils sont joints par un arc. Deux arcs sont adjacents s’ils ont au moins une extrémité commune. DEGRES. Le demi- degreù exteùrieur de xi , d+(xi) est le nombre d’arcs ayan ...