| Property |
Value |
| dbo:abstract
|
- En informatique théorique, le problème de l'isomorphisme de graphes est le problème de décision qui consiste, étant donné deux graphes non orientés, à décider s'ils sont isomorphes ou pas, c'est-à-dire s'ils sont les mêmes, quitte à renommer les sommets. Ce problème est particulièrement important en théorie de la complexité, plus particulièrement pour le problème P=NP. En effet, le problème de l'isomorphisme de graphes est l'un des problèmes de NP, pour lequel on ne connaît ni d'algorithme en temps polynomial ni de preuve de NP-complétude. On le soupçonne être un problème NP-intermédiaire[réf. souhaitée]. Cependant le problème peut être résolu en temps polynomial pour certaines classes de graphes, par exemple les graphes planaires ou les graphes de degré borné et en temps quasi-polynomial pour le cas général. Ce problème peut-être vu comme une restriction du problème de l'isomorphisme de sous-graphes. où les graphes G et H ont le même nombre de sommets. En pratique, l'isomorphisme de graphes est utilisé en chimie pour classer les molécules. (fr)
- En informatique théorique, le problème de l'isomorphisme de graphes est le problème de décision qui consiste, étant donné deux graphes non orientés, à décider s'ils sont isomorphes ou pas, c'est-à-dire s'ils sont les mêmes, quitte à renommer les sommets. Ce problème est particulièrement important en théorie de la complexité, plus particulièrement pour le problème P=NP. En effet, le problème de l'isomorphisme de graphes est l'un des problèmes de NP, pour lequel on ne connaît ni d'algorithme en temps polynomial ni de preuve de NP-complétude. On le soupçonne être un problème NP-intermédiaire[réf. souhaitée]. Cependant le problème peut être résolu en temps polynomial pour certaines classes de graphes, par exemple les graphes planaires ou les graphes de degré borné et en temps quasi-polynomial pour le cas général. Ce problème peut-être vu comme une restriction du problème de l'isomorphisme de sous-graphes. où les graphes G et H ont le même nombre de sommets. En pratique, l'isomorphisme de graphes est utilisé en chimie pour classer les molécules. (fr)
|
| dbo:thumbnail
| |
| dbo:wikiPageExternalLink
| |
| dbo:wikiPageID
| |
| dbo:wikiPageLength
|
- 17249 (xsd:nonNegativeInteger)
|
| dbo:wikiPageRevisionID
| |
| dbo:wikiPageWikiLink
| |
| prop-fr:année
|
- 1977 (xsd:integer)
- 1985 (xsd:integer)
- 1996 (xsd:integer)
|
| prop-fr:doi
| |
| prop-fr:langue
| |
| prop-fr:lieu
|
- University of Alberta, Edomonton, Alberta, Canada (fr)
- University of Alberta, Edomonton, Alberta, Canada (fr)
|
| prop-fr:lireEnLigne
| |
| prop-fr:nom
|
- Read (fr)
- Fortin (fr)
- Corneil (fr)
- Tyshkevich (fr)
- Korneenko (fr)
- Zemlyachenko (fr)
- Read (fr)
- Fortin (fr)
- Corneil (fr)
- Tyshkevich (fr)
- Korneenko (fr)
- Zemlyachenko (fr)
|
| prop-fr:numéro
| |
| prop-fr:passage
|
- 339 (xsd:integer)
- 1426 (xsd:integer)
|
| prop-fr:prénom
|
- Scott (fr)
- R. I. (fr)
- Ronald C. (fr)
- N. M. (fr)
- Derek G. (fr)
- V. N. (fr)
- Scott (fr)
- R. I. (fr)
- Ronald C. (fr)
- N. M. (fr)
- Derek G. (fr)
- V. N. (fr)
|
| prop-fr:périodique
|
- Journal of Mathematical Sciences (fr)
- Journal of Graph Theory (fr)
- Journal of Mathematical Sciences (fr)
- Journal of Graph Theory (fr)
|
| prop-fr:titre
|
- The graph isomorphism problem (fr)
- Graph isomorphism problem (fr)
- The graph isomorphism disease (fr)
- The graph isomorphism problem (fr)
- Graph isomorphism problem (fr)
- The graph isomorphism disease (fr)
|
| prop-fr:volume
|
- 1 (xsd:integer)
- 29 (xsd:integer)
|
| prop-fr:wikiPageUsesTemplate
| |
| dct:subject
| |
| rdfs:comment
|
- En informatique théorique, le problème de l'isomorphisme de graphes est le problème de décision qui consiste, étant donné deux graphes non orientés, à décider s'ils sont isomorphes ou pas, c'est-à-dire s'ils sont les mêmes, quitte à renommer les sommets. En pratique, l'isomorphisme de graphes est utilisé en chimie pour classer les molécules. (fr)
- En informatique théorique, le problème de l'isomorphisme de graphes est le problème de décision qui consiste, étant donné deux graphes non orientés, à décider s'ils sont isomorphes ou pas, c'est-à-dire s'ils sont les mêmes, quitte à renommer les sommets. En pratique, l'isomorphisme de graphes est utilisé en chimie pour classer les molécules. (fr)
|
| rdfs:label
|
- Graphen-Isomorphismusproblem (de)
- Problème de l'isomorphisme de graphes (fr)
- Задача изоморфности графов (ru)
- Graphen-Isomorphismusproblem (de)
- Problème de l'isomorphisme de graphes (fr)
- Задача изоморфности графов (ru)
|
| owl:sameAs
| |
| prov:wasDerivedFrom
| |
| foaf:depiction
| |
| foaf:isPrimaryTopicOf
| |
| is dbo:wikiPageWikiLink
of | |
| is oa:hasTarget
of | |
| is foaf:primaryTopic
of | |
