Metraipolis › archive › dc_d12e16bc51b4

Logique des graphes — Wikipedia (fr)

Source
Wikipedia (fr)
Original
https://fr.wikipedia.org/wiki/Logique_des_graphes
License (as archived)
CC-BY-SA-4.0
Archived
2026-10-07T16:54:41.714Z
SHA-256 of the archived text
5b77c107e7645a38cfc4d6e6c5ae2097bfceccef44bd50b837760f9f75ec8a28
Stable URL of this page
https://metraipolis.com/documento/dc_d12e16bc51b4

How to cite

Logique des graphes — Wikipedia (fr) — Wikipedia (fr), https://fr.wikipedia.org/wiki/Logique_des_graphes (CC-BY-SA-4.0); archived copy: https://metraipolis.com/documento/dc_d12e16bc51b4 (Metraipolis archive dc_d12e16bc51b4, sha256 5b77c107e7645a38cfc4d6e6c5ae2097bfceccef44bd50b837760f9f75ec8a28)
BibTeX
@misc{dcd12e16bc51b4,
  title = {Logique des graphes — Wikipedia (fr)},
  howpublished = {Wikipedia (fr)},
  url = {https://fr.wikipedia.org/wiki/Logique_des_graphes},
  note = {License CC-BY-SA-4.0; archived copy https://metraipolis.com/documento/dc_d12e16bc51b4; sha256 5b77c107e7645a38cfc4d6e6c5ae2097bfceccef44bd50b837760f9f75ec8a28},
  year = {2026}
}

Archived text

Reproduced under CC-BY-SA-4.0. Attribution: Wikipedia (fr), https://fr.wikipedia.org/wiki/Logique_des_graphes. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

Dans les domaines mathématiques de la théorie des graphes et de la théorie des modèles finis, la logique des graphes traite de la spécification formelle de propriétés de graphe en utilisant des propositions de la logique mathématique. Il existe plusieurs variantes suivant les types d'opérations logiques qui peuvent être utilisées dans ces propositions. La logique du premier ordre des graphes concerne les propositions dans lesquelles les variables et les prédicats concernent les sommets et les arêtes individuels d'un graphe, tandis que la logique monadique de graphe du second ordre permet une quantification sur des ensembles de sommets ou d'arêtes. Les logiques basées sur les plus petits opérateurs de point fixe permettent des prédicats plus généraux sur des tuples de sommets, mais ces prédicats ne peuvent être construits qu'en utilisant des opérateurs de point fixe, ce qui limite leur puissance. Une proposition S {\displaystyle S} peut être vraie pour certains graphes et fausse pour d'autres; un graphe G {\displaystyle G} est un modèle de S {\displaystyle S} , écrire G ⊨ S {\displaystyle G\models S} , si S {\displaystyle S} est vraie sur les sommets et la relation d'adjacence de G {\displaystyle G} . Le problème algorithmique de vérification du modèle (model checking) est relatif au fait de savoir si un graphe est un modèle d'une proposition donnée. Le problème algorithmique de satisfiabilité se demande s'il existe un graphe modélisant une proposition donnée. Bien que la vérification de modèle et la satisfiabilité soient difficiles en général, plusieurs méta-théorèmes algorithmiques majeurs montrent que les propriétés exprimées de cette manière peuvent être testées efficacement pour d'importantes classes de graphes. D'autres sujets de recherche en logique des graphes incluent des études sur la probabilité qu'un graphe aléatoire modélise une proposition spécifiée pour un type particulier de logique, ainsi que des méthodes de compression des données s'intéressant à la recherche de propositions logiques modélisées par un graphe unique.

Tema degli esploratori: matematica e informatica teorica (deposito sistematico; ricerca «théorie des graphes»).
Fonte: Wikipedia in francese, voce «Logique des graphes» — https://fr.wikipedia.org/wiki/Logique_des_graphes
Wikidata Q25304160 (dati Wikidata in CC0 1.0) — https://www.wikidata.org/wiki/Q25304160
Autori: i contributori di Wikipedia (cronologia: https://fr.wikipedia.org/wiki/Logique_des_graphes?action=history).
Licenza: Creative Commons Attribuzione-Condividi allo stesso modo 4.0 (CC BY-SA 4.0) — https://creativecommons.org/licenses/by-sa/4.0/. Il riuso richiede attribuzione e stessa licenza.
Estratto dell'introduzione non modificato nel contenuto; revisione 238970731, consultata il 2026-10-07T16:23:38.458Z tramite l'API ufficiale di Wikipedia. Impronta SHA-256 dell'estratto: 91463cf074c5bd7c012bee48ce496d64ecae319d7f8015d8c0fe8bc117c035ca