Voir la source de Graphe scindé

[[Fichier:Split_graph.svg|vignette|240x240px| Un graphe scindé, partitionné en une clique et un ensemble stable.]]
En [[théorie des graphes]], un '''graphe scindé'''<ref>Le terme « scindé » est utilisé dans plusieurs textes, par exemple la thèse {{Ouvrage
|auteur1= Tom Bouvier 
|titre= Graphes et décomposition
|éditeur= Université de Bordeaix
|année= 2014
|hal= tel-01110277
|passage= &nbsp; Chapitre 3. Graphes d’incidence et graphes scindés, p. 18
|consulté le=17 juillet 2021
}}.</ref> ou '''graphe séparé''' (en anglais : '''split graph''') est un graphe dont les sommets peuvent être partitionnés deux parties :  une [[Clique (théorie des graphes)|clique]] et un [[Stable (théorie des graphes)|ensemble stable]]. Les graphes scindés ont été étudiés pour la première fois par Földes et Marteau en 1977<ref>{{harvsp|Földes|Hammer|1977a}} ; {{harvsp|Földes|Hammer|1977b|}}.</ref>, et introduit indépendamment par Tyshkevich et Tchernyak en 1979<ref>{{harvsp|Tyshkevich|Chernyak|1979}}.</ref>{{,}} <ref>{{harvsp|Földes|Hammer|1977a}} donent une définition plus générale, dans laquelle les graphes scindés comprennent aussi les [[graphe biparti|graphes bipartis]] (c'est-à-dire les graphes qui peuvent être partitionnés en deux ensembles stables) et les [[Graphe complémentaire|compléments]] de graphes bipartis, (c'est-à-dire les graphes qui peuvent être partitionnés en deux cliques). {{harvsp|Földes|Hammer|1977b}} utilisent la définition donnée ici, qui est aussi utilisée dans la littérature ultérieure, par exemple dans {{harvsp|Brandstädt|Le|Spinrad|1999|loc= Definition 3.2.3, p. 41}}.</ref>{{,}}<ref>La terminologie « graphe séparé » se trouve par exemple dans les notes sur les [http://perso.ens-lyon.fr/eric.thierry/Graphes2007/florian-hatat.pdf graphes parfaits] de Florian Hatat.</ref>.

== Exemples élémentaires ==

Un graphe scindé peut avoir plus d'une partition en une clique et un ensemble stable ; par exemple, le chemin ''a'' – ''b'' – ''c'' est un graphe scindé, dont les sommets peuvent être partitionnés de trois manières différentes :

# la clique <math>\{a,b\}</math> et l'ensemble stable <math>\{c\}</math> ;
# la clique <math>\{b,c\}</math> et l'ensemble stable <math>\{a\}</math> ;
# la clique <math>\{b\}</math> et l'ensemble stable <math>\{a,c\}</math>.

Les graphes scindés peuvent être caractérisés par leurs sous-graphes induits interdits : un graphe est scindé si et seulement si aucun sous-graphe induit n'est un [[Graphe cycle|cycle]] sur quatre ou cinq sommets, ou n'est une paire d'arêtes disjointes (le complément d'un 4-cycle<ref>{{harvsp|Földes|Hammer|1977a}}</ref>{{,}}<ref>{{harvsp|Golumbic|1980}}, Theorem 6.3, p. 151.</ref>.

== Relation avec d'autres familles de graphes ==
De par leur définition, les graphes scindé sont clairement fermés par [[Graphe complémentaire|complémentation]]. Une autre caractérisation des graphes scindés fait intervenir la complémentation : ce sont des [[Graphe cordal|graphes cordaux]] dont les [[Graphe complémentaire|compléments]] sont également cordaux. Tout comme les graphes cordaux sont les [[Graphe d'intersection|graphes d'intersection]] de sous-arbres d'arbres, les graphes scindés sont les graphes d'intersection de sous-étoiles distinctes de [[Graphe étoile| graphes en étoile]]<ref>{{harvsp|McMorris|Shier|1983}}; {{harvsp|Voss|1985}}; {{harvsp|Brandstädt|Le|Spinrad|1999}}, Theorem 4.4.2, p. 52.</ref>. [[Presque tous]] les graphes cordaux sont des graphes scindés, au sens où la fraction des graphes cordaux scindés parmi les graphes cordaux à ''n'' sommets qui sont scindé tend vers 1 lorsque ''n'' tend vers l'infini<ref>{{harvsp|Bender|Richmond|Wormald|1985}}.</ref>.

Comme les graphes cordaux sont [[Graphe parfait|parfaits]], les graphes scindés le sont aussi. Les '''graphes à double scission''', une famille de graphes dérivés de graphes scindés en doublant chaque sommet (la clique induit alors un  anti-couplage et l'ensemble stable induit un couplage), figure, dans la preuve de {{harvsp|Chudnovsky|Robertson|Seymour|Thomas|2006}} du [[théorème des graphes parfaits]] fort, comme l'une des cinq classes de base de graphes parfaits à partir desquels tous les autres peuvent être formés.

Si un graphe est à la fois un graphe scindé et un [[Graphe d'intervalles|graphe d'intervalle]], alors son complément est à la fois un graphe scindé et un [[graphe de comparabilité]], et vice versa. Les graphes de comparabilité scindés, et donc aussi les graphes d'intervalles scindés, peuvent être caractérisés en termes d'un ensemble de trois sous-graphes induits interdits<ref>{{harvsp|Földes|Hammer|1977b}} ; {{harvsp|Golumbic|1980}}, Theorem 9.7, page 212.</ref>. Les [[Cographe|cographes]] scindés sont exactement les [[Graphe à seuil|graphes à seuil]]. Les [[Graphe de permutation|graphes de permutation]] scindés sont exactement les graphes d'intervalle dont les compléments sont des graphes d'intervalle<ref>{{harvsp|Brandstädt|Le|Spinrad|1999}}, Corollary 7.1.1, p. 106, et Theorem 7.1.2, p. 107.</ref> ;  ce sont les graphes de permutation pour des permutations symétriques gauches{{Sfnp|Kézdy|Snevily|Wang|1996}}. Les graphes scindés ont un [[Cocoloration|nombre cochromatique]] égal à 2.

== Problèmes algorithmiques ==
Soit ''G'' un graphe scindé, partitionné en une clique ''C'' et un ensemble stable ''I''. Alors chaque [[Clique (théorie des graphes)|clique maximale]] dans le graphe scindé est soit ''C'' lui-même, soit le [[Voisinage (théorie des graphes)|voisinage]] d'un sommet dans ''I''. Ainsi, il est facile d'identifier la clique maximale et, de manière complémentaire, l'[[Stable (théorie des graphes)|ensemble stable maximal]] dans un graphe scindé. Dans tout graphe scindé, l'une des trois conditions suivantes est réalisée<ref>{{harvsp|Hammer|Simeone|1981}}; {{harvsp|Golumbic|1980|loc=Theorem 6.2, p. 150}}.</ref> : 

# Il existe un sommet <math>x</math>  dans <math>I</math> tel que <math>C\cup \{x\}</math> est complet. Dans ce cas, <math>C\cup \{x\}</math>  est une clique maximale et <math>I</math> est un ensemble stable maximal.
# Il existe un sommet <math>x</math>  dans <math>C</math> tel que <math>I\cup \{x\}</math> est stable. Dans ce cas, <math>I\cup \{x\}</math> est un ensemble stable maximum et  <math>C</math> est une clique maximum.
#  <math>C</math> est une clique maximale et <math>I</math> est un ensemble stable maximal. Dans ce cas, ''G'' a une partition unique  <math>(C,I)</math> en une clique et un ensemble stable, <math>C</math> est la clique maximale et <math>I</math> est l'ensemble stable maximal.

Certains problèmes d'optimisation qui sont [[Problème NP-complet|NP-complets]] sur des familles de graphes plus générales, y compris la [[coloration de graphe]]s, deviennent simples sur des graphes scindés. Trouver une [[chaîne hamiltonienne]] reste [[Problème NP-complet|NP-complet]] même pour les graphes scindés qui sont des graphes cordaux forts<ref>{{harvsp|Müller|1996}}.</ref>. Il est également connu que le problème de l'ensemble dominant minimum reste [[Problème NP-complet|NP-complet]] pour les graphes scindés<ref>{{harvsp|Bertossi|1984}}.</ref>.

== Suites de degrés ==
Une propriété remarquable des graphes scindés est qu'ils peuvent être reconnus uniquement à partir de leurs suite de [[degré (théorie des graphes)|degré]]s. Soit <math>d_1\ge d_2\ge\cdots\ge d_n</math>''d'' <sub>1</sub> ≥ ''d'' <sub>2</sub> ≥ ... ≥ ''d'' <sub>''n''</sub> la suite de degrés d'un graphe ''G''  et soit <math>m</math> le plus grand indice <math>i</math> tel que <math>d_i\ge i-1</math>. Alors ''G'' est un graphe scindé si et seulement si

: <math>\sum_{i=1}^m d_i = m(m-1) + \sum_{i=m+1}^n d_i.</math>

Dans cas les ''m'' sommets avec les degrés les plus grands forment une clique maximale dans ''G'', et les sommets restants constituent un ensemble stable<ref>{{harvsp|Hammer|Simeone|1981}}</ref>{{,}}<ref>{{harvsp|Tyshkevich|1980}}</ref>{{,}}<ref>{{harvsp|Tyshkevich|Melnikow|Kotov|1981}}</ref>{{,}}<ref>{{harvsp|Golumbic|1980}}, Theorem 6.7 et Corollary 6.8, p. 154</ref>{{,}}<ref> {{harvsp|Brandstädt|Le|Spinrad|1999}}, Theorem 13.3.2, p. 203.</ref>. {{harv|Merris|2003}} étudie plus à fond les suites de degrés de graphes scindés.

== Nombre de graphes scindés ==
Gordon F. Royle a démontré<ref>{{harvsp|Royle|2000}}</ref> que les graphes scindé à ''n'' sommets sont en [[bijection]] avec certaines [[Famille de Sperner|familles de Sperner]]. À l'aide de cette observation, il a établi une formule pour le nombre de graphes scindés non isomorphes à ''n'' sommets. Les premières valeurs de cette suite, à partir de ''n'' = 1, sont

: 1, 2, 4, 9, 21, 56, 164, 557, 2223, 10766, 64956, 501696, ... {{OEIS|id=A048194}}     .

Ce résultat d'énumération a également été prouvé, en 1990, par Tyshkevich et Chernyak<ref>{{harvsp|Tyshkevich|Chernyak|1990}}</ref>.

== Notes et références ==
{{Références}}
== Bibliographie ==

*{{article
 | nom1 = Bender | prénom1 = E. A.
 | nom2 = Richmond | prénom2 = L. B.
 | nom3 = Wormald | prénom3 = N. C.
 | titre = Almost all chordal graphs split
 | journal = J. Austral. Math. Soc.
 | collection = A
 | volume = 38
 | année = 1985
 | numéro = 2
 | mr = 0770128
 | pages = 214–221
 | doi = 10.1017/S1446788700023077| accès doi = libre
 }}.
*{{article
 | nom = Bertossi | prénom = Alan A.
 | titre = Dominating sets for split and bipartite graphs
 | journal = [[Information Processing Letters]]
 | volume = 19
 | année = 1984
 | pages = 37–40
 | doi=10.1016/0020-0190(84)90126-1
}}.
*{{ouvrage
 | nom1 = Brandstädt
 | prénom1 = Andreas
 | lien auteur1 = Andreas Brandstädt
 | nom2 = Le
 | prénom2 = Van Bang
 | nom3 = Spinrad
 | prénom3 = Jeremy
 | titre = Graph Classes: A Survey
 | éditeur = SIAM Monographs on Discrete Mathematics and Applications
 | année = 1999
 | isbn = 0-89871-432-X
 | accès url = inscription
 | url = https://archive.org/details/graphclassessurv0000bran
 }}.
*{{article
 | nom1 = Chudnovsky | prénom1 = Maria | lien auteur1 = Maria Chudnovsky
 | nom2 = Robertson | prénom2 = Neil | lien auteur2 = Neil Robertson (mathématicien)
 | nom3 = Seymour | prénom3 = Paul | lien auteur3 = Paul Seymour (mathématicien)
 | nom4 = Thomas | prénom4 = Robin | lien auteur4 = Robin Thomas (mathématicien)
 | titre = The strong perfect graph theorem
 | journal = [[Annals of Mathematics]]
 | volume = 164
 | année = 2006
 | numéro = 1
 | pages = 51–229
 | mr = 2233847
 | doi = 10.4007/annals.2006.164.51| arxiv = math/0212070}}.
* {{article|nom1=Dukes|prénom1=Mark
 |titre=The sandpile model on the complete split graph, Motzkin words, and tiered parking functions
 |journal=Journal of Combinatorial Theory, Series A
 |volume=180|année=2021
 |pages=105418
 |doi=10.1016/j.jcta.2021.105418}}.
*{{article
 | nom1 = Földes | prénom1 = Stéphane
 | nom2 = Hammer | prénom2 = Peter Ladislaw | lien auteur2 =Peter Ladislaw Hammer
 | titre = Split graphs
 | périodique = Proceedings of the Eighth Southeastern Conference on Combinatorics, Graph Theory and Computing (Louisiana State Univ., Baton Rouge, La., 1977)
 | pages = 311–315
 | collection = Congressus Numerantium
 | numéro dans collection = XIX
 | éditeur = Utilitas Math.
 | lieu = Winnipeg
 | année = 1977a
 | mr = 0505860}}.
*{{article
 | nom1 = Földes | prénom1 = Stéphane
 | nom2 = Hammer | prénom2 = Peter Ladislaw | lien auteur2 =Peter Ladislaw Hammer
 | titre = Split graphs having Dilworth number two
 | journal = [[Canadian Journal of Mathematics]]
 | volume = 29
 | année = 1977b
 | numéro = 3
 | pages = 666–672
 | mr = 0463041
 | doi = 10.4153/CJM-1977-069-1}}.
*{{ouvrage
 | nom = Golumbic | prénom = Martin Charles | lien auteur = Martin Charles Golumbic
 | titre = Algorithmic Graph Theory and Perfect Graphs
 | éditeur = Academic Press
 | année = 1980
 | isbn = 0-12-289260-7
 | mr = 0562306}}.
*{{article
 | nom1 = Hammer | prénom1 = Peter Ladislaw | lien auteur1 = Peter Ladislaw Hammer
 | nom2 = Simeone | prénom2 = Bruno
 | titre = The splittance of a graph
 | journal = [[Combinatorica]]
 | volume = 1
 | année = 1981
 | numéro = 3
 | pages = 275–284
 | mr = 0637832
 | doi = 10.1007/BF02579333}}.
*{{article
 | nom1 = Kézdy | prénom1 = André E.
 | nom2 = Snevily | prénom2 = Hunter S.
 | nom3 = Wang | prénom3 = Chi
 | doi = 10.1016/S0097-3165(96)80012-4
 | numéro = 2
 | journal = [[Journal of Combinatorial Theory]], Series A
 | mr = 1370138
 | pages = 353–359
 | titre = Partitioning permutations into increasing and decreasing subsequences
 | volume = 73
 | année = 1996| accès doi = libre
 }}.
* {{article|nom1=Lintzmayer|prénom1=C. N.|nom2=Mota|prénom2=G. O.|nom3=Sambinelli|prénom3=M.
 |titre=Decomposing split graphs into locally irregular graphs
 |journal=Discrete Applied Mathematics|volume=292|année=2021|pages=33–44|doi=10.1016/j.dam.2020.12.002}}.
* {{Article
|auteur1= Nicolas Maack | auteur2= Hendrik Molter | auteur3= Rolf Niedermeier |auteur4= Malte Renken
|titre= On Finding Separators in Temporal Split and Permutation Graphs
|périodique= arxiv
|date= 2021
|pages=
|arxiv= 2105.12003
|consulté le=12 juillet 2021
}}.
*{{article
 | nom1 = McMorris | prénom1 = F. R.
 | nom2 = Shier | prénom2 = D. R.
 | titre = Representing chordal graphs on ''K''<sub>1,''n''</sub>
 | journal = Commentationes Mathematicae Universitatis Carolinae
 | volume = 24
 | année = 1983
 | pages = 489–494
 | mr = 0730144}}.
*{{article
 | nom = Merris | prénom = Russell
 | titre = Split graphs
 | journal = [[European Journal of Combinatorics]]
 | volume = 24
 | année = 2003
 | numéro = 4
 | pages = 413–430
 | doi = 10.1016/S0195-6698(03)00030-1
 | mr = 1975945| accès doi = libre
 }}.
*{{article
 | nom = Müller | prénom = Haiko
 | titre = Hamiltonian Circuits in Chordal Bipartite Graphs
 | journal = [[Discrete Mathematics (journal)|Discrete Mathematics]]
 | volume = 156
 | année = 1996
 | pages = 291–298
 | doi=10.1016/0012-365x(95)00057-4
| accès doi = libre
 }}.
*{{article
 | nom = Royle | prénom = Gordon F. | lien auteur = Gordon Royle
 | titre = Counting set covers and split graphs
 | journal = Journal of Integer Sequences
 | volume = 3
 | année = 2000
 | numéro = 2
 | pages = 00.2.6
 | mr = 1778996
 | url = http://www.emis.ams.org/journals/JIS/VOL3/ROYLE/royle.pdf}}.
*{{article
 | nom = Tyshkevich | prénom = Regina I. | lien auteur=Regina Tyshkevich
 | titre = The canonical decomposition of a graph
 | langue = ru
 | journal = [[Doklady Akademii Nauk SSSR]]
 | volume = 24
 | année = 1980
 | pages = 677–679
 | mr = 0587712}}
*{{article
 | nom1 = Tyshkevich | prénom1 = Regina I. | lien auteur1=Regina Tyshkevich
 | nom2 = Chernyak | prénom2 = A. A.
 | titre = Canonical partition of a graph defined by the degrees of its vertices
 | langue = ru
 | année = 1979
 | journal = Isv. Akad. Nauk BSSR, Ser. Fiz.-Mat. Nauk
 | volume = 5
 | pages = 14–26
 | mr = 0554162}}.
*{{article
 | nom1 = Tyshkevich | prénom1 = Regina I. | lien auteur1=Regina Tyshkevich
 | nom2 = Chernyak | prénom2 = A. A.
 | titre= Еще один метод перечисления непомеченных комбинаторных объектов
 | langue = ru
 | année = 1990
 | journal = Mat. Zametki
 | volume = 48
 | pages = 98–105
 | mr = 1102626
 | url = http://mi.mathnet.ru/eng/mz3413
 | numéro = 6}}. — Traduction : {{article|titre=Yet another method of enumerating unmarked combinatorial objects|journal=Mathematical Notes of the Academy of Sciences of the USSR|volume=48|numéro=6|année=1990|pages=1239–1245|issn=0001-4346|doi=10.1007/BF01240267}}.
*{{article
 | nom1 = Tyshkevich | prénom1 = Regina I. | lien auteur1=Regina Tyshkevich
 | nom2 = Melnikow | prénom2 = O. I.
 | nom3 = Kotov | prénom3 = V. M.
 | titre = On graphs and degree sequences: the canonical decomposition
 | langue = ru
 | journal = Kibernetika
 | volume = 6
 | année = 1981
 | pages = 5–8
 | mr = 0689420}}.
*{{article
 | nom = Voss | prénom = H.-J.
 | titre = Note on a paper of McMorris and Shier
 | journal = Commentationes Mathematicae Universitatis Carolinae
 | volume = 26
 | année = 1985
 | pages = 319–322
 | mr = 0803929}}.

== Liens externes ==
{{Liens}}
* {{MathWorld|nom_url=SplitGraph|titre= Split Graph}}

{{Portail|mathématiques|informatique théorique}}

[[Catégorie:Graphe parfait]]
[[Catégorie:Famille de graphes]]