Appariement (mathématiques)

Appariement (mathématiques)

Appariement (mathématiques)

Page d'aide sur l'homonymie Pour les articles homonymes, voir Appariement.

En théorie des graphes, un appariement ou couplage d'un graphe (en anglais matching) est un ensemble d'arêtes de ce graphe qui n'ont pas de sommets en commun.

Définitions

Soit un graphe G = (S,A), l'appariement M est un ensemble d'arêtes non-adjacentes deux à deux. C'est à dire, M est l'ensemble des arêtes (s_1,s_2)\in S telles que \forall ((s_1,s_2), (s_3,s_4)) \in M^2 avec (s_1,s_2)\neq(s_3,s_4), \forall i,j \in \{1,2,3,4\}, avec i \neq j, alors s_i \neq s_j .

Un appariement maximum est un appariement contenant le plus grand nombre possible d'arêtes. Un graphe peut posséder plusieurs appariements maximum.

Un appariement maximal est un appariement M du graphe tel que toute arête du graphe possède une intersection non vide avec au moins une arête de M. Il en découle la propriété suivante : soit un appariement maximal M, si une arête quelconque de A qui n'est pas dans M est ajoutée à M , alors M n'est plus un appariement de G.

Un appariement parfait ou appariement complet est un appariement M du graphe tel que tout sommet du graphe est incident à exactement une arête de M.

Propriétés

Un appariement maximum est aussi un appariement maximal.

Un appariement parfait est aussi un appariement maximal.

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Appariement (math%C3%A9matiques) ».

Wikimedia Foundation. 2010.

Contenu soumis à la licence CC-BY-SA. Source : Article Appariement (mathématiques) de Wikipédia en français (auteurs)

Игры ⚽ Поможем сделать НИР

Regardez d'autres dictionnaires:

  • Appariement (Mathématiques) — Pour les articles homonymes, voir Appariement. En théorie des graphes, un appariement ou couplage d un graphe (en anglais matching) est un ensemble d arêtes de ce graphe qui n ont pas de sommets en commun. Définitions Soit un graphe G = (S,A), l… …   Wikipédia en Français

  • Appariement (mathematiques) — Appariement (mathématiques) Pour les articles homonymes, voir Appariement. En théorie des graphes, un appariement ou couplage d un graphe (en anglais matching) est un ensemble d arêtes de ce graphe qui n ont pas de sommets en commun. Définitions… …   Wikipédia en Français

  • Liste des articles de mathematiques — Projet:Mathématiques/Liste des articles de mathématiques Cette page recense les articles relatifs aux mathématiques, qui sont liés aux portails de mathématiques, géométrie ou probabilités et statistiques via l un des trois bandeaux suivants  …   Wikipédia en Français

  • Couplage (Théorie des Graph) — Appariement (mathématiques) Pour les articles homonymes, voir Appariement. En théorie des graphes, un appariement ou couplage d un graphe (en anglais matching) est un ensemble d arêtes de ce graphe qui n ont pas de sommets en commun. Définitions… …   Wikipédia en Français

  • Couplage (Théorie des Graphes) — Appariement (mathématiques) Pour les articles homonymes, voir Appariement. En théorie des graphes, un appariement ou couplage d un graphe (en anglais matching) est un ensemble d arêtes de ce graphe qui n ont pas de sommets en commun. Définitions… …   Wikipédia en Français

  • Classification JEL — La classification JEL est la classification la plus reconnue en sciences économiques. Elle a été créée par le Journal of Economic Literature (JEL), revue publiée quatre fois par année par l American Economic Association (AEA). Sommaire 1 A –… …   Wikipédia en Français

  • L'inverse d'un nombre — Nombre La notion de nombre en linguistique est traitée à l’article Nombre grammatical Un nombre est un concept permettant d’évaluer et de comparer des quantités ou des rapports de grandeurs, mais aussi d’ordonner des éléments par une numérotation …   Wikipédia en Français

  • Nombre — La notion de nombre en linguistique est traitée à l’article « Nombre grammatical ». Un nombre est un concept permettant d’évaluer et de comparer des quantités ou des rapports de grandeurs, mais aussi d’ordonner des éléments par une… …   Wikipédia en Français

  • nombre — [ nɔ̃br ] n. m. • déb. XIIe; lat. numerus I ♦ 1 ♦ Concept de base des mathématiques, une des notions fondamentales de l entendement que l on peut rapporter à d autres idées (de pluralité, d ensemble, de correspondance), mais non définir.… …   Encyclopédie Universelle

  • Unicode — est une norme informatique, développée par le Consortium Unicode, qui vise à permettre le codage de texte écrit en donnant à tout caractère de n’importe quel système d’écriture un nom et un identifiant numérique, et ce de manière unifiée, quelle… …   Wikipédia en Français

Share the article and excerpts

Direct link
… Do a right-click on the link above
and select “Copy Link”