Graphe couronne

Graphe couronne
Graphes couronnes avec six, huit ou dix sommets.

Notation	$S_{n}^{0}$
Nombre de sommets	$2n$
Nombre d'arêtes	$n(n-1)$
Distribution des degrés	$(n-1){\text{ - régulier}}$
Rayon	$\left\{{\begin{array}{ll}\infty &n\leq 2\\3&{\text{sinon}}\end{array}}\right.$
Diamètre	$\left\{{\begin{array}{ll}\infty &n\leq 2\\3&{\text{sinon}}\end{array}}\right.$
Maille	$\left\{{\begin{array}{ll}\infty &n\leq 2\\6&n=3\\4&{\text{sinon}}\end{array}}\right.$
Nombre chromatique	$\left\{{\begin{array}{ll}1&n=1\\2&{\text{sinon}}\end{array}}\right.$
Propriétés	Régulier Biparti Symétrique Distance-transitif
modifier

En théorie des graphes, une branche des mathématiques, un graphe couronne à 2 n sommets est un graphe non orienté comportant deux jeux de sommets u_i et v_i reliés par une arête de u_i à v_j à chaque fois que i ≠ j.

Exemples

Le graphe couronne à six sommets est un graphe cycle.

Le graphe couronne à huit sommets est le graphe hexaédrique, celui qui décrit les sommets et les arêtes d'un cube.

Autres façons de voir le graphe couronne

Le graphe couronne peut être vu comme un graphe biparti complet d'où l'on aurait retiré les arêtes formant un couplage parfait (les arêtes horizontales absentes sur la figure).

On peut aussi le voir comme la double couverture bipartie (en) d'un graphe complet.

Si l'on considère un ensemble à n éléments et tous ses sous-ensembles à 1 ou à n - 1 éléments, le graphe couronne montre toutes les possibilités qu'un de ces sous-ensembles en contienne un autre. Cela fait du graphe couronne un graphe biparti de Kneser H_{n, 1}.

Propriétés

Le nombre d'arêtes d'un graphe couronne est le nombre oblong n (n − 1).

Le nombre achromatique est n : on obtient une coloration complète en attribuant n couleurs aux sommets d'une des partitions, les mêmes n couleurs aux sommets de l'autre partition et en prenant des couleurs identiques pour les sommets non reliés^[1].

Les graphes couronne sont symétriques et distance-transitifs.

Le graphe complémentaire du graphe couronne à 2 n sommets est le graphe qui décrirait les mouvements possibles d'une tour sur un échiquier à n rangées et à 2 colonnes (graphe de la tour (en)).

Applications

Les règles traditionnelles de savoir-vivre imposent de placer les convives à table en alternant les hommes et les femmes et de manière qu'aucun couple marié ne soit assis côte à côte. Les façons de placer les convives selon ces règles sont les cycles hamiltoniens d'un graphe couronne, où les sommets représentent les convives et les arêtes représentent les compatibilités entre ces convives. Déterminer toutes ces façons de placer les convives constitue le problème des ménages.

Les graphes couronnes fournissent un bon exemple pour montrer que l'algorithme glouton de coloration de graphe se comporte mal si l'on ne choisit pas bien l'ordre dans lequel on colore les sommets. En effet, si les sommets sont passés à l'algorithme glouton dans l'ordre (u₀, v₀, u₁, v₁, …, u_n, v_n), l'algorithme utilisera n couleurs, alors que le nombre optimal de couleurs n'est que de 2. Cette construction est attribuée à D. S. Johnson^[2], c'est pourquoi les graphes couronnes sont parfois appelés graphes de Johnson et notés J_n^[3].

Références

↑ (en) Amitabh Chaudhary et Sundar Vishwanathan, SODA '97: Proceedings of the 8th ACM-SIAM Symposium on Discrete Algorithms, 1997, p. 558-563.
↑ (en) D. S. Johnson, Proc. 5th Southeastern Conf. on Combinatorics, Graph Theory, and Computing, Utilitas Mathematicae, Winnipeg, 1974, p. 513-527
↑ (en) M. Kubale, Graph Colorings, American Mathematical Society, 2004 (ISBN 0-8218-3458-4)

Lien externe

(en) (en) Eric W. Weisstein et Simone Severini, « Crown Graph », sur MathWorld

Portail des mathématiques

Read other articles:

Halle Bailey

Halle BaileyBailey pada Desember 2020LahirHalle Lynn Bailey27 Maret 2000 (umur 23)Atlanta, Georgia, Amerika SerikatPekerjaanPenyanyiPenulis laguAktrisTahun aktif2006–sekarangKarier musikAsalMableton, Georgia, Amerika SerikatGenreR&Bneo soulpopInstrumen Vokal gitar LabelParkwoodColumbia Halle Lynn Bailey (lahir 27 Maret 2000) adalah seorang penyanyi-penulis lagu dan aktris asal Amerika Serikat. Dia dikenal sebagai anggota dari duo musik Chloe x Halle dengan saudara perempuanny...

Esteban Paredes

Nama ini menggunakan cara penamaan Spanyol: nama keluarga pertama atau paternalnya adalah Paredes dan nama keluarga kedua atau maternalnya adalah Quintanilla. Esteban Paredes Esteban Paredes, Colo Colo v Huachipato, Stadion Monumental, Santiago, Chili. 2018Informasi pribadiNama lengkap Esteban Efraín Paredes QuintanillaTanggal lahir 1 Agustus 1980 (umur 43)Tempat lahir Santiago, ChiliTinggi 1,76 m (5 ft 9+1⁄2 in)Posisi bermain PenyerangInformasi klubKlub saat i...

منتخب بلجيكا تحت 17 سنة لكرة السلة للسيدات

هذه المقالة تحتاج للمزيد من الوصلات للمقالات الأخرى للمساعدة في ترابط مقالات الموسوعة. فضلًا ساعد في تحسين هذه المقالة بإضافة وصلات إلى المقالات المتعلقة بها الموجودة في النص الحالي. (أغسطس 2019) منتخب بلجيكا تحت 17 سنة لكرة السلة للسيدات البلد بلجيكا كأس العالم لكرة السل�...

BMW Seri 5 (G30)

BMW Seri 5 (G30/G31/G32)InformasiProdusenBMWModel untuk tahun2017–2023Bodi & rangkaKelasKendaraan mewah ukuran medium / Mobil eksekutif (E)Bentuk kerangka4-pintu sedan5-pintu estateTata letakMesin depan, penggerak roda belakangMesin depan, penggerak 4 rodaPlatformBMW OKL platformPenyalur dayaMesinMesin bensin:2.0 L B48 turbocharger I43.0 L B58 turbocharger I64.4 L N63TU2 turbocharger V8mesin diesel:2.0 L B47 turbocharger I43.0 L B57 turbocharger I63.0 L quad-turbo I6Transmisi6...

Alexandra Danilova

Russian-American ballerina (1903–1997) This article includes a list of general references, but it lacks sufficient corresponding inline citations. Please help to improve this article by introducing more precise citations. (July 2015) (Learn how and when to remove this template message) In this name that follows Eastern Slavic naming customs, the patronymic is Dionisyevna and the family name is Danilova. Alexandra DanilovaАлександра ДаниловаDanilova as Fanny Cerrito in ...

コルク

この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）出典検索?: コルク – ニュース · 書籍 · スカラー · CiNii · J-STAGE · NDL · dlib.jp · ジャパンサーチ · TWL（2017年4月）コルクを打ち抜いて作った瓶の栓コルク（木栓、�...

羅德島州

本條目存在以下問題，請協助改善本條目或在討論頁針對議題發表看法。此條目需要擴充。 (2013年1月1日)请協助改善这篇條目，更進一步的信息可能會在討論頁或扩充请求中找到。请在擴充條目後將此模板移除。此條目需要补充更多来源。 (2013年1月1日)请协助補充多方面可靠来源以改善这篇条目，无法查证的内容可能會因為异议提出而被移除。致使用者：请搜索一下条目的...

他侬·吉滴卡宗

泰国陆军元帅他侬·吉滴卡宗ถนอม กิตติขจรPChW SR MPCh MWM第10任泰國總理任期1963年12月9日—1973年10月14日君主拉玛九世前任沙立·他那叻元帥继任訕耶·探瑪塞任期1958年1月1日—1958年10月20日君主拉玛九世前任乃朴·沙拉信继任沙立·他那叻元帥第32任泰國國防部長任期1957年9月23日—1973年10月14日前任鑾披汶·頌堪继任他威·尊拉塞（英语：Dawee Chullasapya）个人资料出...

She's Having a Baby

1988 film by John Hughes She's Having a BabyTheatrical release posterDirected byJohn HughesWritten byJohn HughesProduced byJohn HughesBill BrownRonald ColbyStarring Kevin Bacon Elizabeth McGovern CinematographyDonald PetermanEdited byAlan HeimMusic byStewart CopelandProductioncompanyHughes EntertainmentDistributed byParamount PicturesRelease date February 5, 1988 (1988-02-05) Running time106 minutesCountryUnited StatesLanguageEnglishBudget$20 million[1]Box office$16 mil...

Max Roser

Economist and philosopher Max RoserBorn1983 (age 40–41)Kirchheimbolanden, West GermanyAcademic careerInstitutionNuffield College, OxfordOxford Martin SchoolFieldEconomics of income distribution, poverty, global development, global healthInfluencesTony Atkinson, Amartya Sen, Angus Deaton, Hans Rosling Websitewww.maxroser.comwww.ourworldindata.org Max Roser (born 1983) is an economist and philosopher who focuses on large global problems such as poverty, disease, hunger, climate chang...

Marc Gasol

Spanish basketball player (born 1985) In this Spanish name, the first or paternal surname is Gasol and the second or maternal family name is Sáez. Marc GasolGasol in 2019Bàsquet GironaPositionPresidentLeagueLiga ACBPersonal informationBorn (1985-01-29) 29 January 1985 (age 39)Barcelona, SpainListed height6 ft 11 in (2.11 m)Listed weight255 lb (116 kg)Career informationHigh schoolLausanne Collegiate(Memphis, Tennessee)NBA draft2007: 2nd round, 48th overa...

غريميشوفو (نيزنيج نوفغورود)

غريميشوفو الإحداثيات 55°23′27″N 43°02′17″E / 55.390833333333°N 43.038055555556°E / 55.390833333333; 43.038055555556 تقسيم إداري البلد روسيا[1] عدد السكان عدد السكان 3660 (1979)[2]5335 (1989)[3]5303 (2002)[4]5272 (2008)[5]5293 (2009)[5]5262 (2010)[4]5265 (2011)[5]5252 (2012)[6]5227 (2013)[7]5223 (2...

Mauro Turrisi

Mauro Turrisi Deputato del Regno d'ItaliaLegislaturaXIX, XX, XXI GruppoparlamentareSinistra CollegioCefalù Sito istituzionale Senatore del Regno d'ItaliaDurata mandato4 luglio 1908 – LegislaturaXXII Sito istituzionale Dati generaliProfessioneImprenditore Mauro Giovanni Giuseppe Francesco Maria Turrisi Colonna, Barone di Gorgo e Bonvicino (Palermo, 14 marzo 1856 – Fiuggi, 11 agosto 1912), è stato un imprenditore e politico italiano. Biografia Figlio del senatore Nicol�...

選挙ステーション

ニュースステーション > 選挙ステーション報道ステーション > 選挙ステーション選挙ステーション番組のスタジオがあるテレビ朝日本社ビルジャンル選挙特別番組出演者大越健介大下容子小木逸平板倉朋希渡辺瑠海製作制作テレビ朝日（ANN）放送映像形式リアルタイム字幕放送（2012年12月16日放送回より）連動データ放送音声形式ステレオ放送放送国・�...

Bayonne

Subprefecture of Pyrénées-Atlantiques, Nouvelle-Aquitaine For other uses, see Bayonne (disambiguation). Subprefecture and commune in Nouvelle-Aquitaine, FranceBayonne Baiona (Basque)Subprefecture and communeView of the historic centre FlagCoat of armsLocation of Bayonne BayonneShow map of FranceBayonneShow map of Nouvelle-AquitaineCoordinates: 43°29′N 1°29′W / 43.49°N 1.48°W / 43.49; -1.48CountryFranceRegionNouvelle-AquitaineDepartmentPyrénées-Atlantiq...

テッド・デビアス

この項目では、ザ・ミリオンダラー・マンのニックネームで知られるプロレスラーについて説明しています。彼の息子のテッド・デビアスについては「テッド・デビアス・ジュニア」をご覧ください。テッド・デビアス 2021年プロフィールリングネームテッド・デビアス本名セオドア・マーヴィン・デビアスニックネームザ・ミリオンダラー・マン鋼鉄男二世Trillionai...

Foreach loop

Control flow statement for traversing items in a collection For for all in logic (∀), see Universal quantification. foreach loops are almost always used to iterate over items in a sequence of elements. Loop constructs Do while loop While loop For loop Foreach loop Infinite loop Control flow vte In computer programming, foreach loop (or for-each loop) is a control flow statement for traversing items in a collection. foreach is usually used in place of a standard for loop statement. Unlike ot...

Molucche

Isole MolucchePosizione delle Molucche rispetto all'IndonesiaGeografia fisicaCoordinate3°06′S 129°23′E3°06′S, 129°23′E ArcipelagoArcipelago malese Superficie74 505 km² Geografia politicaStato Indonesia ProvinciaMolucche, Molucche Settentrionali DemografiaAbitanti1 895 000 (2000) Etnicomolucchése[1] Cartografia Isole Molucche voci di isole dell'Indonesia presenti su Wikipedia Le Molucche (in indonesiano Maluku) sono un gruppo di isole dell'Indonesia, p...

Jukskei River

River in Gauteng, South AfricaJukskei RiverJukskei flowing past Gillooly's FarmLocation of the Jukskei River mouthLocationCountrySouth AfricaProvinceGautengPhysical characteristicsSourceNatural Spring • locationEllis Park,[1] Johannesburg, South Africa • coordinates26°11′46″S 28°03′50″E / 26.196°S 28.064°E / -26.196; 28.064 MouthCrocodile River • coordinates25°52′34″S 27°55′38″E ...

Kasparov versus the World

Animation of the game Game of chess Kasparov versus the World was a game of chess played in 1999 over the Internet.[1] It was a consultation game, in which a World Team of thousands decided each move for the black pieces by plurality vote, while Garry Kasparov conducted the white pieces by himself. More than 50,000 people from over 75 countries participated in the game. The host and promoter of the match was the MSN Gaming Zone, with sponsorship from First USA bank.[2] After 6...