[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/cycle-theorie-des-graphiques-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/cycle-theorie-des-graphiques-wikipedia\/","headline":"Cycle (th\u00e9orie des graphiques) – Wikipedia","name":"Cycle (th\u00e9orie des graphiques) – Wikipedia","description":"before-content-x4 Graphique cyclique avec cercle (b, c, d, e, b) UN cycle est un train de bord avec diff\u00e9rents bords","datePublished":"2020-11-06","dateModified":"2020-11-06","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/44a4cee54c4c053e967fe3e7d054edd4?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/c\/c2\/Cyclic-graph.svg\/220px-Cyclic-graph.svg.png","url":"https:\/\/upload.wikimedia.org\/wikipedia\/commons\/thumb\/c\/c2\/Cyclic-graph.svg\/220px-Cyclic-graph.svg.png","height":"146","width":"220"},"url":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/cycle-theorie-des-graphiques-wikipedia\/","wordCount":6826,"articleBody":"     (adsbygoogle = window.adsbygoogle || []).push({});before-content-x4 Graphique cyclique avec cercle (b, c, d, e, b) UN cycle est un train de bord avec diff\u00e9rents bords dans un graphique dans une th\u00e9orie de graphe, dans laquelle les n\u0153uds de d\u00e9marrage et de fin sont les m\u00eames. UN Graphique cyclique est un graphique avec au moins un cycle. Les cycles peuvent \u00eatre trouv\u00e9s dans un graphique par recherche de profondeur modifi\u00e9e, par exemple par tri topologique modifi\u00e9.        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4Table of Contentscycle [ Modifier | Modifier le texte source ]] Cercle [ Modifier | Modifier le texte source ]] Long [ Modifier | Modifier le texte source ]] Graphique cyclique [ Modifier | Modifier le texte source ]] Graphique de panzyklischer [ Modifier | Modifier le texte source ]] cycle [ Modifier | Modifier le texte source ]] Un graphique non vide        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4g = ( DANS , ET ) {displayStyle g = (v, e)} Avec la quantit\u00e9 de n\u0153ud DANS = { X d’abord , X 2 , … , X n } {DisplayStyle v = {x_ {1}, x_ {2}, dotsc, x_ {n}}}} Et la quantit\u00e9 de bord ET = { { X d’abord , X 2 } , { X 2 , X 3 } , … , { X n – d’abord , X n } } {DisplayStyle e = {{x_ {1}, x_ {2}}, {x_ {2}, x_ {3}}, DOTSC, {x_ {n-1}, x_ {n}}}}}}}} avec 2 \u2264 n {displaystyle 2leq n} est appel\u00e9 cycle , si        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4X d’abord = X n {DisplayStyle x_ {1} = x_ {n}} Et les bords { X je – d’abord , X je } {displayStyle {x_ {i-1}, x_ {i}}} avec 2 \u2264 je \u2264 n {displayStyle 2leq ileq n} sont diff\u00e9rents par paires. Aussi un graphique avec une quantit\u00e9 de n\u0153ud { X d’abord } {displayStyle {x_ {1}}} (c’est-\u00e0-dire avec un n\u0153ud) et une quantit\u00e9 vide de bord est g\u00e9n\u00e9ralement appel\u00e9e cycle (longueur 0). Souvent, un cycle de simplicit\u00e9 est d\u00fb \u00e0 la cons\u00e9quence de son n\u0153ud (diff\u00e9rent!) ( X d’abord , X 2 , … , X n – d’abord ) {DisplayStyle (x_ {1}, x_ {2}, dotsc, x_ {n-1})} donn\u00e9. Chaque permutation cyclique de cet \u00e9pisode repr\u00e9sente le m\u00eame cycle, par exemple B. ( X 2 , X 3 , … , X n – d’abord , X d’abord ) {DisplayStyle (x_ {2}, x_ {3}, dotsc, x_ {n-1}, x_ {1})} . Est g = ( DANS , ET ) {displayStyle g = (v, e)} Un graphique, puis une traction de bord ferm\u00e9 est appel\u00e9e dans d’abord , C’est d’abord , dans 2 , C’est 2 , … , C’est n – d’abord , dans n {DisplayStyle v_ {1}, e_ {1}, v_ {2}, e_ {2}, dotsc, e_ {n-1}, v_ {n}}}} avec dans je \u2208 DANS {displayStyle v_ {i} dans v} pour je = d’abord , … , n {displayStyle i = 1, ldots, n} et C’est je \u2208 ET {displayStyle e_ {i} dans e} pour je = d’abord , … , n – d’abord {displayStyle i = 1, ldots, n-1}  cycle , si dans 1= dans n{displayStyle v_ {1} = v_ {n}} s’applique, d. H. Si celui de la dans je {displayStyle v_ {i}} et C’est je {displayStyle e_ {i}} Le sous-graphique \u00e9duqu\u00e9 est un cycle dans le sens ci-dessus. Un cycle dans un graphique dirig\u00e9 est appel\u00e9 cycle dirig\u00e9 et dans un graphique soussign\u00e9 cycle d\u00e9loyal . Cercle [ Modifier | Modifier le texte source ]] En cons\u00e9quence, un cycle est appel\u00e9 ( dans d’abord , … , dans n – d’abord ) {displayStyle (v_ {1}, ldots, v_ {n-1})} Dans un graphique Cercle , si dans d’abord , … , dans n – d’abord {displayStyle v_ {1}, ldots, v_ {n-1}} Une fa\u00e7on est. Vous obtenez donc un cercle par le fait que les n\u0153uds finaux dans d’abord {displayStyle v_ {1}} et dans n – d’abord {displayStyle v_ {n-1}} Un chemin \u00e0 travers un bord suppl\u00e9mentaire { X n – d’abord , X d’abord } {DisplayStyle {x_ {n-1}, x_ {1}}}} Soyez connect\u00e9s. [d’abord] Un cercle est un cycle dans lequel seuls les n\u0153uds de d\u00e9marrage et de fin sont les m\u00eames, donc cela s’applique \u00e9galement dans i\u2260 dans j{displayStyle v_ {i} neq v_ {j}} pour je , J \u2208 { d’abord , … , n – d’abord } {displayStyle I, Jin {1, ldots, n-1}} avec je \u2260 J {Displaystyle inq j} . Un cercle dans un graphique dirig\u00e9 est appel\u00e9 cercle dirig\u00e9 et dans un graphique soussign\u00e9 cercle non stade . Un bord qui relie deux n\u0153uds d’un cercle, mais qui ne fait pas partie du cercle, est appel\u00e9 tendon du cercle. Long [ Modifier | Modifier le texte source ]] En graphiques sans poids de bord n – d’abord {displaystyle n-1} le Long d’un cycle ou d’un cercle ( dans d’abord , … , dans n – d’abord ) {displayStyle (v_ {1}, ldots, v_ {n-1})} . Vous comptez donc clairement le nombre d’ar\u00eates associ\u00e9es C’est d’abord = { dans d’abord , dans 2 } , C’est 2 = { dans 2 , dans 3 } , … , C’est n – d’abord = { dans n – d’abord , dans 0 } {displayStyle e_ {1} = {v_ {1}, v_ {2}}, e_ {2} = {v_ {2}, v_ {3}}, dotsc, e_ {n-1} = {v_ {n-}, v_ {0}, v_ {0}, {0}, V_ {0}, v_ {0}, V_ {0}, V_ {0}, V_ {0}, V_ {0}, V_ {0}, }, V_ . Dans un graphique pond\u00e9r\u00e9 par le bord, la longueur d’un cycle ou d’un cercle est la somme des poids de bord de tous les bords associ\u00e9s. Graphique cyclique [ Modifier | Modifier le texte source ]] Un graphique avec au moins un cycle est appel\u00e9 cyclique . Obtenez des graphiques sans cycles acyclique ou appel\u00e9 for\u00eat. Un cycle ou un cercle signifie banal S’il contient moins de trois n\u0153uds. Les cercles ou cycles triviaux ne sont g\u00e9n\u00e9ralement pas pris en compte lors de l’analyse des graphiques. Un cercle qui contient exactement trois n\u0153uds Triangle appel\u00e9. Un graphique sans triangle est alors appel\u00e9 triangulaire . Quand Taillenweite Un graphique est la longueur d’un cercle non trivial le plus court. Si le graphique n’a pas de cercle, la largeur de la taille est infinie. Les graphiques cycliques les plus simples sont les graphiques circulaires. Graphique de panzyklischer [ Modifier | Modifier le texte source ]] Un graphique est appel\u00e9 bord-cyclique , si chaque bord sur un cercle de longueur p {displaystyle p} pour tous p \u2208 { d’abord , 2 , … , | DANS ( g ) | } {DisplayStyle Pin {1,2, ldots, | v (g) |}} mensonges. Un graphique est appel\u00e9 n\u0153ud-cyclique Si chaque n\u0153ud sur un cercle de longueur p {displaystyle p} pour tous p \u2208 { d’abord , 2 , … , | DANS ( g ) | } {DisplayStyle Pin {1,2, ldots, | v (g) |}} mensonges. Un graphique est appel\u00e9 panzyklisch S’il est pour tout le monde p \u2208 { 3 , 4 , … , | DANS ( g ) | } {DisplayStyle Pin {3,4, ldots, | v (g) |}} un cercle de longueur p {displaystyle p} poss\u00e8de. Les graphiques cycliques \u00e2g\u00e9s sont \u00e9galement des graphiques n\u0153uds et cycliques et n\u0153uds. Les graphiques penycliques sont particuli\u00e8rement hamiltonch. \u00c0 une num\u00e9rotation arbitrairement sp\u00e9cifi\u00e9e des bords UN = { un d’abord , un 2 , … , un m } {displayStyle a = {a_ {1}, a_ {2}, ldots, a_ {m}}} signifie un \u00e9l\u00e9ment X = ( X je ) \u2208 R m {displayStyle x = (x_ {i}) dans mathbb {r} ^ {m}}  Vecteur d’incidence \u00c0 la quantit\u00e9 de bord M {displaystyle m} , chutes X i= {0, falls\u00a0ai\u2209M\u2227ai\u22121\u2209M1, falls\u00a0ai\u2208M\u22121, falls\u00a0ai\u22121\u2208M{displaystyle x_{i}={begin{cases}0&{mbox{, falls }}a_{i}notin Mland {a_{i}}^{-1}notin M\\1&{mbox{, falls }}a_{i}in M\\-1&{mbox{, falls }}{a_{i}}^{-1}in M\\end{cases}}} est applicable. Si les bords ont \u00e9galement un poids non n\u00e9gatif, les entr\u00e9es du vecteur sont multipli\u00e9es par ce poids. La quantit\u00e9 de tous les cercles d\u00e9crits de cette mani\u00e8re Cycliste , une salle sous-vectorielle du F 2 m {displayStyle Mathbb {f} _ {2} ^ {m}} . Une base du cycliste est le Cercles fondamentaux . Chaque cercle fondamental est cr\u00e9\u00e9 en ajoutant un bord \u00e0 un arbre de serrage. Le Chambre confortable est la salle vectorielle de tous les vecteurs d’incidence g\u00e9n\u00e9r\u00e9s par les coupes. C’est aussi une salle sous-vectorielle du F 2 m {displayStyle Mathbb {f} _ {2} ^ {m}} Et donne toute la pi\u00e8ce en somme directe avec la salle du cycle. Une base des kozyclanis est le Coupes fondamentales . Chaque coupe fondamentale est cr\u00e9\u00e9e en omettant un bord d’un arbre couvrant comme composant de contexte. Pour chaque n\u0153ud v: visit\u00e9 (v) = faux, fini (v) = fauxPour chaque n\u0153ud V:  DFS (V) DFS (V):  Si fini (v)    retour  Si vous \u00eates visit\u00e9 (V)    \"Cycle trouv\u00e9\" et d\u00e9molition  Visit\u00e9 (v) = vrai  Pour chaque successeur w    DFS (W)  fini (v) = vrai Le successeur signifie tout pour les graphiques dirig\u00e9s et in\u00e9vitables dans n\u0153ud connect\u00e9, sauf pour celui DFS (V) appel\u00e9. Cela emp\u00eache l’algorithme qui emp\u00eache \u00e9galement les cycles triviaux, ce qui est toujours le cas dans chaque graphique ind\u00e9niable avec un bord non vide. \u2191  Reinhard Diesel: Graphentheorie . 3e, nouvel \u00e9d. et Erw Edition. Springer, Berlin, 2006, ISBN 3-540-21391-0, S.  7  ff . ( Diesel- graph-heley.com ).        (adsbygoogle = window.adsbygoogle || []).push({});after-content-x4"},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/all2fr\/wiki1\/cycle-theorie-des-graphiques-wikipedia\/#breadcrumbitem","name":"Cycle (th\u00e9orie des graphiques) – Wikipedia"}}]}]