Graphe Partitionable

Graphe Partitionable

Graphe partitionable

Sommaire

Définitions

Graphe partitionable

Un graphe G est dit partitionable s'il admet une S-partition pour toute partition S de | V | . | V | correspond au cardinal de l'ensemble des sommets de G.

Un graphe G est dit k-partitionable s'il admet une S-partition pour toute k-partition S de | V | .

S-Partition

On note [m] = \left \{ 1, ...,m \right \}.

Soient G un graphe et \ S = (s_1, ..., s_m ) une partition de \ |V|, G est dit admettre une S-partition s'il existe une partition \ P(S)=\left \{V_i : i \in [m]\right \} de V telle que :

  • \ \forall i \in [m], |V_i| = s_i
  • \ \forall i \in [m], G[V_i] est un graphe connexe. L'ensemble P(S) est alors dit être une partition de G induite par S.

On considère de plus ici que :

  • V est un ensemble non vide
  • L'ensemble des arêtes E est un sous-ensemble de l'ensemble des parties à deux éléments de V

Partition d'un entier

Soit n un entier strictement positif, une partition de n est une suite d’entiers \ (s_1, ..., s_m ) vérifiant

  • \ m \ge 1
  • \ \forall i \in [m] \mbox{ on a } s_i \ne 0
  • \sum_{i=1}^m s_i = n

Une k-partition de n est une partition de n possédant k éléments.

Exemples

k-partition(n)

  • Une 2-partition de 5 est (3,2).
  • Une 4-partition de 10 est (1,4,1,4).
  • Une 7-partition de 22 est (2,2,3,1,3,8,3).

S-partition de G

  • Soit le graphe G tel que V = {a,b,c,d,e,f} et E = { {a,b},{b,c},{c,d},{d,e},{e,f},{f,a},{c,e} } représenté ci-dessous par :

Graphe 6 sommets.png

| V | = 6. G admet 3 partitions de 6 possibles : (1,1,4), (1,2,3) et (2,2,2) (en considérant que l'ordre des différentes suites n'a pas d'importance).

Ces trois partitions de l'entier 6 peuvent être appliquées respectivement pour partager le graphe G comme ceci :

Graphe k partitionable.png

Il existe bien d'autres façon d'appliquer ces 3-partitions sur ce graphe. Le schéma ci-dessus est une des représentations possibles.

  • Portail des mathématiques Portail des mathématiques
Ce document provient de « Graphe partitionable ».

Wikimedia Foundation. 2010.

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

Игры ⚽ Нужен реферат?

Regardez d'autres dictionnaires:

  • Graphe partitionable — Sommaire 1 Définitions 1.1 Partition d un entier 1.2 k partition d un entier 1.3 S partition d un graphe …   Wikipédia en Français

  • Graphe de Ferrer — Partition d un entier Une partition d un entier strictement positif n est une façon d écrire n comme une somme d entiers strictement positifs. Deux sommes qui diffèrent seulement de l ordre de leurs opérandes sont considérées comme étant la même… …   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

  • Partage d'un entier — Partition d un entier Une partition d un entier strictement positif n est une façon d écrire n comme une somme d entiers strictement positifs. Deux sommes qui diffèrent seulement de l ordre de leurs opérandes sont considérées comme étant la même… …   Wikipédia en Français

  • Partition entière — Partition d un entier Une partition d un entier strictement positif n est une façon d écrire n comme une somme d entiers strictement positifs. Deux sommes qui diffèrent seulement de l ordre de leurs opérandes sont considérées comme étant la même… …   Wikipédia en Français

  • Partition d'un entier — Pour les articles homonymes, voir Partition.  En particulier en mathématiques, ne pas confondre avec la notion de partition de l unité ni celle de partition d un ensemble …   Wikipédia en Français

Share the article and excerpts

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