Graphe partitionable

Graphe partitionable

Sommaire

Définitions

Partition d'un entier

Soit n un entier strictement positif, une partition de n est une suite d’entiers (s_1, \ldots, s_m) telle que :

  • m \ge 1
  • \forall i \in \left \{ 1, ...,m \right \}, s_i > 0
  • s_1 + \ldots + s_m = n

k-partition d'un entier

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

S-partition d'un graphe

Soit G = (V,E) un graphe simple où :

  • V est l'ensemble non vide des sommets de G.
  • E est l'ensemble des arêtes de G, c'est-à-dire un sous-ensemble de l'ensemble des parties à deux éléments de V.

Soit S = (s_1, \ldots, s_m) une partition de | V | (le nombre de sommets du graphe G).

G est dit admettre une S-partition s'il existe une partition P(S)=\left \{V_i : i \in \left \{ 1, ...,m \right \} \right \} de V telle que :

  • \forall i \in \left \{ 1, ...,m \right \}, |V_i| = s_i
  • \forall i \in \left \{ 1, ...,m \right \}, G[V_i] est un graphe connexe.

L'ensemble P(S) est alors dit être une partition de G induite par S.

Graphe partitionable

Un graphe G = (V,E) est dit partitionable s'il admet une S-partition pour toute partition S de | V | .

Graphe k-partitionable

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

Exemples

k-partition de 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 = (V,E) tel que :

  • V = \left \{ a,b,c,d,e,f \right \}
  • E = \left \{  \left \{ a, b \right \},\left \{ b,c \right \}, \left \{ c,d \right \},\left \{ d, e \right \},\left \{ e,f \right \}, \left \{ f,a \right \},\left \{ c, e \right \}  \right \}

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çons d'appliquer ces 3 partitions sur ce graphe. Le schéma ci-dessus est une des représentations possibles.


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 Graphe partitionable 1.2 S Partition 1.3 Partition d un entier 2 …   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”