CINXE.COM

<!DOCTYPE html> <html class="client-nojs vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available" lang="fr" dir="ltr"> <head> <meta charset="UTF-8"> <title>Tracé de graphes — Wikipédia</title> <script>(function(){var className="client-js vector-feature-language-in-header-enabled vector-feature-language-in-main-page-header-disabled vector-feature-sticky-header-disabled vector-feature-page-tools-pinned-disabled vector-feature-toc-pinned-clientpref-1 vector-feature-main-menu-pinned-disabled vector-feature-limited-width-clientpref-1 vector-feature-limited-width-content-enabled vector-feature-custom-font-size-clientpref-1 vector-feature-appearance-pinned-clientpref-1 vector-feature-night-mode-enabled skin-theme-clientpref-day vector-toc-available";var cookie=document.cookie.match(/(?:^|; )frwikimwclientpreferences=([^;]+)/);if(cookie){cookie[1].split('%2C').forEach(function(pref){className=className.replace(new RegExp('(^| )'+pref.replace(/-clientpref-\w+$|[^\w-]+/g,'')+'-clientpref-\\w+( |$)'),'$1'+pref+'$2');});}document.documentElement.className=className;}());RLCONF={"wgBreakFrames":false,"wgSeparatorTransformTable":[",\t."," \t,"],"wgDigitTransformTable":["",""], "wgDefaultDateFormat":"dmy","wgMonthNames":["","janvier","février","mars","avril","mai","juin","juillet","août","septembre","octobre","novembre","décembre"],"wgRequestId":"c85ba2ab-486a-46f9-bef0-1cdc4d573830","wgCanonicalNamespace":"","wgCanonicalSpecialPageName":false,"wgNamespaceNumber":0,"wgPageName":"Tracé_de_graphes","wgTitle":"Tracé de graphes","wgCurRevisionId":210301171,"wgRevisionId":210301171,"wgArticleId":799036,"wgIsArticle":true,"wgIsRedirect":false,"wgAction":"view","wgUserName":null,"wgUserGroups":["*"],"wgCategories":["Article contenant un appel à traduction en anglais","Portail:Informatique théorique/Articles liés","Portail:Informatique/Articles liés","Projet:Mathématiques/Articles","Théorie topologique des graphes"],"wgPageViewLanguage":"fr","wgPageContentLanguage":"fr","wgPageContentModel":"wikitext","wgRelevantPageName":"Tracé_de_graphes","wgRelevantArticleId":799036,"wgIsProbablyEditable":true,"wgRelevantPageIsProbablyEditable":true,"wgRestrictionEdit" :[],"wgRestrictionMove":[],"wgNoticeProject":"wikipedia","wgCiteReferencePreviewsActive":true,"wgMediaViewerOnClick":true,"wgMediaViewerEnabledByDefault":true,"wgPopupsFlags":0,"wgVisualEditor":{"pageLanguageCode":"fr","pageLanguageDir":"ltr","pageVariantFallbacks":"fr"},"wgMFDisplayWikibaseDescriptions":{"search":true,"watchlist":true,"tagline":true,"nearby":true},"wgWMESchemaEditAttemptStepOversample":false,"wgWMEPageLength":8000,"wgRelatedArticlesCompat":[],"wgEditSubmitButtonLabelPublish":true,"wgULSPosition":"interlanguage","wgULSisCompactLinksEnabled":false,"wgVector2022LanguageInHeader":true,"wgULSisLanguageSelectorEmpty":false,"wgWikibaseItemId":"Q739462","wgCheckUserClientHintsHeadersJsApi":["brands","architecture","bitness","fullVersionList","mobile","model","platform","platformVersion"],"GEHomepageSuggestedEditsEnableTopics":true,"wgGETopicsMatchModeEnabled":false,"wgGEStructuredTaskRejectionReasonTextInputEnabled":false,"wgGELevelingUpEnabledForUser":false};RLSTATE={ "ext.globalCssJs.user.styles":"ready","site.styles":"ready","user.styles":"ready","ext.globalCssJs.user":"ready","user":"ready","user.options":"loading","skins.vector.search.codex.styles":"ready","skins.vector.styles":"ready","skins.vector.icons":"ready","ext.wikimediamessages.styles":"ready","ext.visualEditor.desktopArticleTarget.noscript":"ready","ext.uls.interlanguage":"ready","wikibase.client.init":"ready","ext.wikimediaBadges":"ready"};RLPAGEMODULES=["mediawiki.page.media","site","mediawiki.page.ready","mediawiki.toc","skins.vector.js","ext.centralNotice.geoIP","ext.centralNotice.startUp","ext.gadget.ArchiveLinks","ext.gadget.Wdsearch","ext.urlShortener.toolbar","ext.centralauth.centralautologin","mmv.bootstrap","ext.popups","ext.visualEditor.desktopArticleTarget.init","ext.visualEditor.targetLoader","ext.echo.centralauth","ext.eventLogging","ext.wikimediaEvents","ext.navigationTiming","ext.uls.interface","ext.cx.eventlogging.campaigns","ext.cx.uls.quick.actions", "wikibase.client.vector-2022","ext.checkUser.clientHints","ext.quicksurveys.init","ext.growthExperiments.SuggestedEditSession"];</script> <script>(RLQ=window.RLQ||[]).push(function(){mw.loader.impl(function(){return["user.options@12s5i",function($,jQuery,require,module){mw.user.tokens.set({"patrolToken":"+\\","watchToken":"+\\","csrfToken":"+\\"}); }];});});</script> <link rel="stylesheet" href="/w/load.php?lang=fr&modules=ext.uls.interlanguage%7Cext.visualEditor.desktopArticleTarget.noscript%7Cext.wikimediaBadges%7Cext.wikimediamessages.styles%7Cskins.vector.icons%2Cstyles%7Cskins.vector.search.codex.styles%7Cwikibase.client.init&only=styles&skin=vector-2022"> <script async="" src="/w/load.php?lang=fr&modules=startup&only=scripts&raw=1&skin=vector-2022"></script> <meta name="ResourceLoaderDynamicStyles" content=""> <link rel="stylesheet" href="/w/load.php?lang=fr&modules=site.styles&only=styles&skin=vector-2022"> <meta name="generator" content="MediaWiki 1.44.0-wmf.6"> <meta name="referrer" content="origin"> <meta name="referrer" content="origin-when-cross-origin"> <meta name="robots" content="max-image-preview:standard"> <meta name="format-detection" content="telephone=no"> <meta name="viewport" content="width=1120"> <meta property="og:title" content="Tracé de graphes — Wikipédia"> <meta property="og:type" content="website"> <link rel="preconnect" href="//upload.wikimedia.org"> <link rel="alternate" media="only screen and (max-width: 640px)" href="//fr.m.wikipedia.org/wiki/Trac%C3%A9_de_graphes"> <link rel="alternate" type="application/x-wiki" title="Modifier" href="/w/index.php?title=Trac%C3%A9_de_graphes&action=edit"> <link rel="apple-touch-icon" href="/static/apple-touch/wikipedia.png"> <link rel="icon" href="/static/favicon/wikipedia.ico"> <link rel="search" type="application/opensearchdescription+xml" href="/w/rest.php/v1/search" title="Wikipédia (fr)"> <link rel="EditURI" type="application/rsd+xml" href="//fr.wikipedia.org/w/api.php?action=rsd"> <link rel="canonical" href="https://fr.wikipedia.org/wiki/Trac%C3%A9_de_graphes"> <link rel="license" href="https://creativecommons.org/licenses/by-sa/4.0/deed.fr"> <link rel="alternate" type="application/atom+xml" title="Flux Atom de Wikipédia" href="/w/index.php?title=Sp%C3%A9cial:Modifications_r%C3%A9centes&feed=atom"> <link rel="dns-prefetch" href="//meta.wikimedia.org" /> <link rel="dns-prefetch" href="login.wikimedia.org"> </head> <body class="skin--responsive skin-vector skin-vector-search-vue mediawiki ltr sitedir-ltr mw-hide-empty-elt ns-0 ns-subject mw-editable page-Tracé_de_graphes rootpage-Tracé_de_graphes skin-vector-2022 action-view"><a class="mw-jump-link" href="#bodyContent">Aller au contenu</a> <div class="vector-header-container"> <header class="vector-header mw-header"> <div class="vector-header-start"> <nav class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-dropdown" class="vector-dropdown vector-main-menu-dropdown vector-button-flush-left vector-button-flush-right" > <input type="checkbox" id="vector-main-menu-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-main-menu-dropdown" class="vector-dropdown-checkbox " aria-label="Menu principal" > <label id="vector-main-menu-dropdown-label" for="vector-main-menu-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-menu mw-ui-icon-wikimedia-menu"></span> <span class="vector-dropdown-label-text">Menu principal</span> </label> <div class="vector-dropdown-content"> <div id="vector-main-menu-unpinned-container" class="vector-unpinned-container"> <div id="vector-main-menu" class="vector-main-menu vector-pinnable-element"> <div class="vector-pinnable-header vector-main-menu-pinnable-header vector-pinnable-header-unpinned" data-feature-name="main-menu-pinned" data-pinnable-element-id="vector-main-menu" data-pinned-container-id="vector-main-menu-pinned-container" data-unpinned-container-id="vector-main-menu-unpinned-container" > <div class="vector-pinnable-header-label">Menu principal</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-main-menu.pin">déplacer vers la barre latérale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-main-menu.unpin">masquer</button> </div> <div id="p-navigation" class="vector-menu mw-portlet mw-portlet-navigation" > <div class="vector-menu-heading"> Navigation </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-mainpage-description" class="mw-list-item"><a href="/wiki/Wikip%C3%A9dia:Accueil_principal" title="Accueil général [z]" accesskey="z"><span>Accueil</span></a></li><li id="n-thema" class="mw-list-item"><a href="/wiki/Portail:Accueil"><span>Portails thématiques</span></a></li><li id="n-randompage" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Page_au_hasard" title="Affiche un article au hasard [x]" accesskey="x"><span>Article au hasard</span></a></li><li id="n-contact" class="mw-list-item"><a href="/wiki/Wikip%C3%A9dia:Contact"><span>Contact</span></a></li> </ul> </div> </div> <div id="p-Contribuer" class="vector-menu mw-portlet mw-portlet-Contribuer" > <div class="vector-menu-heading"> Contribuer </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="n-aboutwp" class="mw-list-item"><a href="/wiki/Aide:D%C3%A9buter"><span>Débuter sur Wikipédia</span></a></li><li id="n-help" class="mw-list-item"><a href="/wiki/Aide:Accueil" title="Accès à l’aide"><span>Aide</span></a></li><li id="n-portal" class="mw-list-item"><a href="/wiki/Wikip%C3%A9dia:Accueil_de_la_communaut%C3%A9" title="À propos du projet, ce que vous pouvez faire, où trouver les informations"><span>Communauté</span></a></li><li id="n-recentchanges" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Modifications_r%C3%A9centes" title="Liste des modifications récentes sur le wiki [r]" accesskey="r"><span>Modifications récentes</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> <a href="/wiki/Wikip%C3%A9dia:Accueil_principal" class="mw-logo"> <img class="mw-logo-icon" src="/static/images/icons/wikipedia.png" alt="" aria-hidden="true" height="50" width="50"> <span class="mw-logo-container skin-invert"> <img class="mw-logo-wordmark" alt="Wikipédia" src="/static/images/mobile/copyright/wikipedia-wordmark-fr.svg" style="width: 7.4375em; height: 1.125em;"> <img class="mw-logo-tagline" alt="l'encyclopédie libre" src="/static/images/mobile/copyright/wikipedia-tagline-fr.svg" width="120" height="13" style="width: 7.5em; height: 0.8125em;"> </span> </a> </div> <div class="vector-header-end"> <div id="p-search" role="search" class="vector-search-box-vue vector-search-box-collapses vector-search-box-show-thumbnail vector-search-box-auto-expand-width vector-search-box"> <a href="/wiki/Sp%C3%A9cial:Recherche" class="cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only search-toggle" title="Rechercher sur Wikipédia [f]" accesskey="f"><span class="vector-icon mw-ui-icon-search mw-ui-icon-wikimedia-search"></span> <span>Rechercher</span> </a> <div class="vector-typeahead-search-container"> <div class="cdx-typeahead-search cdx-typeahead-search--show-thumbnail cdx-typeahead-search--auto-expand-width"> <form action="/w/index.php" id="searchform" class="cdx-search-input cdx-search-input--has-end-button"> <div id="simpleSearch" class="cdx-search-input__input-wrapper" data-search-loc="header-moved"> <div class="cdx-text-input cdx-text-input--has-start-icon"> <input class="cdx-text-input__input" type="search" name="search" placeholder="Rechercher sur Wikipédia" aria-label="Rechercher sur Wikipédia" autocapitalize="sentences" title="Rechercher sur Wikipédia [f]" accesskey="f" id="searchInput" > <span class="cdx-text-input__icon cdx-text-input__start-icon"></span> </div> <input type="hidden" name="title" value="Spécial:Recherche"> </div> <button class="cdx-button cdx-search-input__end-button">Rechercher</button> </form> </div> </div> </div> <nav class="vector-user-links vector-user-links-wide" aria-label="Outils personnels"> <div class="vector-user-links-main"> <div id="p-vector-user-menu-preferences" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-userpage" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <nav class="vector-appearance-landmark" aria-label="Apparence"> <div id="vector-appearance-dropdown" class="vector-dropdown " title="Modifier l'apparence de la taille, de la largeur et de la couleur de la police de la page" > <input type="checkbox" id="vector-appearance-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-appearance-dropdown" class="vector-dropdown-checkbox " aria-label="Apparence" > <label id="vector-appearance-dropdown-label" for="vector-appearance-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-appearance mw-ui-icon-wikimedia-appearance"></span> <span class="vector-dropdown-label-text">Apparence</span> </label> <div class="vector-dropdown-content"> <div id="vector-appearance-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <div id="p-vector-user-menu-notifications" class="vector-menu mw-portlet emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> <div id="p-vector-user-menu-overflow" class="vector-menu mw-portlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=fr.wikipedia.org&uselang=fr" class=""><span>Faire un don</span></a> </li> <li id="pt-createaccount-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Sp%C3%A9cial:Cr%C3%A9er_un_compte&returnto=Trac%C3%A9+de+graphes" title="Nous vous encourageons à créer un compte utilisateur et vous connecter ; ce n’est cependant pas obligatoire." class=""><span>Créer un compte</span></a> </li> <li id="pt-login-2" class="user-links-collapsible-item mw-list-item user-links-collapsible-item"><a data-mw="interface" href="/w/index.php?title=Sp%C3%A9cial:Connexion&returnto=Trac%C3%A9+de+graphes" title="Nous vous encourageons à vous connecter ; ce n’est cependant pas obligatoire. [o]" accesskey="o" class=""><span>Se connecter</span></a> </li> </ul> </div> </div> </div> <div id="vector-user-links-dropdown" class="vector-dropdown vector-user-menu vector-button-flush-right vector-user-menu-logged-out" title="Plus d’options" > <input type="checkbox" id="vector-user-links-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-user-links-dropdown" class="vector-dropdown-checkbox " aria-label="Outils personnels" > <label id="vector-user-links-dropdown-label" for="vector-user-links-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-ellipsis mw-ui-icon-wikimedia-ellipsis"></span> <span class="vector-dropdown-label-text">Outils personnels</span> </label> <div class="vector-dropdown-content"> <div id="p-personal" class="vector-menu mw-portlet mw-portlet-personal user-links-collapsible-item" title="Menu utilisateur" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-sitesupport" class="user-links-collapsible-item mw-list-item"><a href="https://donate.wikimedia.org/?wmf_source=donate&wmf_medium=sidebar&wmf_campaign=fr.wikipedia.org&uselang=fr"><span>Faire un don</span></a></li><li id="pt-createaccount" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:Cr%C3%A9er_un_compte&returnto=Trac%C3%A9+de+graphes" title="Nous vous encourageons à créer un compte utilisateur et vous connecter ; ce n’est cependant pas obligatoire."><span class="vector-icon mw-ui-icon-userAdd mw-ui-icon-wikimedia-userAdd"></span> <span>Créer un compte</span></a></li><li id="pt-login" class="user-links-collapsible-item mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:Connexion&returnto=Trac%C3%A9+de+graphes" title="Nous vous encourageons à vous connecter ; ce n’est cependant pas obligatoire. [o]" accesskey="o"><span class="vector-icon mw-ui-icon-logIn mw-ui-icon-wikimedia-logIn"></span> <span>Se connecter</span></a></li> </ul> </div> </div> <div id="p-user-menu-anon-editor" class="vector-menu mw-portlet mw-portlet-user-menu-anon-editor" > <div class="vector-menu-heading"> Pages pour les contributeurs déconnectés <a href="/wiki/Aide:Premiers_pas" aria-label="En savoir plus sur la contribution"><span>en savoir plus</span></a> </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="pt-anoncontribs" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Mes_contributions" title="Une liste des modifications effectuées depuis cette adresse IP [y]" accesskey="y"><span>Contributions</span></a></li><li id="pt-anontalk" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Mes_discussions" title="La page de discussion pour les contributions depuis cette adresse IP [n]" accesskey="n"><span>Discussion</span></a></li> </ul> </div> </div> </div> </div> </nav> </div> </header> </div> <div class="mw-page-container"> <div class="mw-page-container-inner"> <div class="vector-sitenotice-container"> <div id="siteNotice"></div> </div> <div class="vector-column-start"> <div class="vector-main-menu-container"> <div id="mw-navigation"> <nav id="mw-panel" class="vector-main-menu-landmark" aria-label="Site"> <div id="vector-main-menu-pinned-container" class="vector-pinned-container"> </div> </nav> </div> </div> <div class="vector-sticky-pinned-container"> <nav id="mw-panel-toc" aria-label="Sommaire" data-event-name="ui.sidebar-toc" class="mw-table-of-contents-container vector-toc-landmark"> <div id="vector-toc-pinned-container" class="vector-pinned-container"> <div id="vector-toc" class="vector-toc vector-pinnable-element"> <div class="vector-pinnable-header vector-toc-pinnable-header vector-pinnable-header-pinned" data-feature-name="toc-pinned" data-pinnable-element-id="vector-toc" > <h2 class="vector-pinnable-header-label">Sommaire</h2> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-toc.pin">déplacer vers la barre latérale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-toc.unpin">masquer</button> </div> <ul class="vector-toc-contents" id="mw-panel-toc-list"> <li id="toc-mw-content-text" class="vector-toc-list-item vector-toc-level-1"> <a href="#" class="vector-toc-link"> <div class="vector-toc-text">Début</div> </a> </li> <li id="toc-Types_de_tracés" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Types_de_tracés"> <div class="vector-toc-text"> <span class="vector-toc-numb">1</span> <span>Types de tracés</span> </div> </a> <ul id="toc-Types_de_tracés-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Méthodes" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Méthodes"> <div class="vector-toc-text"> <span class="vector-toc-numb">2</span> <span>Méthodes</span> </div> </a> <ul id="toc-Méthodes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Métriques" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Métriques"> <div class="vector-toc-text"> <span class="vector-toc-numb">3</span> <span>Métriques</span> </div> </a> <ul id="toc-Métriques-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Voir_aussi" class="vector-toc-list-item vector-toc-level-1 vector-toc-list-item-expanded"> <a class="vector-toc-link" href="#Voir_aussi"> <div class="vector-toc-text"> <span class="vector-toc-numb">4</span> <span>Voir aussi</span> </div> </a> <button aria-controls="toc-Voir_aussi-sublist" class="cdx-button cdx-button--weight-quiet cdx-button--icon-only vector-toc-toggle"> <span class="vector-icon mw-ui-icon-wikimedia-expand"></span> <span>Afficher / masquer la sous-section Voir aussi</span> </button> <ul id="toc-Voir_aussi-sublist" class="vector-toc-list"> <li id="toc-Articles_connexes" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Articles_connexes"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.1</span> <span>Articles connexes</span> </div> </a> <ul id="toc-Articles_connexes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Bibliographie" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Bibliographie"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.2</span> <span>Bibliographie</span> </div> </a> <ul id="toc-Bibliographie-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Liens_externes" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Liens_externes"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.3</span> <span>Liens externes</span> </div> </a> <ul id="toc-Liens_externes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Outils_de_tracés_de_layout_de_graphes" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Outils_de_tracés_de_layout_de_graphes"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.4</span> <span>Outils de tracés de layout de graphes</span> </div> </a> <ul id="toc-Outils_de_tracés_de_layout_de_graphes-sublist" class="vector-toc-list"> </ul> </li> <li id="toc-Formats_de_graphes" class="vector-toc-list-item vector-toc-level-2"> <a class="vector-toc-link" href="#Formats_de_graphes"> <div class="vector-toc-text"> <span class="vector-toc-numb">4.5</span> <span>Formats de graphes</span> </div> </a> <ul id="toc-Formats_de_graphes-sublist" class="vector-toc-list"> </ul> </li> </ul> </li> </ul> </div> </div> </nav> </div> </div> <div class="mw-content-container"> <main id="content" class="mw-body"> <header class="mw-body-header vector-page-titlebar"> <nav aria-label="Sommaire" class="vector-toc-landmark"> <div id="vector-page-titlebar-toc" class="vector-dropdown vector-page-titlebar-toc vector-button-flush-left" > <input type="checkbox" id="vector-page-titlebar-toc-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-titlebar-toc" class="vector-dropdown-checkbox " aria-label="Basculer la table des matières" > <label id="vector-page-titlebar-toc-label" for="vector-page-titlebar-toc-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--icon-only " aria-hidden="true" ><span class="vector-icon mw-ui-icon-listBullet mw-ui-icon-wikimedia-listBullet"></span> <span class="vector-dropdown-label-text">Basculer la table des matières</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-titlebar-toc-unpinned-container" class="vector-unpinned-container"> </div> </div> </div> </nav> <h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Tracé de graphes</span></h1> <div id="p-lang-btn" class="vector-dropdown mw-portlet mw-portlet-lang" > <input type="checkbox" id="p-lang-btn-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-p-lang-btn" class="vector-dropdown-checkbox mw-interlanguage-selector" aria-label="Aller à un article dans une autre langue. Disponible en 10 langues." > <label id="p-lang-btn-label" for="p-lang-btn-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet cdx-button--action-progressive mw-portlet-lang-heading-10" aria-hidden="true" ><span class="vector-icon mw-ui-icon-language-progressive mw-ui-icon-wikimedia-language-progressive"></span> <span class="vector-dropdown-label-text">10 langues</span> </label> <div class="vector-dropdown-content"> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li class="interlanguage-link interwiki-de mw-list-item"><a href="https://de.wikipedia.org/wiki/Graphzeichnen" title="Graphzeichnen – allemand" lang="de" hreflang="de" data-title="Graphzeichnen" data-language-autonym="Deutsch" data-language-local-name="allemand" class="interlanguage-link-target"><span>Deutsch</span></a></li><li class="interlanguage-link interwiki-en mw-list-item"><a href="https://en.wikipedia.org/wiki/Graph_drawing" title="Graph drawing – anglais" lang="en" hreflang="en" data-title="Graph drawing" data-language-autonym="English" data-language-local-name="anglais" class="interlanguage-link-target"><span>English</span></a></li><li class="interlanguage-link interwiki-es mw-list-item"><a href="https://es.wikipedia.org/wiki/Dibujo_de_grafos" title="Dibujo de grafos – espagnol" lang="es" hreflang="es" data-title="Dibujo de grafos" data-language-autonym="Español" data-language-local-name="espagnol" class="interlanguage-link-target"><span>Español</span></a></li><li class="interlanguage-link interwiki-fa mw-list-item"><a href="https://fa.wikipedia.org/wiki/%D8%B1%D8%B3%D9%85_%DA%AF%D8%B1%D8%A7%D9%81" title="رسم گراف – persan" lang="fa" hreflang="fa" data-title="رسم گراف" data-language-autonym="فارسی" data-language-local-name="persan" class="interlanguage-link-target"><span>فارسی</span></a></li><li class="interlanguage-link interwiki-it mw-list-item"><a href="https://it.wikipedia.org/wiki/Raffigurazione_di_un_grafo" title="Raffigurazione di un grafo – italien" lang="it" hreflang="it" data-title="Raffigurazione di un grafo" data-language-autonym="Italiano" data-language-local-name="italien" class="interlanguage-link-target"><span>Italiano</span></a></li><li class="interlanguage-link interwiki-ko mw-list-item"><a href="https://ko.wikipedia.org/wiki/%EA%B7%B8%EB%9E%98%ED%94%84_%EA%B7%B8%EB%A6%AC%EA%B8%B0" title="그래프 그리기 – coréen" lang="ko" hreflang="ko" data-title="그래프 그리기" data-language-autonym="한국어" data-language-local-name="coréen" class="interlanguage-link-target"><span>한국어</span></a></li><li class="interlanguage-link interwiki-ru mw-list-item"><a href="https://ru.wikipedia.org/wiki/%D0%92%D0%B8%D0%B7%D1%83%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D0%BE%D0%B2" title="Визуализация графов – russe" lang="ru" hreflang="ru" data-title="Визуализация графов" data-language-autonym="Русский" data-language-local-name="russe" class="interlanguage-link-target"><span>Русский</span></a></li><li class="interlanguage-link interwiki-ta mw-list-item"><a href="https://ta.wikipedia.org/wiki/%E0%AE%95%E0%AF%8B%E0%AE%9F%E0%AF%8D%E0%AE%9F%E0%AF%81%E0%AE%B0%E0%AF%81_%E0%AE%B5%E0%AE%B0%E0%AF%88%E0%AE%AA%E0%AE%9F%E0%AE%AE%E0%AF%8D" title="கோட்டுரு வரைபடம் – tamoul" lang="ta" hreflang="ta" data-title="கோட்டுரு வரைபடம்" data-language-autonym="தமிழ்" data-language-local-name="tamoul" class="interlanguage-link-target"><span>தமிழ்</span></a></li><li class="interlanguage-link interwiki-tl mw-list-item"><a href="https://tl.wikipedia.org/wiki/Pagguhit_ng_grap" title="Pagguhit ng grap – tagalog" lang="tl" hreflang="tl" data-title="Pagguhit ng grap" data-language-autonym="Tagalog" data-language-local-name="tagalog" class="interlanguage-link-target"><span>Tagalog</span></a></li><li class="interlanguage-link interwiki-uk mw-list-item"><a href="https://uk.wikipedia.org/wiki/%D0%92%D1%96%D0%B7%D1%83%D0%B0%D0%BB%D1%96%D0%B7%D0%B0%D1%86%D1%96%D1%8F_%D0%B3%D1%80%D0%B0%D1%84%D1%96%D0%B2" title="Візуалізація графів – ukrainien" lang="uk" hreflang="uk" data-title="Візуалізація графів" data-language-autonym="Українська" data-language-local-name="ukrainien" class="interlanguage-link-target"><span>Українська</span></a></li> </ul> <div class="after-portlet after-portlet-lang"><span class="wb-langlinks-edit wb-langlinks-link"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q739462#sitelinks-wikipedia" title="Modifier les liens interlangues" class="wbc-editpage">Modifier les liens</a></span></div> </div> </div> </div> </header> <div class="vector-page-toolbar"> <div class="vector-page-toolbar-container"> <div id="left-navigation"> <nav aria-label="Espaces de noms"> <div id="p-associated-pages" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-associated-pages" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-nstab-main" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Trac%C3%A9_de_graphes" title="Voir le contenu de la page [c]" accesskey="c"><span>Article</span></a></li><li id="ca-talk" class="vector-tab-noicon mw-list-item"><a href="/wiki/Discussion:Trac%C3%A9_de_graphes" rel="discussion" title="Discussion au sujet de cette page de contenu [t]" accesskey="t"><span>Discussion</span></a></li> </ul> </div> </div> <div id="vector-variants-dropdown" class="vector-dropdown emptyPortlet" > <input type="checkbox" id="vector-variants-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-variants-dropdown" class="vector-dropdown-checkbox " aria-label="Modifier la variante de langue" > <label id="vector-variants-dropdown-label" for="vector-variants-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">français</span> </label> <div class="vector-dropdown-content"> <div id="p-variants" class="vector-menu mw-portlet mw-portlet-variants emptyPortlet" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> </ul> </div> </div> </div> </div> </nav> </div> <div id="right-navigation" class="vector-collapsible"> <nav aria-label="Affichages"> <div id="p-views" class="vector-menu vector-menu-tabs mw-portlet mw-portlet-views" > <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-view" class="selected vector-tab-noicon mw-list-item"><a href="/wiki/Trac%C3%A9_de_graphes"><span>Lire</span></a></li><li id="ca-ve-edit" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Trac%C3%A9_de_graphes&veaction=edit" title="Modifier cette page [v]" accesskey="v"><span>Modifier</span></a></li><li id="ca-edit" class="collapsible vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Trac%C3%A9_de_graphes&action=edit" title="Modifier le wikicode de cette page [e]" accesskey="e"><span>Modifier le code</span></a></li><li id="ca-history" class="vector-tab-noicon mw-list-item"><a href="/w/index.php?title=Trac%C3%A9_de_graphes&action=history" title="Historique des versions de cette page [h]" accesskey="h"><span>Voir l’historique</span></a></li> </ul> </div> </div> </nav> <nav class="vector-page-tools-landmark" aria-label="Outils de la page"> <div id="vector-page-tools-dropdown" class="vector-dropdown vector-page-tools-dropdown" > <input type="checkbox" id="vector-page-tools-dropdown-checkbox" role="button" aria-haspopup="true" data-event-name="ui.dropdown-vector-page-tools-dropdown" class="vector-dropdown-checkbox " aria-label="Outils" > <label id="vector-page-tools-dropdown-label" for="vector-page-tools-dropdown-checkbox" class="vector-dropdown-label cdx-button cdx-button--fake-button cdx-button--fake-button--enabled cdx-button--weight-quiet" aria-hidden="true" ><span class="vector-dropdown-label-text">Outils</span> </label> <div class="vector-dropdown-content"> <div id="vector-page-tools-unpinned-container" class="vector-unpinned-container"> <div id="vector-page-tools" class="vector-page-tools vector-pinnable-element"> <div class="vector-pinnable-header vector-page-tools-pinnable-header vector-pinnable-header-unpinned" data-feature-name="page-tools-pinned" data-pinnable-element-id="vector-page-tools" data-pinned-container-id="vector-page-tools-pinned-container" data-unpinned-container-id="vector-page-tools-unpinned-container" > <div class="vector-pinnable-header-label">Outils</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-page-tools.pin">déplacer vers la barre latérale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-page-tools.unpin">masquer</button> </div> <div id="p-cactions" class="vector-menu mw-portlet mw-portlet-cactions emptyPortlet vector-has-collapsible-items" title="Plus d’options" > <div class="vector-menu-heading"> Actions </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="ca-more-view" class="selected vector-more-collapsible-item mw-list-item"><a href="/wiki/Trac%C3%A9_de_graphes"><span>Lire</span></a></li><li id="ca-more-ve-edit" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Trac%C3%A9_de_graphes&veaction=edit" title="Modifier cette page [v]" accesskey="v"><span>Modifier</span></a></li><li id="ca-more-edit" class="collapsible vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Trac%C3%A9_de_graphes&action=edit" title="Modifier le wikicode de cette page [e]" accesskey="e"><span>Modifier le code</span></a></li><li id="ca-more-history" class="vector-more-collapsible-item mw-list-item"><a href="/w/index.php?title=Trac%C3%A9_de_graphes&action=history"><span>Voir l’historique</span></a></li> </ul> </div> </div> <div id="p-tb" class="vector-menu mw-portlet mw-portlet-tb" > <div class="vector-menu-heading"> Général </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-whatlinkshere" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Pages_li%C3%A9es/Trac%C3%A9_de_graphes" title="Liste des pages liées qui pointent sur celle-ci [j]" accesskey="j"><span>Pages liées</span></a></li><li id="t-recentchangeslinked" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Suivi_des_liens/Trac%C3%A9_de_graphes" rel="nofollow" title="Liste des modifications récentes des pages appelées par celle-ci [k]" accesskey="k"><span>Suivi des pages liées</span></a></li><li id="t-upload" class="mw-list-item"><a href="/wiki/Aide:Importer_un_fichier" title="Téléverser des fichiers [u]" accesskey="u"><span>Téléverser un fichier</span></a></li><li id="t-specialpages" class="mw-list-item"><a href="/wiki/Sp%C3%A9cial:Pages_sp%C3%A9ciales" title="Liste de toutes les pages spéciales [q]" accesskey="q"><span>Pages spéciales</span></a></li><li id="t-permalink" class="mw-list-item"><a href="/w/index.php?title=Trac%C3%A9_de_graphes&oldid=210301171" title="Adresse permanente de cette version de cette page"><span>Lien permanent</span></a></li><li id="t-info" class="mw-list-item"><a href="/w/index.php?title=Trac%C3%A9_de_graphes&action=info" title="Davantage d’informations sur cette page"><span>Informations sur la page</span></a></li><li id="t-cite" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:Citer&page=Trac%C3%A9_de_graphes&id=210301171&wpFormIdentifier=titleform" title="Informations sur la manière de citer cette page"><span>Citer cette page</span></a></li><li id="t-urlshortener" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:UrlQ%C4%B1sald%C4%B1c%C4%B1s%C4%B1&url=https%3A%2F%2Ffr.wikipedia.org%2Fwiki%2FTrac%25C3%25A9_de_graphes"><span>Obtenir l'URL raccourcie</span></a></li><li id="t-urlshortener-qrcode" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:QrKodu&url=https%3A%2F%2Ffr.wikipedia.org%2Fwiki%2FTrac%25C3%25A9_de_graphes"><span>Télécharger le code QR</span></a></li> </ul> </div> </div> <div id="p-coll-print_export" class="vector-menu mw-portlet mw-portlet-coll-print_export" > <div class="vector-menu-heading"> Imprimer / exporter </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="coll-create_a_book" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:Livre&bookcmd=book_creator&referer=Trac%C3%A9+de+graphes"><span>Créer un livre</span></a></li><li id="coll-download-as-rl" class="mw-list-item"><a href="/w/index.php?title=Sp%C3%A9cial:DownloadAsPdf&page=Trac%C3%A9_de_graphes&action=show-download-screen"><span>Télécharger comme PDF</span></a></li><li id="t-print" class="mw-list-item"><a href="/w/index.php?title=Trac%C3%A9_de_graphes&printable=yes" title="Version imprimable de cette page [p]" accesskey="p"><span>Version imprimable</span></a></li> </ul> </div> </div> <div id="p-wikibase-otherprojects" class="vector-menu mw-portlet mw-portlet-wikibase-otherprojects" > <div class="vector-menu-heading"> Dans d’autres projets </div> <div class="vector-menu-content"> <ul class="vector-menu-content-list"> <li id="t-wikibase" class="wb-otherproject-link wb-otherproject-wikibase-dataitem mw-list-item"><a href="https://www.wikidata.org/wiki/Special:EntityPage/Q739462" title="Lien vers l’élément dans le dépôt de données connecté [g]" accesskey="g"><span>Élément Wikidata</span></a></li> </ul> </div> </div> </div> </div> </div> </div> </nav> </div> </div> </div> <div class="vector-column-end"> <div class="vector-sticky-pinned-container"> <nav class="vector-page-tools-landmark" aria-label="Outils de la page"> <div id="vector-page-tools-pinned-container" class="vector-pinned-container"> </div> </nav> <nav class="vector-appearance-landmark" aria-label="Apparence"> <div id="vector-appearance-pinned-container" class="vector-pinned-container"> <div id="vector-appearance" class="vector-appearance vector-pinnable-element"> <div class="vector-pinnable-header vector-appearance-pinnable-header vector-pinnable-header-pinned" data-feature-name="appearance-pinned" data-pinnable-element-id="vector-appearance" data-pinned-container-id="vector-appearance-pinned-container" data-unpinned-container-id="vector-appearance-unpinned-container" > <div class="vector-pinnable-header-label">Apparence</div> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-pin-button" data-event-name="pinnable-header.vector-appearance.pin">déplacer vers la barre latérale</button> <button class="vector-pinnable-header-toggle-button vector-pinnable-header-unpin-button" data-event-name="pinnable-header.vector-appearance.unpin">masquer</button> </div> </div> </div> </nav> </div> </div> <div id="bodyContent" class="vector-body" aria-labelledby="firstHeading" data-mw-ve-target-container> <div class="vector-body-before-content"> <div class="mw-indicators"> </div> <div id="siteSub" class="noprint">Un article de Wikipédia, l'encyclopédie libre.</div> </div> <div id="contentSub"><div id="mw-content-subtitle"></div></div> <div id="mw-content-text" class="mw-body-content"><div class="mw-content-ltr mw-parser-output" lang="fr" dir="ltr"><p>En <a href="/wiki/Th%C3%A9orie_des_graphes" title="Théorie des graphes">théorie des graphes</a>, le <b>tracé de graphes</b> consiste à représenter des graphes dans le plan. Le tracé de graphes est utile à des applications telles que la conception de circuits <a href="/wiki/VLSI" class="mw-redirect" title="VLSI">VLSI</a>, l'analyse de <a href="/wiki/R%C3%A9seau_social" title="Réseau social">réseaux sociaux</a>, la <a href="/wiki/Cartographie" title="Cartographie">cartographie</a>, et la <a href="/wiki/Bio-informatique" title="Bio-informatique">bio-informatique</a>. </p> <meta property="mw:PageProp/toc" /> <div class="mw-heading mw-heading2"><h2 id="Types_de_tracés"><span id="Types_de_trac.C3.A9s"></span>Types de tracés</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trac%C3%A9_de_graphes&veaction=edit&section=1" title="Modifier la section : Types de tracés" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Trac%C3%A9_de_graphes&action=edit&section=1" title="Modifier le code source de la section : Types de tracés"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Les graphes sont généralement représentés en utilisant des points, disques ou boites pour représenter les sommets, et des courbes ou des segments pour représenter les arêtes. Pour les <a href="/wiki/Graphe_orient%C3%A9" title="Graphe orienté">graphes orientés</a>, on utilise habituellement ses <a href="/wiki/Fl%C3%A8che_(symbole)" title="Flèche (symbole)">flèches</a> en bout d'arête pour représenter l'orientation. Cette représentation graphique ne doit pas être confondue avec le graphe lui-même (la structure abstraite et non graphique). Des dessins très différents peuvent correspondre au même graphe. La seule chose qui compte vraiment est le nombre d'arêtes entre chaque paire de sommets. En pratique, cependant l'arrangement de ces nœuds et arêtes influence la compréhensibilité, l'usabilité, le coût de fabrication et l'esthétique. </p><p>D'autres exemples de conventions sont la <a href="/wiki/Graphe_d%27intersection" title="Graphe d'intersection">représentation par intersection</a> et les représentations de la <a href="/wiki/Matrice_d%27adjacence" title="Matrice d'adjacence">matrice d'adjacence</a>. </p> <div class="mw-heading mw-heading2"><h2 id="Méthodes"><span id="M.C3.A9thodes"></span>Méthodes</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trac%C3%A9_de_graphes&veaction=edit&section=2" title="Modifier la section : Méthodes" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Trac%C3%A9_de_graphes&action=edit&section=2" title="Modifier le code source de la section : Méthodes"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Fondées sur ces concepts et problématiques, différentes stratégies de <i>dessin</i> de graphes existent, telles que: </p> <ul><li><a href="/wiki/Force-based_layout" title="Force-based layout">Layout dirigé par les forces</a> : minimisation par <a href="/wiki/Descente_de_gradient" class="mw-redirect" title="Descente de gradient">descente de gradient</a> d'une fonction d'énergie, inspiré par une métaphore physique.</li> <li><a href="/w/index.php?title=Spectral_layout&action=edit&redlink=1" class="new" title="Spectral layout (page inexistante)">spectral layout</a>: layout basé sur une <a href="/w/index.php?title=Fonction_%C3%A9nergie&action=edit&redlink=1" class="new" title="Fonction énergie (page inexistante)">fonction énergie</a> qui est <i> amenable</i> à de la minimisation globale fondée sur des techniques d'algèbre linéaire.</li> <li>orthogonal layout: <i>layout</i> avec des arcs courant horizontalement et verticalement, avec des approches pour réduire le nombre d'arcs s'entrecoupant ainsi que la superficie. Ils sont d'un grand intérêt dans le domaine de <a href="/wiki/VLSI" class="mw-redirect" title="VLSI">VLSI</a> et conception de <a href="/w/index.php?title=Printed_circuit_board&action=edit&redlink=1" class="new" title="Printed circuit board (page inexistante)">PCB</a> .</li> <li>symmetric layout: ils essayent de trouver les <a href="/wiki/Groupe_de_sym%C3%A9trie" title="Groupe de symétrie">groupes de symétries</a> dans le graphe.</li> <li>dessins arborescents : techniques spécialisées pour le tracé d'<a href="/wiki/Arbre_(th%C3%A9orie_des_graphes)" title="Arbre (théorie des graphes)">arbre</a>.</li> <li>dessins hiérarchiques : essayent de trouver une source et un puits dans un graphe orienté et d'arranger les nœuds en <i>strates</i> en ayant le plus d'arcs commençant vers la source et suivant la direction du puits.</li></ul> <p>Dans certaines applications de tracé de graphes, il est important de formellement <a href="/w/index.php?title=Sp%C3%A9cification_logicielle&action=edit&redlink=1" class="new" title="Spécification logicielle (page inexistante)">spécifier</a> la <a href="/wiki/Mise_en_%C5%93uvre" title="Mise en œuvre">mise en œuvre</a> et la <a href="/wiki/M%C3%A9thode_formelle_(informatique)" title="Méthode formelle (informatique)">vérification formelle</a> de ces procédures. </p> <div class="mw-heading mw-heading2"><h2 id="Métriques"><span id="M.C3.A9triques"></span>Métriques</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trac%C3%A9_de_graphes&veaction=edit&section=3" title="Modifier la section : Métriques" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Trac%C3%A9_de_graphes&action=edit&section=3" title="Modifier le code source de la section : Métriques"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <figure class="mw-halign-right" typeof="mw:File/Thumb"><a href="/wiki/Fichier:Complete_graph_K4.svg" class="mw-file-description"><img src="//upload.wikimedia.org/wikipedia/commons/thumb/5/59/Complete_graph_K4.svg/150px-Complete_graph_K4.svg.png" decoding="async" width="150" height="150" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/5/59/Complete_graph_K4.svg/225px-Complete_graph_K4.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/5/59/Complete_graph_K4.svg/300px-Complete_graph_K4.svg.png 2x" data-file-width="512" data-file-height="512" /></a><figcaption>K<sub>4</sub> (le <a href="/wiki/Graphe_complet" title="Graphe complet">graphe complet</a> d'ordre 4) peut être dessiné avec ou sans arcs croisés (en déplaçant l'un des sommets à l'intérieur du triangle formé par les trois autres)</figcaption></figure> <p>Il n'y a pas de « meilleur » tracé — différentes manières d'afficher un graphe montrent différentes caractéristiques. Une <a href="/wiki/M%C3%A9trique_(math%C3%A9matiques)" class="mw-redirect" title="Métrique (mathématiques)">métrique</a> d'un algorithme de tracé de graphes est le nombre d'arcs s'entrecoupant. Alors que certains graphes ne peuvent être tracés sans que les arcs s'entrecoupent, certains graphes <i>peuvent</i> l'être, on les appelle des <a href="/wiki/Graphe_planaire" title="Graphe planaire">graphes planaires</a>. D'après cette métrique, les « bons » algorithmes tracent des graphes avec aussi peu de croisements que possible. Le <a href="/wiki/Nombre_de_croisements_(th%C3%A9orie_des_graphes)" title="Nombre de croisements (théorie des graphes)">nombre minimal de croisements</a> d'un graphe possible mesure cette propension. </p> <div class="mw-heading mw-heading2"><h2 id="Voir_aussi">Voir aussi</h2><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trac%C3%A9_de_graphes&veaction=edit&section=4" title="Modifier la section : Voir aussi" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Trac%C3%A9_de_graphes&action=edit&section=4" title="Modifier le code source de la section : Voir aussi"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <div class="mw-heading mw-heading3"><h3 id="Articles_connexes">Articles connexes</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trac%C3%A9_de_graphes&veaction=edit&section=5" title="Modifier la section : Articles connexes" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Trac%C3%A9_de_graphes&action=edit&section=5" title="Modifier le code source de la section : Articles connexes"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/Diagramme_%C3%A9tats-transitions" title="Diagramme états-transitions">Diagramme états-transitions</a></li> <li><a href="/wiki/M%C3%A9canique_mol%C3%A9culaire" title="Mécanique moléculaire">Mécanique moléculaire</a></li></ul> <div class="mw-heading mw-heading3"><h3 id="Bibliographie">Bibliographie</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trac%C3%A9_de_graphes&veaction=edit&section=6" title="Modifier la section : Bibliographie" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Trac%C3%A9_de_graphes&action=edit&section=6" title="Modifier le code source de la section : Bibliographie"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li>Giuseppe Di Battista, <a href="/w/index.php?title=Peter_Eades&action=edit&redlink=1" class="new" title="Peter Eades (page inexistante)">Peter Eades</a> <a href="https://en.wikipedia.org/wiki/Peter_Eades" class="extiw" title="en:Peter Eades"><span class="indicateur-langue" title="Article en anglais : « Peter Eades »">(en)</span></a>, Roberto Tamassia, Ioannis G. Tollis. Graph Drawing: Algorithms for the Visualization of Graphs. <a href="/wiki/Prentice_Hall" title="Prentice Hall">Prentice Hall</a>, 1999.</li> <li>Giuseppe Di Battista, Peter Eades, Roberto Tamassia, Ioannis G. Tollis. Algorithms for Drawing Graphs: an Annotated Bibliography. Computational Geometry: Theory and Applications 4:235-282 (1994). <a rel="nofollow" class="external text" href="http://www.cs.brown.edu/people/rt/gd.html">www.cs.brown.edu</a></li> <li>Isabel F. Cruz, Roberto Tamassia. Graph Drawing Tutorial. <a rel="nofollow" class="external text" href="http://www.cs.brown.edu/~rt/papers/gd-tutorial/gd-constraints.pdf">www.cs.brown.edu</a></li></ul> <div class="mw-heading mw-heading3"><h3 id="Liens_externes">Liens externes</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trac%C3%A9_de_graphes&veaction=edit&section=7" title="Modifier la section : Liens externes" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Trac%C3%A9_de_graphes&action=edit&section=7" title="Modifier le code source de la section : Liens externes"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <p>Exemples de layouts de graphes: </p> <ul><li><a rel="nofollow" class="external text" href="http://pigale.sourceforge.net/images.html">PIGALE Images</a></li> <li><a rel="nofollow" class="external text" href="http://www.dia.uniroma3.it/~gdt/editablePages/sample_applications.htm">www.dia.uniroma3.it</a></li> <li><a rel="nofollow" class="external text" href="http://www.tomsawyer.com/gallery/index.php">Data Visualization Software | Tom Sawyer Software Image Gallery</a></li> <li><a rel="nofollow" class="external text" href="http://www.aisee.com/gallery">aiSee Graph Gallery</a></li> <li><a rel="nofollow" class="external text" href="http://www.graphviz.org/Gallery.php">Graphviz</a></li> <li><a rel="nofollow" class="external text" href="http://www.yworks.com/en/products_yfiles_practicalinfo_gallery.htm">yWorks - Products</a></li> <li><a rel="nofollow" class="external text" href="http://www.visualcomplexity.com">VisualComplexity.com</a> - A visual exploration on mapping complex networks</li></ul> <p>Une collection de <i>layouts</i> de graphes animés interactivement: </p> <ul><li><a rel="nofollow" class="external text" href="http://www.ilog.com/products/jviews/demos/index.cfm">IBM ILOG Visualization for Java</a></li> <li><a rel="nofollow" class="external text" href="http://www.yworks.com/en/products_yfiles_practicalinfo_demos.htm">yWorks - Products</a></li> <li><a rel="nofollow" class="external text" href="http://www.tensegrity-software.com/graph-demo.html">Tensegrity Software - Graph Framework Sample Applications</a></li> <li><a rel="nofollow" class="external text" href="http://www.gd2005.org/">GD 2005 (Limerick, Ireland)</a> -- One of the top academic conferences for new research in graph drawing is the annually held International Symposium on Graph Drawing (GD).</li> <li><a rel="nofollow" class="external text" href="http://graphdrawing.org">graphdrawing.org</a> - Site fournissant des points d'entrée sur les problématiques des graphes.</li></ul> <div class="mw-heading mw-heading3"><h3 id="Outils_de_tracés_de_layout_de_graphes"><span id="Outils_de_trac.C3.A9s_de_layout_de_graphes"></span>Outils de tracés de layout de graphes</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trac%C3%A9_de_graphes&veaction=edit&section=8" title="Modifier la section : Outils de tracés de layout de graphes" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Trac%C3%A9_de_graphes&action=edit&section=8" title="Modifier le code source de la section : Outils de tracés de layout de graphes"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a rel="nofollow" class="external text" href="http://aragorn.ads.tuwien.ac.at/AGD/">aragorn.ads.tuwien.ac.at</a></li> <li><a rel="nofollow" class="external text" href="http://pigale.sourceforge.net">pigale.sourceforge.net</a> - Public Implementation of a Graph Algorithm Library and Editor.</li> <li><a rel="nofollow" class="external text" href="http://www.dia.uniroma3.it/~gdt/">GDToolkit</a> - Boite à outils pour dessiner des graphes comportant une interface de programmation orienté objet (GAPI) et gestion par lot via une ligne de commande (BLAG).</li> <li><a rel="nofollow" class="external text" href="http://www.tomsawyer.com">www.tomsawyer.com</a> - Ensemble de services pour créer, manipuler et afficher des graphes.</li> <li><a href="/wiki/Graphviz" title="Graphviz">Graphviz</a> : <a rel="nofollow" class="external text" href="http://www.graphviz.org">www.graphviz.org</a> - Visualisation de graphe supportant le langage <a href="/wiki/DOT_(langage)" title="DOT (langage)">DOT</a>.</li> <li><a rel="nofollow" class="external text" href="http://www.cs.uni-sb.de/RW/users/sander/html/gsvcg1.html">www.cs.uni-sb.de</a></li> <li><a rel="nofollow" class="external text" href="http://www.aisee.com">www.aisee.com</a></li> <li><a rel="nofollow" class="external text" href="http://www.tulip-software.org">www.tulip-software.org</a></li> <li><a rel="nofollow" class="external text" href="http://www.oreas.com/">www.oreas.com</a></li> <li><a rel="nofollow" class="external text" href="http://www.ilog.com/products/jviews/graphlayout/">IBM ILOG Visualization for Java</a></li> <li><a rel="nofollow" class="external text" href="http://www.algorithmic-solutions.com/enalgocomsdiagram.htm">www.algorithmic-solutions.com</a></li> <li><a rel="nofollow" class="external text" href="http://www.jgraph.com/">www.jgraph.com</a></li> <li><a rel="nofollow" class="external text" href="http://www.yworks.com/en/products.htm">yWorks - Products</a> - Ensemble de service pour créer/éditer des graphes (yEd).</li> <li><a rel="nofollow" class="external free" href="ftp://ftp.cs.uni-sb.de/pub/graphics/vcg/doc/tr-A03-94.ps.gz">ftp://ftp.cs.uni-sb.de/pub/graphics/vcg/doc/tr-A03-94.ps.gz</a></li> <li><a rel="nofollow" class="external free" href="https://github.com/Gravisto/Gravisto">https://github.com/Gravisto/Gravisto</a> - Visualisation et édition de graphes.</li> <li><a rel="nofollow" class="external text" href="http://www.wilmascope.org">www.wilmascope.org</a></li> <li><a rel="nofollow" class="external text" href="http://www.cs.uleth.ca/~vpak/gluskap">..:: GLuskap ::..</a></li> <li><a rel="nofollow" class="external text" href="http://jung.sourceforge.net">jung.sourceforge.net</a> - Outil de modélisation, d'analyse et d'édition de graphes développé en Java.</li> <li><a rel="nofollow" class="external text" href="http://www.tensegrity-software.com">www.tensegrity-software.com</a></li></ul> <div class="mw-heading mw-heading3"><h3 id="Formats_de_graphes">Formats de graphes</h3><span class="mw-editsection"><span class="mw-editsection-bracket">[</span><a href="/w/index.php?title=Trac%C3%A9_de_graphes&veaction=edit&section=9" title="Modifier la section : Formats de graphes" class="mw-editsection-visualeditor"><span>modifier</span></a><span class="mw-editsection-divider"> | </span><a href="/w/index.php?title=Trac%C3%A9_de_graphes&action=edit&section=9" title="Modifier le code source de la section : Formats de graphes"><span>modifier le code</span></a><span class="mw-editsection-bracket">]</span></span></div> <ul><li><a href="/wiki/GML" class="mw-disambig" title="GML">GML</a></li> <li><a href="/wiki/GraphML" title="GraphML">GraphML</a></li> <li><a href="/w/index.php?title=GraphXML&action=edit&redlink=1" class="new" title="GraphXML (page inexistante)">GraphXML</a></li> <li><a href="/w/index.php?title=GXL&action=edit&redlink=1" class="new" title="GXL (page inexistante)">GXL</a></li> <li><a rel="nofollow" class="external text" href="http://gexf.net/format/">GEXF</a></li> <li><a href="/wiki/DOT_(langage)" title="DOT (langage)">DOT</a></li></ul> <ul id="bandeau-portail" class="bandeau-portail"><li><span class="bandeau-portail-element"><span class="bandeau-portail-icone"><span class="noviewer skin-invert-image" typeof="mw:File"><a href="/wiki/Portail:Informatique_th%C3%A9orique" title="Portail de l'informatique théorique"><img alt="icône décorative" src="//upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/30px-Max-cut.svg.png" decoding="async" width="30" height="24" class="mw-file-element" srcset="//upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/45px-Max-cut.svg.png 1.5x, //upload.wikimedia.org/wikipedia/commons/thumb/c/cf/Max-cut.svg/60px-Max-cut.svg.png 2x" data-file-width="200" data-file-height="160" /></a></span></span> <span class="bandeau-portail-texte"><a href="/wiki/Portail:Informatique_th%C3%A9orique" title="Portail:Informatique théorique">Portail de l'informatique théorique</a></span> </span></li> </ul>    </div><noscript><img src="https://login.wikimedia.org/wiki/Special:CentralAutoLogin/start?useformat=desktop&type=1x1&usesul3=0" alt="" width="1" height="1" style="border: none; position: absolute;"></noscript> <div class="printfooter" data-nosnippet="">Ce document provient de « <a dir="ltr" href="https://fr.wikipedia.org/w/index.php?title=Tracé_de_graphes&oldid=210301171">https://fr.wikipedia.org/w/index.php?title=Tracé_de_graphes&oldid=210301171</a> ».</div></div> <div id="catlinks" class="catlinks" data-mw="interface"><div id="mw-normal-catlinks" class="mw-normal-catlinks"><a href="/wiki/Cat%C3%A9gorie:Accueil" title="Catégorie:Accueil">Catégorie</a> : <ul><li><a href="/wiki/Cat%C3%A9gorie:Th%C3%A9orie_topologique_des_graphes" title="Catégorie:Théorie topologique des graphes">Théorie topologique des graphes</a></li></ul></div><div id="mw-hidden-catlinks" class="mw-hidden-catlinks mw-hidden-cats-hidden">Catégories cachées : <ul><li><a href="/wiki/Cat%C3%A9gorie:Article_contenant_un_appel_%C3%A0_traduction_en_anglais" title="Catégorie:Article contenant un appel à traduction en anglais">Article contenant un appel à traduction en anglais</a></li><li><a href="/wiki/Cat%C3%A9gorie:Portail:Informatique_th%C3%A9orique/Articles_li%C3%A9s" title="Catégorie:Portail:Informatique théorique/Articles liés">Portail:Informatique théorique/Articles liés</a></li><li><a href="/wiki/Cat%C3%A9gorie:Portail:Informatique/Articles_li%C3%A9s" title="Catégorie:Portail:Informatique/Articles liés">Portail:Informatique/Articles liés</a></li><li><a href="/wiki/Cat%C3%A9gorie:Projet:Math%C3%A9matiques/Articles" title="Catégorie:Projet:Mathématiques/Articles">Projet:Mathématiques/Articles</a></li></ul></div></div> </div> </main> </div> <div class="mw-footer-container"> <footer id="footer" class="mw-footer" > <ul id="footer-info"> <li id="footer-info-lastmod"> La dernière modification de cette page a été faite le 6 décembre 2023 à 01:34.</li> <li id="footer-info-copyright"><span style="white-space: normal"><a href="/wiki/Wikip%C3%A9dia:Citation_et_r%C3%A9utilisation_du_contenu_de_Wikip%C3%A9dia" title="Wikipédia:Citation et réutilisation du contenu de Wikipédia">Droit d'auteur</a> : les textes sont disponibles sous <a rel="nofollow" class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.fr">licence Creative Commons attribution, partage dans les mêmes conditions</a> ; d’autres conditions peuvent s’appliquer. Voyez les <a class="external text" href="https://foundation.wikimedia.org/wiki/Policy:Terms_of_Use/fr">conditions d’utilisation</a> pour plus de détails, ainsi que les <a href="/wiki/Wikip%C3%A9dia:Cr%C3%A9dits_graphiques" title="Wikipédia:Crédits graphiques">crédits graphiques</a>. En cas de réutilisation des textes de cette page, voyez <a href="/wiki/Sp%C3%A9cial:Citer/Trac%C3%A9_de_graphes" title="Spécial:Citer/Tracé de graphes">comment citer les auteurs et mentionner la licence</a>.<br /> Wikipedia® est une marque déposée de la <a rel="nofollow" class="external text" href="https://wikimediafoundation.org/">Wikimedia Foundation, Inc.</a>, organisation de bienfaisance régie par le paragraphe <a href="/wiki/501c" title="501c">501(c)(3)</a> du code fiscal des États-Unis.</span><br /></li> </ul> <ul id="footer-places"> <li id="footer-places-privacy"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Privacy_policy/fr">Politique de confidentialité</a></li> <li id="footer-places-about"><a href="/wiki/Wikip%C3%A9dia:%C3%80_propos_de_Wikip%C3%A9dia">À propos de Wikipédia</a></li> <li id="footer-places-disclaimers"><a href="/wiki/Wikip%C3%A9dia:Avertissements_g%C3%A9n%C3%A9raux">Avertissements</a></li> <li id="footer-places-contact"><a href="//fr.wikipedia.org/wiki/Wikipédia:Contact">Contact</a></li> <li id="footer-places-wm-codeofconduct"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Universal_Code_of_Conduct">Code de conduite</a></li> <li id="footer-places-developers"><a href="https://developer.wikimedia.org">Développeurs</a></li> <li id="footer-places-statslink"><a href="https://stats.wikimedia.org/#/fr.wikipedia.org">Statistiques</a></li> <li id="footer-places-cookiestatement"><a href="https://foundation.wikimedia.org/wiki/Special:MyLanguage/Policy:Cookie_statement">Déclaration sur les témoins (cookies)</a></li> <li id="footer-places-mobileview"><a href="//fr.m.wikipedia.org/w/index.php?title=Trac%C3%A9_de_graphes&mobileaction=toggle_view_mobile" class="noprint stopMobileRedirectToggle">Version mobile</a></li> </ul> <ul id="footer-icons" class="noprint"> <li id="footer-copyrightico"><a href="https://wikimediafoundation.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/static/images/footer/wikimedia-button.svg" width="84" height="29" alt="Wikimedia Foundation" loading="lazy"></a></li> <li id="footer-poweredbyico"><a href="https://www.mediawiki.org/" class="cdx-button cdx-button--fake-button cdx-button--size-large cdx-button--fake-button--enabled"><img src="/w/resources/assets/poweredby_mediawiki.svg" alt="Powered by MediaWiki" width="88" height="31" loading="lazy"></a></li> </ul> </footer> </div> </div> </div> <div class="vector-settings" id="p-dock-bottom"> <ul></ul> </div><script>(RLQ=window.RLQ||[]).push(function(){mw.config.set({"wgHostname":"mw-web.codfw.main-66c5b56c76-l6nf2","wgBackendResponseTime":227,"wgPageParseReport":{"limitreport":{"cputime":"0.063","walltime":"0.092","ppvisitednodes":{"value":221,"limit":1000000},"postexpandincludesize":{"value":3241,"limit":2097152},"templateargumentsize":{"value":293,"limit":2097152},"expansiondepth":{"value":12,"limit":100},"expensivefunctioncount":{"value":1,"limit":500},"unstrip-depth":{"value":0,"limit":20},"unstrip-size":{"value":0,"limit":5000000},"entityaccesscount":{"value":1,"limit":400},"timingprofile":["100.00% 66.502 1 -total"," 73.36% 48.784 1 Modèle:Portail"," 29.99% 19.947 1 Modèle:Catégorisation_badges"," 27.67% 18.400 1 Modèle:Suivi_des_biographies"," 26.40% 17.556 1 Modèle:Lien"," 11.16% 7.419 1 Modèle:Portail_informatique_théorique"," 7.32% 4.870 1 Modèle:Méta_lien_vers_portail"," 3.69% 2.452 1 Modèle:Méta_lien_vers_portail/Catégorisation"]},"scribunto":{"limitreport-timeusage":{"value":"0.023","limit":"10.000"},"limitreport-memusage":{"value":1056555,"limit":52428800}},"cachereport":{"origin":"mw-web.codfw.main-6b7f745dd4-xwfb6","timestamp":"20241125143542","ttl":2592000,"transientcontent":false}}});});</script> <script type="application/ld+json">{"@context":"https:\/\/schema.org","@type":"Article","name":"Trac\u00e9 de graphes","url":"https:\/\/fr.wikipedia.org\/wiki\/Trac%C3%A9_de_graphes","sameAs":"http:\/\/www.wikidata.org\/entity\/Q739462","mainEntity":"http:\/\/www.wikidata.org\/entity\/Q739462","author":{"@type":"Organization","name":"Contributeurs aux projets Wikimedia"},"publisher":{"@type":"Organization","name":"Fondation Wikimedia, Inc.","logo":{"@type":"ImageObject","url":"https:\/\/www.wikimedia.org\/static\/images\/wmf-hor-googpub.png"}},"datePublished":"2006-05-15T15:39:58Z","dateModified":"2023-12-06T00:34:43Z"}</script> </body> </html>